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
> π/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]{.underline}**:

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](mailto:Michael.dArcy@nist.gov)

Sigma Xi member: No

Category:

Physics