Exponential algorithmic speedup by quantum walk

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.

24 pages, 7 figures; minor corrections and clarifications

Cited by in corpus (17)

• Limits on Efficient Computation in the Physical World
• A note on graphs resistant to quantum uniform mixing
• Mixing and Decoherence in Continuous-Time Quantum Walks on Cycles
• A note on the classical lower bound for a quantum walk algorithm
• Coins Make Quantum Walks Faster
• Mixing in Continuous Quantum Walks on Graphs
• Quantum Cellular Automata from Lattice Field Theories
• On Quantum Cellular Automata
• Limit theorems and absorption problems for quantum random walks in one dimension
• Entanglement and its Role in Shor's Algorithm
• Estimating mixing properties of local Hamiltonian dynamics and continuous quantum random walks is PSPACE-hard
• A Lattice Problem in Quantum NP
• Quantum Algorithm for Commutativity Testing of a Matrix Set
• Temporal Fluctuations of Continuous-Time Quantum Random Walks on Circles
• Quantum Algorithms and Covering Spaces
• Continuous-time quantum walks on the symmetric group
• Quantum Search of Spatial Regions