Quantum Walk on the Line
By Ashwin Nayak, Ashvin Vishwanath. 2000
173 citations recorded by the source corpus.
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/ √ 2 , t/ √ 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.
View Paper: https://www.semanticscholar.org/paper/0377be9ee303418ef1420960a76e4cc55c6f7dc8
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
- Miklos Santha
- Salvador Elías Venegas-Andraca
- Andrew M. Childs
- Frédéric Magniez
- Andris Ambainis
- Ashwin Nayak
- Julia Kempe
- Jérémie Roland
Citations in the corpus
- Quantum random walks: An introductory overview (2003, background): “puter simulation of the Hadamard walk with a symmetric initial condition [15].”
- Quantum walks driven by many coins (2002, methodology): “We can now use the tensor-product structure of the evolution matrix and the integral simplifications in [6] to simplify the integrals for aR and aL.”
- Search via quantum walk (2006, background): “Afterwards notions related to quantum walks, such as mixing time, and deviation from starting state, were studied for restricted graphs by several researchers [22, 7, 3, 23], suggesting the possibility of speedup of classical algorithms based on random walk.”
- Quantum Walk Based Search Algorithms (2008, background): “Different parameters related to quantum walks and possible speedups of classical algorithms were investigated by several researchers [30, 8, 3, 29, 19, 32].”
- A new type of limit theorems for the one-dimensional quantum random walk (2002, background): “When ϕ = t[0, 1] (θ = 0), Nayak and Vishwanath [9] and Ambainis et al. [1] gave a similar result, but both papers did not treat weak convergence.”