NIST Home page
Realization of a quantum random walk with ultracold atoms

D. Ciampini, M.B. d’Arcy, J.M. Grossman, K. Helmerson, P.D. Lett, W.D. Phillips, A. Vaziri

Laser Cooling & Trapping Group, National Institute of Standards & Technology, Atomic Physics Division, Physics Laboratory

S.L. Rolston

Department of Physics, University of Maryland, College Park MD

Classical random walks have many applications in computer science. Quantum random walks (QRWs) [1] have been suggested as the potential basis for quantum computing algorithms. Such algorithms have been reported, some of which offer an exponential speed-up over the best classical algorithms [2,3]. Studying QRWs experimentally, therefore, can give insight that may aid in systematically developing quantum computing algorithms with practical applications.

We implement a discrete quantum random walk of atoms on a line. The classical random walk analog of this QRW is Galton’s pegboard, also known as the quincunx [4]. In the classical version, a particle begins at the origin of a one-dimensional lattice. At each time step the particle has equal probability of moving one lattice site to the left or right. After N steps the probability distribution of the particle’s location is given by a binomial distribution, which approaches a Gaussian in the limit of many steps.

In the classical random walk on a line, the standard deviation of the probability distribution grows as the square root of N. For the quantum random walk, however, the probability distribution spreads linearly with the number of steps. Classically, in the limit of large N the probability distribution falls off exponentially away from the mean position, while in the quantum case the probability away from the maximum is only suppressed as 1/N. These differences account for the computing speed-up of algorithms using quantum random walks [2,3].

Our implementation of the quantum random walk on a line uses atoms diffracted from a sodium Bose-Einstein condensate. We release the condensate from a magnetic trap and allow it to expand to reduce the mean-field interactions. We then apply pulsed counterpropagating beams at regular time intervals. These pulses satisfy the conditions for p/2-Bragg pulses, coupling atoms between zero-recoil and two-recoil momentum states, with each pulse leaving each atom in an equal superposition of these two momentum states [5]. Between pulses the atoms evolve so that the populations in the two momentum states separate by about one cloud diameter. The final population distribution after many pulses differs dramatically from the classical analog, providing another clear demonstration of the dichotomy between quantum and classical dynamics.

These QRW experiments also facilitate the investigation of the effect of decoherence, which would tend to produce the classical distribution. Dephasing, which mimics decoherence, is introduced by a random change in the phase of the light potential applied in each pulse. Mean-field interactions can also reduce the quantum signatures of the probability distribution.

References

1. J. Kempe, "Quantom random walks?an introductory overview," Contemp. Phys 44, 307 (2003).
2. A.M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D.A. Spielman, "Exponential algorithmic speedup by quantum walk," e-print quant-ph/0209131.
3. N. Shenvi, J. Kempe, and K.B. Whaley, "A quantum random walk search algorithm," e-print quant-ph/0210064.
4. F. Galton, Natural Inheritance (Macmillan, London, 1894).
5. M. Kozuma, L. Deng, E.W. Hagley, J. Wen, R. Lutwak, K. Helmerson, S.L. Rolston, and W.D. Phillips, "Coherent splitting of Bose-Einstein condensed atoms with optically induced Bragg diffraction," Phys. Rev. Lett. 82, 871 (1999).

Authors:

Postdocs:

Donatella Ciampini

Atomic Physics Division, Physics Laboratory

Rm A159, Bldg 221

Stop 8424

Phone: x6583

Fax: x8272

Email: Donatella.ciampini@nist.gov

Sigma Xi member: No

Michael d’Arcy

Atomic Physics Division, Physics Laboratory

Rm A151, Bldg 221

Stop 8424

Phone: x4360

Fax: x8272

Email: Michael.dArcy@nist.gov

Sigma Xi member: No

Joshua Grossman

Atomic Physics Division, Physics Laboratory

Rm A165, Bldg 221

Stop 8424

Phone: x8571

Fax: x8272

Email: Joshua.Grossman@nist.gov

Sigma Xi member: No

Alipasha Vaziri

Atomic Physics Division, Physics Laboratory

Rm A159, Bldg 221

Stop 8424

Phone: x2353

Fax: x8272

Email: Ali.Vaziri@nist.gov

Sigma Xi member: No
 
 

Category:

Physics