An Example of the Difference Between Quantum and Classical Random Walks

By Andrew M. Childs, Edward Farhi, Sam Gutmann. Quantum Information Processing, 2001

428 citations recorded by the source corpus.

AbstractIn this note, we discuss a general definition of quantum random walks on graphs and illustrate with a simple graph the possibility of very different behavior between a classical random walk and its quantum analog. In this graph, propagation between a particular pair of nodes is exponentially faster in the quantum case. PACS: 03.67.Hk

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/8bfc72bc7b33ef9d081d5f206d95d398c00556f5

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

A new type of limit theorems for the one-dimensional quantum random walk (2002, background): “Very recently quantum random walks have been widely investigated by a number of groups in connection with the quantum computing, for exmples, [1, 3 , 4, 5, 6, 8, 9, 13, 14].”
Coins make quantum walks faster (2004, background): “This means that one variant of quantum walks could be more powerful than the other in some context, but so far all known examples have given similar behavior of the two walks (see e.g. [ CFG02 , Kem03b, CCD+03]).”
QUANTUM WALKS AND THEIR ALGORITHMIC APPLICATIONS (2003, methodology): “To summarize, classical random walk takes O(2d) steps to find B from A but quantum walk of [ 7 , 8] takes O(d2) steps.”
On the Relationship Between Continuous- and Discrete-Time Quantum Walk (2008, background): “1 Similarly, one can define two notions of quantum walk, the continuous-time quantum walk [14, 27] and the discrete-time quantum walk [2, 6, 52].”
Quantum algorithms: an overview (2015, neutral): “For some graphs, hitting time of quantum walks can be exponentially less than their classical counterparts [27, 54].”
Quantum walks: a comprehensive review (2012, methodology): “In the field of quantum walks, Hines and Stamp have shown in [193] how to map quantum walk Hamiltonians and Hamiltonians for other quantum systems on hypercubes and hyperlattices.”
Efficient Quantum Algorithms for Simulating Sparse Hamiltonians (2005, background): “Such respresentations of Hamiltonians can arise as encodings of computational problems, such as simulations of quantum walks [6, 7, 8, 9, 10] or adiabatic quantum computations [11].”
Quantum random walks: An introductory overview (2003, methodology): “13: Approximation of the finite line by an infinite homogeneous line [25].”
Exponential algorithmic speedup by a quantum walk (2002, methodology): “Our problem is based on a generalization of the graphs presented in [17].”