@inbook{fd27987d5b994b5ab22c203d7a37788f,

title = "Discrete quantum walks hit exponentially faster",

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 random walk on the n-bit hypercube from one comer 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.",

author = "Julia Kempe",

year = "2003",

doi = "10.1007/978-3-540-45198-3_30",

language = "English (US)",

isbn = "3540407707",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "354--369",

editor = "Sanjeev Asora and Amit Sahai and Klaus Jansen and Rolim, {Jose D.P.}",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

}