Quantum walks on graphs

By Dorit Aharonov, Andris Ambainis, Julia Kempe, Umesh V. Vazirani. Symposium on the Theory of Computing, 2000

751 citations recorded by the source corpus.

We set the ground for a theory of quantum walks on graphs-the generalization of random walks on finite graphs to the quantum world. Such quantum walks do not converge to any stationary distribution, as they are unitary and reversible. However, by suitably relaxing the definition, we can obtain a measure of how fast the quantum walk spreads or how confined the quantum walk stays in a small neighborhood. We give definitions of mixing time, filling time, dispersion time. We show that in all these measures, the quantum walk on the cycle is almost quadratically faster then its classical correspondent. On the other hand, we give a lower bound on the possible speed up by quantum walks for general graphs, showing that quantum walks can be at most polynomially faster than their classical counterparts.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/508650174102df16a7b4c1f66d610571381d154c

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

Coins make quantum walks faster (2004, background): “Both discrete-time [Mey96, AAKV01, ABN + 01] and continous time [FG98, CFG02] quantum walks have been introduced 1 .”
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 algorithms: an overview (2015, neutral): “The separation between quantum and classical mixing time can be quadratic, but no more than this [3] (approximately).”
QUANTUM WALKS AND THEIR ALGORITHMIC APPLICATIONS (2003, background): “Recently, quantum counterparts of Markov chains have been deﬁned [2, 3, 4, 5], with the hope that they could have similar applications in design of new quantum algorithms.”
Quantum speedup of Monte Carlo methods (2015, background): “[10,11]), although it is not known whether this can be achieved in general [12–14].”
Quantum walk algorithm for element distinctness (2003, methodology): “r ﬂavor but uses completely diﬀerent methods to search the graph (quantum walk instead of ‘’divide-and-conquer”). Quantum walks. There has been considerable amount of research on quantum walks (e.g., [5, 30, 4, 9]) and their applications (e.g., [20, 18, 26, 31, 21]). We refer to [27] for an excellen”
On Quantum Cellular Automata (2004, background): “So-called coined quantum walk (CQW) on cycle [14] may be described as composition of Eq.”
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 for the triangle problem (2003, background): “the content of the coin register (see [29, 2, 7]).”
Quantum walks: a comprehensive review (2012, background): “Several other important results for quantum walks on a graph are delivered in [13].”
One-dimensional quantum walks (2001, background): “[2]D.Aharonov,A.Ambainis,J.Kempe,and U.Vazirani.”
Exponential algorithmic speedup by a quantum walk (2002, methodology): “In the present paper, we modify the example presented in [7] and construct a black box problem based on it that can be solved e.ciently a quantum algorithm that simulates a quantum walk, whereas no classical algorithm can solve the problem in subexponential time.”
Quantum walks in higher dimensions (2001, background): “Quantum physics introduces new perspectives, such as quantum diffusion [1], quantum stochastics [2], and quantum walks [3, 4, 5, 6].”