Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published 2001 | public
Book Section - Chapter

One-dimensional quantum walks

Abstract

We define and analyze quantum computational variants of random walks on one-dimensional lattices. In particular, we analyze a quantum analog of the symmetric random walk, which we call the Hadamard walk. Several striking differences between the quantum and classical cases are ob- served. For example, when unrestricted in either direction, the Hadamard walk has position that is nearly uniformly distributed in the range [-t/√2, t/√2] after t steps, which is in sharp contrast to the classical random walk, which has distance O(√t) from the origin with high probability. With an absorbing boundary immediately to the left of the starting position, the probability that the walk exits to the left is 2/π, and with an additional absorbing boundary at location n, the probability that the walk exits to the left actually increases, approaching 1/√2 in the limit. In the classical case both values are 1.

Additional Information

© 2001 ACM. Supported by Microsoft Graduate Fellowship and NSF Grant CCR 9800024. Part of this work done while visiting Aspen Center for Physics. Supported by NSF Grant CCR-9988202. Supported by Charles Lee Powell Foundation, NSF grant CCR 98761722, and Institute for Quantum Information. This work was done while the author was at DIMACS and AT&T Labs, supported by NSF grants STC 91-19999, CCR 99-06105 and EIA 00-80234. Supported by Canada's NSERC. A.A. thanks Isaac Chuang for suggesting to study the two- way infinite timed quantum walk and Dorit Aharonov and Julia Kempe for useful discussions. A.N. and A.V. thank Mike Saks for discussions on the asymptotic behavior of integrals and for directing us to [4]. E.B. thanks Richard Askey for pointing us toward [7] and Mourad Ismail for sharing corrections to it.

Additional details

Created:
August 19, 2023
Modified:
October 18, 2023