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

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

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. 

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

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

Deutsch and Jozsa have shown that a quantum computer is able to select a true statement, A or B, in the same time that only two applications of U/ require. They also show that for some functions / any classical algorithm would require N + 1 calls of /. Thus, quantum computers do better by a factor 0(N). 

Again, Shor s and Grover s algorithms are based on the ideas given by Deutsch and Jozsa in [5]. 

---