Quantum Walk on the Line

2000/10/31 by Ashwin Nayak, Ashvin Vishwanath, Nayak, Ashwin +1 · 2 citations
Computer Science · Physics and Astronomy · #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #quant-ph

paper · pdf · doi:10.48550/arxiv.quant-ph/0010117

20 pages, 5 figures

arxiv created 2000/10/31 · arxiv updated 2009/12/01

Abstract

Motivated by the immense success of random walk and Markov chain methods in the design of classical algorithms, we consider_quantum_ walks on graphs. We analyse in detail the behaviour of unbiased quantum walk on the line, with the example of a typical walk, the ``Hadamard walk''. We show that after t time steps, the probability distribution on the line induced by the Hadamard walk is almost uniformly distributed over the interval [-t/sqrt(2),t/sqrt(2)]. This implies that the same walk defined on the circle mixes in_linear_ time. This is in direct contrast with the quadratic mixing time for the corresponding classical walk. We conclude by indicating how our techniques may be applied to more general graphs.

Cited by

• A Probabilistic Representation for Multi-State Discrete-time Quantum Walks
• Classification of coined quantum walks on the line and comparison to correlated classical random walks

Related

• An example of the difference between quantum and classical random walks
• Quantum Walks can Unitarily Represent Random Walks on Finite Graphs
• Quantum walks, the discrete wave equation and Chebyshev polynomials
• Selected Open Problems in Continuous-Time Quantum Walks
• Quantum Walks on the Hypercube