Exponential algorithmic speedup by a quantum walk

By Andrew M. Childs, Richard Cleve, E. Deotto, Edward Farhi, Sam Gutmann, Daniel A. Spielman. Symposium on the Theory of Computing, 2002

948 citations recorded by the source corpus.

We construct a black box graph traversal problem that can be solved exponentially faster on a quantum computer than on a classical computer. The quantum algorithm is based on a continuous time quantum walk, and thus employs a different technique from previous quantum algorithms based on quantum Fourier transforms. We show how to implement the quantum walk efficiently in our black box setting. We then show how this quantum walk solves our problem by rapidly traversing a graph. Finally, we prove that no classical algorithm can solve the problem in subexponential time.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/1db974616dc9ce742c2f5cf2a8d8e1a25d0b9740

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

Quantum walk algorithm for element distinctness (2003, background): “The first class is exponentially faster hitting times [19, 18, 25].”
Universal computation by quantum walk. (2008, background): “By exploiting interference effects, quantum walks can outperform random walks at certain computational tasks: there are black-box problems for which quantum walk provides an exponential speedup over classical computation [4, 5], and many quantum walk algorithms achieve polynomial speedup over classi”
Adiabatic quantum computation is equivalent to standard quantum computation (2004, background): “, [2–5]) have demonstrated the possible exponential advantage of quantum computing systems over classical ones.”
Universal Computation by Multiparticle Quantum Walk (2012, methodology): “roduced as potential techniques for quantum computation and have subsequently developed into major algorithmic tools. Applications include an example of exponential speedup over classical computation [13] and optimal algorithms for element distinctness [5] and formula evaluation [17]. In addition to”
Quantum walks: a comprehensive review (2012, methodology): “In order to build the quantum walk that will be used to traverse a graph Gr, the authors of [116] defined a Hamiltonian Ĥ based on G’s adjacency matrix A.”
Quantum random walks: An introductory overview (2003, methodology): “To get a hand on the exact hitting time of this walk very recently [27] an upper bound for the propagation time is found.”
Spin- 1 ∕ 2 particles moving on a two-dimensional lattice with nearest-neighbor interactions can realize an autonomous quantum computer (2005, background): “Since the time evolution of such a walk has been discussed in detail in the literature [33], we will only describe the implications for our model.”
Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters (2015, methodology): “In addition, sparse Hamiltonian simulation can be used to design other quantum algorithms [17, 18, 19].”
Machine learning \& artificial intelligence in the quantum domain (2017, result): “Similar results have been achieved in a plethora of other scenarios, such as spatial search (Childs and Goldstone, 2004), search over structures (including various quantum walk-based algorithms (Kempe, 2003; Childs et al., 2003; Reitzner et al., 2012)), NAND (Childs et al.”
A Polynomial Quantum Algorithm for Approximating the Jones Polynomial (2005, background): “One interesting exception is the beautiful result of [8] who used random walks to achieve an exponential algorithmic speed-up for an oracle graph problem.”
Quantum Computation and Information (2006, background): “…a quadratic speed-up [40] [41], and in 2003 Andrew Childs and collaborators came up with an algorithm to find a particular node in a specific graph [28], a very academic problem but the only quantum algorithm so far offering a demonstrated exponential speed-up compared to its classical…”
Quipper: a scalable quantum programming language (2013, methodology): “To ﬁnd a labeled node in a graph [4].”
QUANTUM WALKS AND THEIR ALGORITHMIC APPLICATIONS (2003, methodology): “[6, 7, 8 ] to get speedups for natural problems?”
Hamiltonian simulation using linear combinations of unitary operations (2012, methodology): “This work was later generalized to give eﬃcient simulations of sparse time-independent Hamiltonians that need not have tensor-product structure [4, 9].”