## Abstract

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 OSA

## 1. Introduction

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 [1], Grover’s algorithm for searching an unstructured database or unordered list [2], and Deutsch-Jozsa algorithm for solving a black-box problem [3].

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 $f(x)$ is a function about variable *x*, where $x=0$ or 1 and its value of function for each input is either 0 or 1. If $f(0)=f(1)$, $f(x)$ is called the constant function; If $f(0)\ne f(1)$, it is the balanced function. The Deutsch algorithm only needs one query to determine whether the $f(x)$ is constant or balanced, that is, this algorithm can fast know the global property of the function $f(x)$. 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 [6]. With a single electronic spin in diamond [7] or QED technique [8], 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 [9], preparation of two-particle or multiparticle entanglement [10,11], implementation of a multiqubit quantum phase gate [12], and an efficient quantum repeater architecture with mesoscopic atomic ensembles [13] 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 [17]. Being an attractive system for quantum information processing, the Rydberg approach has its own advantages [9]: it does not require cooling of the atoms to the ground state of the confining potentials, it can be operated on $\mu s$ 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 $f(x)$. For constant function, it includes two cases: $f(0)=f(1)=0$ and $f(0)=f(1)=1$, and for balanced function, $f(0)=0$ and $f(1)=1$, and $f(0)=1$ and$f(1)=0$ are included. D-J algorithm does not give the concrete value of the function $f(x)$. Next we want to ask what on earth the value of $f(x)$ 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 $z=10\mu m$ [17]. Internal states of each atom can be expressed as $|0\u3009$, $|1\u3009$ and $|r\u3009$, where $|0\u3009$, $|1\u3009$ stand for qubit states, and $|r\u3009$ 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:

where $x,\text{}y\in \{0,1\}$, ⊕ is addition modulo two, and*i*and

*a*stand for an input query qubit and an auxiliary qubit, respectively. Considering the transition between internal levels $|0\u3009$ and $|1\u3009$, in the rotating-wave approximation, the evolution of each atom is described by the interaction Hamiltonian [18] $H=-\frac{\hslash {\Omega}_{R}}{2}(|1\u3009\u30080|+|0\u3009\u30081|)$, where ${\Omega}_{R}$ is the Rabi frequency. Assuming the initial state of two atoms is in state $|0\u3009$, we choose ${\Omega}_{R}t=\pi /2$, and ${\Omega}_{R}t=3\pi /2$ for input qubit and auxiliary qubit, respectively, then ${|0\u3009}_{i}\to \frac{1}{\sqrt{2}}({|0\u3009}_{i}+{|1\u3009}_{i})$, and ${|0\u3009}_{a}\to \frac{1}{\sqrt{2}}({|0\u3009}_{a}-{|1\u3009}_{a})$. The state of two-atom can be expressed asWe send this state into a quantum black box. According to the value of function $f(x)$, the quantum black box performs four different kinds of operations ${U}_{fj}$ ($j=1,2,3,4)$, where ${U}_{f1}$ corresponding to $f(0)=f(1)=0$, ${U}_{f2}$ corresponding to $f(0)=f(1)=1$, ${U}_{f3}$ corresponding to $f(0)=1\text{and}f(1)=0$, and ${U}_{f4}$ corresponding to $f(0)=0\text{and}f(1)=1$. After the operations ${U}_{fj}$are performed, the state ${|\Psi \u3009}_{1}$ becomes

For the case $f(0)=f(1)=0$, quantum black box does not perform any operations on input and auxiliary qubits, that is, ${U}_{f1}={I}_{i}\otimes {I}_{a}$.

If the values of $f(0)$ and $f(1)$ are equal to 1, state ${|1\u3009}_{a}$ and Rydberg state ${|r\u3009}_{a}$ of the auxiliary qubit are coupled by a laser beam with Rabi frequency ${\Omega}_{R}$. Choosing the ${\Omega}_{R}t=2\pi $ (a $2\pi $ pulse), the auxiliary atom undergoes an excitation and de-excitation, and a phase shift of *π* on the state ${|1\u3009}_{a}$, i.e. ${|1\u3009}_{a}\to -{|1\u3009}_{a}$. Next we apply a *π* pulse to couple states ${|0\u3009}_{a}$ and ${|1\u3009}_{a}$, and the auxiliary qubit undergoes the transformations ${|0\u3009}_{a}\to {|1\u3009}_{a}$ and ${|1\u3009}_{a}\to -{|0\u3009}_{a}$. The final state evolves as

If the value of $f(0)$ is 1 and $f(1)=0$, the level scheme and the sequence of operations for ${U}_{f3}$ 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 ${|1\u3009}_{i}$ to Rydberg state ${|r\u3009}_{i}$. Due to the strong Rydberg interaction energy ${\Delta}_{rr}{|r\u3009}_{i}{|r\u3009}_{aa}{\u3008r|}_{i}\u3008r|$, the excitation between ${|1\u3009}_{a}$ and Rydberg state ${|r\u3009}_{a}$ is blocked. The interaction Hamiltonian [19] for two atoms can be expressed as $H=\hslash {\Delta}_{rr}{|r\u3009}_{i}{|r\u3009}_{aa}{\u3008r|}_{i}\u3008r|+\frac{\hslash {\Omega}_{R}}{2}({|r\u3009}_{aa}\u30081|+{|r\u3009}_{ii}\u30081|+h.c.)$, where considering the coupling between states ${|1\u3009}_{a}$ and Rydberg state ${|r\u3009}_{a}$. For step 3, the dipole-dipole interaction ${|r\u3009}_{i}\leftrightarrow {|r\u3009}_{a}$ shifts the Rydberg level ${|r\u3009}_{a}$ so that it is blockade and ${|1\u3009}_{a}\stackrel{2\pi}{\to}{|1\u3009}_{a}$. After the operation ${U}_{f3}$, the state ${|\Psi \u3009}_{1}$ can be expressed as

