A Caltech Library Service

One-dimensional quantum walks

Ambainis, Andris and Bach, Eric and Nayak, Ashwin and Vishwanath, Ashvin and Watrous, John (2001) One-dimensional quantum walks. In: Proceedings of the thirty-third annual ACM symposium on Theory of computing (STOC '01). ACM , New York, NY, pp. 37-49. ISBN 1-58113-349-9.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Nayak, Ashwin0000-0002-3924-0875
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.
Funding AgencyGrant Number
NSFCCR 9800024
Charles Lee Powell FoundationUNSPECIFIED
NSFCCR 98761722
Institute for Quantum InformationUNSPECIFIED
NSFSTC 91-19999
NSFCCR 99-06105
NSFEIA 00-80234
Natural Sciences and Engineering Research Council of Canada (NSERC)UNSPECIFIED
Record Number:CaltechAUTHORS:20160419-111958294
Persistent URL:
Official Citation:Andris Ambainis, Eric Bach, Ashwin Nayak, Ashvin Vishwanath, and John Watrous. 2001. One-dimensional quantum walks. In Proceedings of the thirty-third annual ACM symposium on Theory of computing (STOC '01). ACM, New York, NY, USA, 37-49. DOI=
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:66275
Deposited By: Kristin Buxton
Deposited On:19 Apr 2016 20:22
Last Modified:09 Mar 2020 13:19

Repository Staff Only: item control page