Discrete quantum walks hit exponentially faster

Julia Kempe

Research output: Contribution to journalArticlepeer-review


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 languageEnglish (US)
Pages (from-to)215-235
Number of pages21
JournalProbability Theory and Related Fields
Issue number2
StatePublished - Oct 2005

ASJC Scopus subject areas

  • Analysis
  • Statistics and Probability
  • Statistics, Probability and Uncertainty


Dive into the research topics of 'Discrete quantum walks hit exponentially faster'. Together they form a unique fingerprint.

Cite this