Quantum Random Walks Hit Exponentially Faster

Abstract

We show that the hitting time of the discrete time quantum random walk on the n-bit hypercube from one corner to its opposite is polynomial in n. This gives the first exponential quantum-classical gap in the hitting time of discrete quantum random walks. We provide the framework for quantum hitting time and give two alternative definitions to set the ground for its study on general graphs. We then give an application to random routing.

15 pages, no Figures

Cited by in corpus (9)

• Exponential algorithmic speedup by quantum walk
• The Hidden Subgroup Problem - Review and Open Problems
• Decoherence in a quantum walk on the line
• A note on graphs resistant to quantum uniform mixing
• Mixing and Decoherence in Continuous-Time Quantum Walks on Cycles
• One-dimensional quantum walks with absorbing boundaries
• Mixing in Continuous Quantum Walks on Graphs
• Limit theorems and absorption problems for quantum random walks in one dimension
• Quantum Algorithms and Covering Spaces