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