We propose an efficient scheme in which the Deutsch-Jozsa algorithm can be realized via Rydberg blockade interaction. Deutsch-Jozsa algorithm can fast determine whether function is constant or balanced, but this algorithm does not give the concrete value of function. Using the Rydberg blockade, value of function may be determined in our scheme. According to the quantitative calculation of Rydberg blockade, we discuss the experimental feasibility of our scheme.
©2011 Optical Society of America
Quantum algorithm, which is made up of a fixed sequence of quantum logic gates, is applied in the process of quantum computation. Quantum algorithm uses some essential feature of quantum mechanics such as quantum superposition or quantum entanglement, so it can solve some problems those cannot be solved by classical algorithm, or it might be able to solve some problems faster than classical algorithm. The most well known algorithm includes Shor’s algorithm for factoring , Grover’s algorithm for searching an unstructured database or unordered list , and Deutsch-Jozsa algorithm for solving a black-box problem .
For Deutsch-Jozsa algorithm, a black box problem can be done with one query, but, for deterministic classical computers, one requires exponentially many queries to solve the black box problem. Taking the two-qubit Deutsch-Jozsa algorithm (Deutsch algorithm) as an example, we know quantum black box is designed to distinguish between the constant and balanced function on two qubits. The Deutsch question is: supposing is a function about variable x, where or 1 and its value of function for each input is either 0 or 1. If , is called the constant function; If , it is the balanced function. The Deutsch algorithm only needs one query to determine whether the is constant or balanced, that is, this algorithm can fast know the global property of the function . The experimental realization of Deutsch-Jozsa algorithm is firstly reported in the nuclear magnetic resonance system by two research groups [4,5]. Subsequently, some researchers realize Deutsch-Jozsa algorithm in ion trap and the linear optical system . With a single electronic spin in diamond  or QED technique , Deutsch-Jozsa algorithm is also investigated.
Neutral atom qubits are considered a very promising approach to a scalable quantum computer [9–16]. With neutral atoms using Rydberg blockade interactions, the demonstration of two-qubit controlled-NOT gate , preparation of two-particle or multiparticle entanglement [10,11], implementation of a multiqubit quantum phase gate , and an efficient quantum repeater architecture with mesoscopic atomic ensembles  are proposed in the latest results of research. In this Rydberg blockade effect, the first excited atom shifts the Rydberg levels of nearby atoms and prevents any further excitation of them, resulting in the production of singly excited collective states . Being an attractive system for quantum information processing, the Rydberg approach has its own advantages : it does not require cooling of the atoms to the ground state of the confining potentials, it can be operated on time scales due to the long lifetime of Rydberg atoms, it permits large interaction distance and does not require precise control of the interaction strength between two-atom, and it is easy to scale to multiqubit system.
In this paper, we consider the implementation of two-qubit Deutsch-Jozsa (D-J) algorithm via Rydberg blockade. D-J algorithm only determines the global property of function . For constant function, it includes two cases: and , and for balanced function, and , and and are included. D-J algorithm does not give the concrete value of the function . Next we want to ask what on earth the value of is. Besides the global property, the value of function is also important. In this paper, we propose a scheme where the value of function in D-J algorithm can be determined via Rydberg blockade.
2. Implementation of two-qubit Deutsch-Jozsa Algorithm
We consider two atoms are trapped by the confining potentials and two trapping regions might be separated by . Internal states of each atom can be expressed as , and , where , stand for qubit states, and is Rydberg state. Levels and transitions between levels are shown in Fig. 1 .
For D-J algorithm, we consider a quantum black box and it can perform a two-qubit transformation:18] , where is the Rabi frequency. Assuming the initial state of two atoms is in state , we choose , and for input qubit and auxiliary qubit, respectively, then , and . The state of two-atom can be expressed as
For the case , quantum black box does not perform any operations on input and auxiliary qubits, that is, .
If the values of and are equal to 1, state and Rydberg state of the auxiliary qubit are coupled by a laser beam with Rabi frequency . Choosing the (a pulse), the auxiliary atom undergoes an excitation and de-excitation, and a phase shift of π on the state , i.e. . Next we apply a π pulse to couple states and , and the auxiliary qubit undergoes the transformations and . The final state evolves asFig. 2 .
If the value of is 1 and , the level scheme and the sequence of operations for are shown in Fig. 3 . Here we apply the Rydberg blockade: for step 2, under the drive by laser, the state of the input atom is transferred from to Rydberg state . Due to the strong Rydberg interaction energy , the excitation between and Rydberg state is blocked. The interaction Hamiltonian  for two atoms can be expressed as , where considering the coupling between states and Rydberg state . For step 3, the dipole-dipole interaction shifts the Rydberg level so that it is blockade and . After the operation , the state can be expressed asFig. 3 are performed on the input and the auxiliary atoms. Finally, we re-perform a operation on the input qubit. The final state of two-atom system becomes
3. Determination of value of function
This is very indeed: the D-J algorithm has given us the ability to determine a global property of . However, D-J algorithm cannot give the concrete value of function . For example, means is the constant function. But either or is unknown to us. Now we propose a scheme in which the value of function may be determined.
In order to get the value of function , we need a two-atom entangled state10].
After the D-J algorithm is completed, let this entangled state Eq. (8) cross the quantum black box. For the constant function, if , two atoms are in the entangled state , i.e.Fig. 3 on the state . For the case , the state (expression (9)) evolves as , and for the case , the state (expression (10)) becomes . Then, performing a measurement on the auxiliary atom with basis . If the outcome of measurement is , is equal to 1; If the outcome shows , is equal to 0. For the constant function, we have determined the value of function .
For the balanced function, the entangled state Eq. (8) is sent into quantum black box. For the case and , the entangled state undergoes unitary operation , and becomes . For the case and , unitary operation is applied on the entangled state, and we obtain . Next, single particle measurement is performed on the auxiliary atom in basis , which is sufficient to determine whether the values of function are and or and .
Our scheme can be extended to multi-qubit system. Here, we consider the three-qubit Deutsch-Jozsa question. The state of two input qubits and an auxiliary qubit can be expressed as
For constant function, outcomes of measurement are , corresponding values of are , or
For balanced function, measurements include three different outcomes. If outcomes of measurement are , values of are , or
If outcomes of measurement are , values of are , or ,
If outcomes are , values of are , or
Next we send three-particle entangled state into black box again. For case , we obtain(12), we know Eqs. (12a) and (12b) are mutually orthogonal, Eqs. (12c) and (12d) are mutually orthogonal, Eqs. (12e) and (12f) are mutually orthogonal, and Eqs. (12g) and (12h) are also mutually orthogonal, so we can distinguish these quantum states, that is, another measurement can determine the value of . Summing up the above process, we find we need two queries to evaluate the function. In the classical case, three queries () are required. Our method is faster than the classical one.
In the process of two-qubit D-J algorithm, single qubit gates and a two-qubit controlled-NOT gate are proposed via Rydberg blockade. Based on a complete set of universal gates, the three-atom D-J algorithm and extraction of the values of might be realizable.
Applying the Rydberg blockade, we have proposed a scheme for implementing two-qubit Deutsch-Jozsa algorithm. According to the D-J algorithm, we can learn the global property of function . In our scheme, the entangled state of two atoms is sent into quantum black box and undergoes appropriate unitary operations. Finally, the value of function can be completely determined. As far as we know, this result of study is first reported.
Based on the experimental developments of Rydberg blockade in quantum information, we discuss the experimental feasibility of our scheme. Our scheme can be implemented using cold 87Rb atom. Rydberg blockade between two rubidium atoms localized in spatially separated trapping sites has been observed . A controlled-NOT gate between two individually addressed rubidium atoms has been realized . In addition, Rabi oscillation between ground and Rydberg states with dipole-dipole interaction can be effectively controlled , which can help us perform single qubit operation. In our scheme, sequential unitary operations made up of single qubit and two-qubit gates are based on latest experiments of Rydberg blockade. According to the theory of excitation dynamics in a two-atom system driven by external laser field , the interaction Hamiltonian is expressed as . Through solving the equation of evolution of the system, we can calculate the probability of double excitation (i.e. the state are simultaneously populated by two atoms.). When the Rydberg-Rydberg interaction is weak (see dashed curve in Fig. 4 ), population of double Rydberg level is large. The population of the doubly excited state decreases with increase of Rydberg-Rydberg interaction, that is, the double excitation is blocked (see dotted curve in Fig. 4). A complete set of universal gates, which can be comprised of single qubit gates together with a two-qubit controlled-NOT gate, are constructed via Rydberg blockade. Based on the latest experiments and the quantitative calculation of Rydberg blockade, the proposed scheme might be realizable.
We thank Swinburne theoretical physics group for useful discussions. Financial support by the National Natural Science Foundation of China under Grant No. 11065007 and the Foundation of Talent of Jinggang of Jiangxi Province, China, Grant No. 2008DQ00400, is acknowledged.
References and links
1. P. W. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” SIAM J. Comput. 26(5), 1484–1509 (1997). [CrossRef]
2. L. K. Grover, “Quantum Computers Can Search Rapidly by Using Almost Any Transformation,” Phys. Rev. Lett. 80(19), 4329–4332 (1998). [CrossRef]
3. D. Deutsch and R. Jozsa, “Rapid solution of problems by quantum computation,” Proc. R. Soc. Lond. A 439(1907), 553–558 (1992). [CrossRef]
4. I. L. Chuang, I. M. K. Vandersypen, X. Zhou, D. W. Leung, and S. Lloyd, “Experimental realization of a quantum algorithm,” Nature 393(6681), 143–146 (1998). [CrossRef]
5. J. A. Jones and M. Mosca, “Implementation of a quantum algorithm on a nuclear magnetic resonance quantum computer,” J. Chem. Phys. 109(5), 1648–1653 (1998). [CrossRef]
6. M. Mohseni, J. S. Lundeen, K. J. Resch, and A. M. Steinberg, “Experimental application of decoherence-free subspaces in an optical quantum-computing algorithm,” Phys. Rev. Lett. 91(18), 187903 (2003). [CrossRef] [PubMed]
7. F. Shi, X. Rong, N. Xu, Y. Wang, J. Wu, B. Chong, X. Peng, J. Kniepert, R. S. Schoenfeld, W. Harneit, M. Feng, and J. Du, “Room-temperature implementation of the Deutsch-Jozsa algorithm with a single electronic spin in diamond,” Phys. Rev. Lett. 105(4), 040504 (2010). [CrossRef] [PubMed]
8. S.-B. Zheng, “Scheme for implementing the Deutsch-Jozsa algorithm in cavity QED,” Phys. Rev. A 70(3), 034301 (2004). [CrossRef]
9. L. Isenhower, E. Urban, X. L. Zhang, A. T. Gill, T. Henage, T. A. Johnson, T. G. Walker, and M. Saffman, “Demonstration of a neutral atom controlled-NOT quantum gate,” Phys. Rev. Lett. 104(1), 010503 (2010). [CrossRef] [PubMed]
10. T. Wilk, A. Gaëtan, C. Evellin, J. Wolters, Y. Miroshnychenko, P. Grangier, and A. Browaeys, “Entanglement of two individual neutral atoms using Rydberg blockade,” Phys. Rev. Lett. 104(1), 010502 (2010). [CrossRef] [PubMed]
12. H.-Z. Wu, Z.-B. Yang, and S.-B. Zheng, “Implementation of a multiqubit quantum phase gate in a neutral atomic ensemble via the asymmetric Rydberg blockade,” Phys. Rev. A 82(3), 034307 (2010). [CrossRef]
13. B. Zhao, M. Müller, K. Hammerer, and P. Zoller, “Efficient quantum repeater based on deterministic Rydberg gates,” Phys. Rev. Lett. 81, 052329 (2010).
15. M. Müller, I. Lesanovsky, H. Weimer, H. P. Büchler, and P. Zoller, “Mesoscopic Rydberg gate based on electromagnetically induced transparency,” Phys. Rev. Lett. 102(17), 170502 (2009). [CrossRef] [PubMed]
16. Y. Wu, M. G. Payne, E. W. Hagley, and L. Deng, “Preparation of multiparty entangled states using pairwise perfectly efficient single-probe photon four-wave mixing,” Phys. Rev. A 69(6), 063803 (2004). [CrossRef]
17. E. Urban, T. A. Johnson, T. Henage, L. Isenhower, D. D. Yavuz, T. G. Walker, and M. Saffman, “Observation of Rydberg blockade between two atoms,” Nat. Phys. 5(2), 110–114 (2009). [CrossRef]
18. M. O. Scully, and M. S. Zubairy, Quantum Optics (Cambridge: Cambridge University Press,1997), Chap.5.
19. C. Ates, T. Pohl, T. Pattard, and J. M. Rost, “Many-body theory of excitation dynamics in an ultracold Rydberg gas,” Phys. Rev. A 76(1), 013413 (2007). [CrossRef]
20. T. A. Johnson, E. Urban, T. Henage, L. Isenhower, D. D. Yavuz, T. G. Walker, and M. Saffman, “Rabi oscillations between ground and Rydberg states with dipole-dipole atomic interactions,” Phys. Rev. Lett. 100(11), 113003 (2008). [CrossRef] [PubMed]