The Deutschs algorithm

Quantum algorithms can be divided into two classes, called A and B, the exponentially fast and the polynomially fast, respectively. 

In this section, a non-exhaustive discussion of these three algorithms, is made, showing the basic operations necessary for their implementation. 

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 first operation of the algorithm is a Hadamard logic gate applied to both qubits, yielding  

The next step is to perform an unitary operation U/, which takes the two-qubit system from a generic state, x, y) to the state x,y f x)). This transformation x, y) - x, y0 f x)) is nothing but the sum of the second qubit, the bottom line of the circuit, with f x), that is the computed function of the first qubit. The binary function, f x), is the one to be 

---

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 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. 

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... 

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],... 

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. 

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].

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... 

Zadoyan R, Kohen D, Lidar DA, Apkarian VA (2001) The manipulation of massive ro-vibronic superpositions using time-frequency-resolved coherent anti-stokes Raman scattering (TFR-CARS) from quantum control to quantum computing. Chem Phys 266 323 Bihary Z, Glenn DR, Lidar DA, 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 459... 

Guide S, Riebe M, Lancaster GPT, Becher C, Eschner J, Haffner H, Schmidt-Kaler F, Chuang IL, Blatt R (2003) Implementation of the Deutsch-Jozsa algorithm on an ion-trap quantum computer. Nature 421 48... 

Tesch CM, de Vivie-Riedle R (2004) Vibrational molecular quantum computing basis set independence and theoretical realization of the Deutsch-Josza algorithm. J Chem Phys 121 12158... 

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. 

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. 

Agudelo, J.C., Carnielli, W. Quantum algorithms, paraconsistent computation and Deutsch s problem. In Prasad, B. (ed.) Proceedings of the 2nd Indian International Conference on Artificial Intelligence, Pune, India, pp. 1609-1628 (2005)... 

---