Exponential algorithmic speedup by a quantum walk
Open Access
- 9 June 2003
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 59-68
Abstract
We construct an oracular (i.e., black box) 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 oracular setting. We then show how this quantum walk can be used to solve our problem by rapidly traversing a graph. Finally, we prove that no classical algorithm can solve this problem with high probability in subexponential time.Comment: 24 pages, 7 figures; minor corrections and clarificationKeywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Sharp Quantum versus Classical Query Complexity SeparationsAlgorithmica, 2002
- Quantum Simulations of Classical Random Walks and Undirected Graph ConnectivityJournal of Computer and System Sciences, 2001
- Quantum computation and decision treesPhysical Review A, 1998
- Quantum Complexity TheorySIAM Journal on Computing, 1997
- On the Power of Quantum ComputationSIAM Journal on Computing, 1997
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum ComputerSIAM Journal on Computing, 1997
- From quantum cellular automata to quantum lattice gasesJournal of Statistical Physics, 1996
- Universal Quantum SimulatorsScience, 1996
- Rapid solution of problems by quantum computationProceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences, 1992
- Quantum theory, the Church–Turing principle and the universal quantum computerProceedings of the Royal Society of London. A. Mathematical and Physical Sciences, 1985