## Abstract

The quantum walk is the quantum analog of the well-known random walk, which forms the basis for models and applications in many realms of science. Its properties are markedly different from the classical counterpart and might lead to extensive applications in quantum information science. In our experiment, we implemented a quantum walk on the line with single neutral atoms by deterministically delocalizing them over the sites of a one-dimensional spin-dependent optical lattice. With the use of site-resolved fluorescence imaging, the final wave function is characterized by local quantum state tomography, and its spatial coherence is demonstrated. Our system allows the observation of the quantum-to-classical transition and paves the way for applications, such as quantum cellular automata.

Interference phenomena with microscopic particles are a direct consequence of their quantum-mechanical wave nature (*1*–*5*). The prospect to fully control quantum properties of atomic systems has stimulated ideas to engineer quantum states that would be useful for applications in quantum information processing, for example, and also would elucidate fundamental questions, such as the quantum-to-classical transition (*6*). A prominent example of state engineering by controlled multipath interference is the quantum walk of a particle (*7*). Its classical counterpart, the random walk, is relevant in many aspects of our lives, providing insight into diverse fields: It forms the basis for algorithms (*8*), describes diffusion processes in physics or biology (*8*, *9*), such as Brownian motion, or has been used as a model for stock market prices (*10*). Similarly, the quantum walk is expected to have implications for various fields, for instance, as a primitive for universal quantum computing (*11*), systematic quantum algorithm engineering (*12*), or for deepening our understanding of the efficient energy transfer in biomolecules for photosynthesis (*13*).

Quantum walks have been proposed to be observable in several physical systems (*12*, *14*, *15*). Special realizations have been reported in either the populations of nuclear magnetic resonance samples (*16*, *17*) or in optical systems, in either frequency space of a linear optical resonator (*18*), with beam splitters (*19*), or in the continuous tunneling of light fields through waveguide lattices (*20*). Recently, a three-step quantum walk in the phase space of trapped ions has been observed (*21*). However, the coherent walk of an individual quantum particle with controllable internal states, as originally proposed by Feynman (*22*), has so far not been observed. We present the experimental realization of such a single quantum particle walking in a one-dimensional (1D) lattice in position space. This basic example of a walk provides all of the relevant features necessary to understand the fundamental properties and differences of the quantum and classical regimes. For example, the atomic wave function resulting from a quantum walk exhibits delocalized coherence, which reflects the underlying quantum interference. Simultaneous detection of internal state and the atomic position in the lattice by an optical microscope allows for local quantum state tomography of the wave function. This is an important requirement to realize applications in quantum information science, such as the quantum cellular automaton (*23*–*25*).

In the classical random walk on a line, a coin is tossed in each time step. Depending on the outcome (heads or tails), a walker takes one step to the left or to the right. After *N* time steps, the probability of finding the walker at a certain site on the line follows a binomial distribution with a width increasing proportional to

In the quantum case, the walker can be brought in a coherent superposition of going to the right or left. This can be realized by adding internal states to the walker, providing an additional degree of freedom, which can be used to control the system. We consider a two-level particle with internal states |0〉 and |1〉. In every step of the walk, the coin operator brings each internal state into a coherent superposition of the two states. The essence of the general quantum walk is to entangle this internal state with the position of the corresponding wave packet by a state-dependent transport. This can be realized by shifting both internal states into opposite directions, which coherently delocalizes the particle over two lattice sites. Repetition of the unitary coin-shift operation sequence results in the so-called quantum walk. After two steps of the quantum walk, two parts of the wave function are re-combined at a common lattice site. Being in different internal states, they cannot interfere. The next coin operator, however, mixes the internal states in a deterministic way, which gives rise to quantum interference of the two overlapping wave packets. Further steps result in a multipath interference (Fig. 1A), which then alters the properties of the quantum walk as compared with the classical random walk. In particular, the width of the probability distribution to find the walker at a certain position scales proportional to *N* for the quantum walk, as in a ballistic transport, in contrast to the diffusive

