Quantum Random Walks Hit Exponentially Faster

Simple item page
dc.creatorKempe, Julia
dc.date2002-05-14
dc.date.accessioned2026-07-07T06:26:59Z
dc.date.available2026-07-07T06:26:59Z
dc.descriptionWe 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.
dc.description15 pages, no Figures
dc.identifierhttps://arxiv.org/abs/quant-ph/0205083
dc.identifierhttp://arxiv.org/abs/quant-ph/0205083
dc.identifierProbability Theory and Related Fields, Vol. 133(2), p. 215-235 (2005), conference version in Proc. 7th RANDOM, p. 354-69, 2003
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/97285
dc.subjectQuantum Physics
dc.subjectComputational Complexity
dc.titleQuantum Random Walks Hit Exponentially Faster
dc.typetext

Files

Collections

arXiv