Abstract
This paper addresses the question: what processes take polynomial time on a quantum computer that require exponential time classically? We show that the hitting time of the discrete time quantum 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 walks. We provide the basic framework for quantum hitting time and give two alternative definitions to set the ground for its study on general graphs. We outline a possible application to sequential packet routing.
Original language | English (US) |
---|---|
Pages (from-to) | 215-235 |
Number of pages | 21 |
Journal | Probability Theory and Related Fields |
Volume | 133 |
Issue number | 2 |
DOIs | |
State | Published - Oct 2005 |
ASJC Scopus subject areas
- Analysis
- Statistics and Probability
- Statistics, Probability and Uncertainty