We realize a quantum walk with single laser-cooled cesium (Cs) atoms, trapped in the potential wells of a 1D optical lattice (*12*) with site separation of λ/2 = 433 nm (here, λ is the wavelength of the lattice laser light). The atoms are thermal with a mean energy of *k*_{B} × 10 μK, whereas the optical potential depth is *k*_{B} × 80 μK (here, *k*_{B} is the Boltzmann constant). They are distributed among the axial vibrational states with a mean occupation number of *F* = 4, *m*_{F} = 4〉 hyperfine state by optical pumping, where *F* is the total angular momentum, and *m*_{F} its projection onto the quantization axis along the dipole trap axis. Resonant microwave radiation around 9.2 GHz coherently couples this state to the |1〉 ≡ |*F* = 3, *m*_{F} = 3〉 state. A π/2 pulse of 4 μs initializes the system in the superposition (|0〉 + *i*|1〉)/*26*). After *N* steps of coin operation and state-dependent shift, the final atom distribution is probed by fluorescence imaging. From these images, the exact lattice site of the atom after the walk is extracted (*27*) and compared to the initial position of the atom. Spin echo operations are combined with each coin operation (*26*), leading to a coherence time of 0.8 ms.

The final probability distribution *P _{N}*(ξ) to find an atom at position ξ after

*N*steps (Fig. 1) is obtained from the distance each atom has walked by taking the ensemble average over several hundreds of identical realizations of the sequence. Ideally, one expects a double-peak distribution with large amplitude close to the edges of the distribution (

*7*). The relative heights of the left and right peaks—and therefore the symmetry—depend on the choice of the initial state. Decoherence gradually suppresses the pronounced peaks (

*12*,

*28*). We compare the measured distributions for the symmetric and asymmetric quantum walks of

*N*= 6 steps (Fig. 1, D and E) with the theoretical expectations for the ideal case and find good agreement.

In contrast, a random walk distribution can be recovered by introducing decoherence after each step of the walk. Omitting the spin-echo from the coin operation and additionally waiting 400 μs between coin and subsequent shift operation destroys the phase relation between subsequent steps of the walk. The resulting probability distribution is described by a binomial distribution (Fig. 1G), as expected for a purely classical random walk.

The scaling of the width of the quantum and the random walk distribution with the number of steps is one of the most prominent distinguishing features. We have investigated this scaling behavior for both walks for up to *N* = 24 steps (Fig. 2). For the quantum walk, the width follows closely the expected linear behavior for up to 10 steps. The subsequent deviation is due to decoherence (*26*), which asymptotically turns the quantum walk into a classical random walk. In contrast, for the random walk, the typical square-root scaling is recovered.

To get a more detailed characterization of the wave function prepared by a six-step quantum walk sequence, we extract information on the internal state populations and relative phase by local quantum state tomography. This is based on site-resolved, state-selective detection combined with single-particle operations (*26*, *29*), providing a population distribution for each eigenstate of the Pauli spin operators

The local tomography, however, does not yield information about the off-diagonal elements of the position space density matrix, which essentially contain information about the phase relation between the wave function at different lattice sites rather than at each site. To demonstrate the spatial coherence of the state over all populated lattice sites, we invert the coin operation *C*^{–1}: {|0〉 → (|0〉 + |1〉)/

We have studied the quantum walk of single neutral atoms in an optical lattice and characterized the quantum state of the delocalized atom. We have found good agreement with the ideal case of a quantum walk for up to 10 steps. Inversion of the walk causes the delocalized wave function to refocus to the initial lattice site. Although the atoms in our experiments are thermally distributed among several vibrational states, we obtain large coherence over a macroscopic distance. In the ideal case, motional state and internal states factorize so that the coherence created in one degree of freedom is not affected by the other. We have found that, as soon as internal and external degrees of freedom are coupled by diabatic transport leading to vibrational excitations, for instance, the matter wave interference is quickly suppressed.

It will be interesting to investigate the behavior of quantum walks for different conditions when coin operations depend on position or time. In particular, monitoring the decay of coherence under the influence of different noise sources will further elucidate the transition from the quantum to the classical regime. Performing the quantum walk with more than one atom and enabling coherent interactions between the atoms (*30*) will realize first operational quantum cellular automata that can be probed by full quantum state tomography, opening another experimental route toward quantum information science.

## References and Notes

- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
- ↵
See the supporting material on

*Science*Online. - ↵
- ↵
- ↵
- ↵
- We thank D. Döring, F. Grenz, and A. Härter for help in the construction of the apparatus and A. Rauschenbeutel for valuable discussions. We acknowledge financial support from the Deutsche Forschungsgemeinschaft (research unit 635) and European Commission (Integrated Project on Scalable Quantum Computing with Light and Atoms). M.K. acknowledges support from the Studienstiftung des deutschen Volkes, and J.-M.C. received partial support from the Korea Research Foundation grant funded by the Korean Government (Ministry of Education and Human Resources Development).