*π*pulse leads to ${|0\u3009}_{i}\to {|1\u3009}_{i}$ and ${|1\u3009}_{i}\to -{|0\u3009}_{i}$. Next, sequential operations shown in Fig. 3 are performed on the input and the auxiliary atoms. Finally, we re-perform a ${\sigma}_{x}$ 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 $f(x)$. However, D-J algorithm cannot give the concrete value of function $f(x)$. For example, $f(0)=f(1)$ means $f(x)$ is the constant function. But either $f(0)=f(1)=0$ or $f(0)=f(1)=1$ 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 $f(x)$, we need a two-atom entangled state

After the D-J algorithm is completed, let this entangled state Eq. (8) cross the quantum black box. For the constant function, if $f(0)=f(1)=0$, two atoms are in the entangled state ${|\Psi \u3009}_{ia}^{1}$, i.e.

If $f(0)=f(1)=1$, the state of two-atom undergoes the unitary operation ${U}_{f2}$, and evolves asFor the balanced function, the entangled state Eq. (8) is sent into quantum black box. For the case $f(0)=1$ and $f(1)=0$, the entangled state ${|\Psi \u3009}_{ia}^{1}$ undergoes unitary operation ${U}_{f3}$, and becomes $\frac{1}{\sqrt{2}}({|0\u3009}_{i}+{|1\u3009}_{i}){|1\u3009}_{a}$. For the case $f(0)=0$ and $f(1)=1$, unitary operation ${U}_{f4}$ is applied on the entangled state, and we obtain $\frac{1}{\sqrt{2}}({|0\u3009}_{i}+{|1\u3009}_{i}){|0\u3009}_{a}$. Next, single particle measurement is performed on the auxiliary atom in basis $\{{|0\u3009}_{a},{|1\u3009}_{a}\}$, which is sufficient to determine whether the values of function $f(x)$ are $f(0)=0$ and $f(1)=1$ or $f(0)=1$ and $f(1)=0$.

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 ${|0\u3009}_{{i}_{1}}{|0\u3009}_{{i}_{2}}$, corresponding values of $f(x)$ are $f(00)=f(01)=f(10)=f(11)=0$, or $f(00)=f(01)=f(10)=f(11)=1.$

For balanced function, measurements include three different outcomes. If outcomes of measurement are ${|0\u3009}_{{i}_{1}}{|1\u3009}_{{i}_{2}}$, values of $f(x)$ are $f(00)=f(10)=1,$ $f(01)=f(11)=0$, or $f(00)=f(10)=0,$ $f(01)=f(11)=1.$

If outcomes of measurement are ${|1\u3009}_{{i}_{1}}{|0\u3009}_{{i}_{2}}$, values of $f(x)$ are $f(00)=f(01)=0,$ $f(10)=f(11)=1$, or $f(00)=f(01)=1$, $f(10)=f(11)=0.$

If outcomes are ${|1\u3009}_{{i}_{1}}{|1\u3009}_{{i}_{2}}$, values of $f(x)$ are $f(00)=f(11)=0,$ $f(01)=f(10)=1$, or $f(00)=f(11)=1,$ $f(01)=f(10)=0.$

Next we send three-particle entangled state $\frac{1}{\sqrt{2}}({|0\u3009}_{{i}_{1}}{|0\u3009}_{{i}_{2}}{|0\u3009}_{a}+{|1\u3009}_{{i}_{1}}{|1\u3009}_{{i}_{2}}{|1\u3009}_{a})$ into black box again. For case $f(00)=f(01)=f(10)=f(11)=0$, we obtain

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 $f(x)$ might be realizable.

## 4. Conclusion

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 $f(x)$. 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 ^{87}Rb atom. Rydberg blockade between two rubidium atoms localized in spatially separated trapping sites has been observed [17]. A controlled-NOT gate between two individually addressed rubidium atoms has been realized [9]. In addition, Rabi oscillation between ground and Rydberg states with dipole-dipole interaction can be effectively controlled [20], 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 [19], the interaction Hamiltonian is expressed as $H=\hslash {\Delta}_{rr}{|r\u3009}_{i}{|r\u3009}_{aa}{\u3008r|}_{i}\u3008r|+\frac{\hslash {\Omega}_{R}}{2}({|r\u3009}_{aa}\u30081|+{|r\u3009}_{ii}\u30081|+h.c.)$. Through solving the equation of evolution of the system, we can calculate the probability of double excitation (i.e. the state $|r\u3009$ are simultaneously populated by two atoms.). When the Rydberg-Rydberg interaction is weak (see dashed curve in Fig. 4
), population of double Rydberg level ${|r\u3009}_{i}{|r\u3009}_{a}$ is large. The population of the doubly excited state ${|r\u3009}_{i}{|r\u3009}_{a}$ 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.

## Acknowledgments

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]

**11. **M. Saffman and K. Mølmer, “Efficient multiparticle entanglement via asymmetric Rydberg blockade,” Phys. Rev. Lett. **102**(24), 240502 (2009). [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).

**14. **D. Jaksch, J. I. Cirac, P. Zoller, S. L. Rolston, R. Côté, and M. D. Lukin, “Fast quantum gates for neutral atoms,” Phys. Rev. Lett. **85**(10), 2208–2211 (2000). [CrossRef] [PubMed]

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