Deutsch algorithm

After Benioff, in the year of 1985, David Deutsch gave a decisively important step towards quantum computers presenting the first example of a quantum algorithm [6]. The Deutsch algorithm shows how quantum superposition can be used to speed up computational processes. Another influent name is Richard Feynman, who was involved about the same time in the discussions of the viability of quantum computers and their use for quantum systems simulations [7]. 

Figure 3.9 Quantum circuit to implement the Deutsch algorithm. Adapted with permission from [1].

The Deutsch algorithm is used to test whether a binary function of one qubit is constant (/(0) = /( )) or balanced (/(O) /( )), without the need of computing the two possible values / (0) and / (1), separately, and then comparing their results, as it would be made in a classical computer [18]. 

The quantum circuit that describes the Deutsch algorithm is illustrated in Figure 3.9, from which we can see that at the input the qubits are in a quantum state described by ... 

Reminding that the Oracle acts only on the second set of qubits, in order to invert the phase of the searched state, it is necessary to prepare the system in the state x)[ 0)- l)]/V2. In this case, when the Oracle is applied, the system will evolve as described on Equation (3.8.9), similarly to what happens in the Deutsch algorithm. As it can be seen, the solution gets marked after the Oracle operation, inverting the phase of the desired state, i.e. x) — x), if x) is the desired item. 

The first experimental implementation of a quantum algorithm by NMR was reported by J.A. Jones and M. Mosca [3]. They demonstrated the Deutsch algorithm using as qubits the spins of two protons in a sample of partially deuterated cytosine. The observed /-coupling in this system is only 7.2 Hz, and the doublets were separated by 763 Hz. 

The result of the application of the full Deutsch algorithm is shown in Figure 5.2. The lines on the right of the spectra represent the input state 1), which remains in 1) at the output. The line on the left represents the output of the calculation the corresponding qubit always start at 0>, but it is inverted in cases (b) and (c). These represent the balanced functions. In cases (a) and (d) it remains in 0) and the function is constant. 

A variation of the Deutsch algorithm is the so called Deutsch-Jozsa algorithm, which uses more than one qubit binary functions [4]. A number of experimental demonstrations... 

I. Carmesin and K. Kremer (1988) The bond fluctuation method - a new effective algorithm for the dynamics of polymers in all spatial dimensions. Macromolecules 21, pp. 2819-2823 H.-P. Deutsch and K. Binder (1991) Interdiffusion and self-diffusion in polymer mixtures - a monte-carlo study. J. Chem. Phys. 94, pp. 2294-2304... 

So indeed, ever since the scheme was invented in 1997 there have been dozens of papers with a large impact (here is just a small selection) with algorithms performed including Grover [Jones 1998], Deutsch-Jozsa [Chuang 1998], Shor [Vandersypen 2001] recently and even teleportation [Nielsen 1998],... 

We also remark that the language needed to express quasi-inverses requires disjunction. As a result, PRISM uses an extension of the chase and backchase algorithm that is able to handle disjunctive dependencies this extension was developed as part of MARS [Deutsch and Tannen 2003], Finally, we note that we may not always succeed in finding equivalent reformulations, depending on the input query, the evolution mappings and also on the quasi-inverses that are chosen. Hence, PRISM must still rely on a human DBA to solve exceptions. 

Following Clatter and Zipper [76] the effect of Q(x) must be corrected first. After the deconvolution of Eq.(33) which may be done conveniently by the algorithm of Beniaminy and Deutsch [77] the effect of slit length embodied in Eq.(32) can be corrected using the method of Strobl [78]. For the routines to be discussed here the raw data are fitted by an approximating spline fvmction the coefficients of which are directly used for the deconvolution of integral Eq.(33) [77]. 

David Deutsch creates the first quantum algorithm. 

There exists a variation of this algorithm for systems containing more than two qubits, which was derived by Deutsch and Jozsa, and it will not be discussed here. It uses the same principles as above, and is referred as the Deutsch-Jozsa algorithm [20],... 

Figure 5.10 Quantum circuit and NMR spectra corresponding to the implementation of the Deutsch-Jozsa algorithm in a quadmpole 7 = 3/2 nucleus by Das and Kumar [6). The two qubits are represented by the central and outer transitions. Transitions pointing to the same direction represent constant functions, and to opposite directions balanced ones. Adapted with permission from Ref. [6].

O. Mangold, A. Heidebrecht, M. Mehring, NMR tomography of the three-qubit Deutsch-Jozsa algorithm, Phys. Rev. A 70 (2004) 042307. 

K. Dorai, Arvind, A. Kumar, Implementation of a Deutsch-like quantum algorithm utilizing entanglement at the two-qubit level on an NMR quantum-information processor, Phys. Rev. A 63 (2001) 034101. 

Bihary Z, Glenn D, Lidar D, Apkarian VA (2002) An implementation of the deutsch-jozsa algorithm on molecular vibronic coherences through four-wave mixing a theoretical study. Chem Phys Lett 360 62316... 

Vala J, Amitay Z, Zhang B, Leone S, Kosloff R (2002) Experimental implementation of the deutsch-jozsa algorithm for three-qubit functions using pure coherent molecular superpositions. Phys Rev A 66 62316... 

---