Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Probability Theory and Related Fields

Discrete Quantum Walks Hit Exponentially Faster

Julia Kempe

Published Feb 10, 2005• 149 citations
Publisher
DOI
10.1007/s00440-004-0423-2

Related papers

Discrete Quantum Walks Hit Exponentially Faster

Julia Kempe

Lecture notes in computer science•Jan 1, 2003•84 citations

Quantum Random Walks Hit Exponentially Faster

Julia Kempe

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.

arXiv:quant-ph/0205083•May 14, 2002•136 citations

Connecting the Discrete-time and Continuous-time Quantum Walks

Albert T. Schmitz

Bulletin of the American Physical Society•Mar 15, 2016•0 citations

Discrete-time quantum walk with history dependence

Zlatko Dimcovic, Yevgeniy Kovchegov

Bulletin of the American Physical Society•Mar 18, 2013•0 citations

Quantum walks on embedded hypercubes

Adi Makmal, Manran Zhu, Daniel Manzano +2 more

It has been proved by Kempe that discrete quantum walks on the hypercube (HC) hit exponentially faster than the classical analog. The same was also observed numerically by Krovi and Brun for a slightly different property, namely, the expected hitting time. Yet, to what extent this striking result survives in more general graphs is to date an open question. Here, we tackle this question by studying the expected hitting time for quantum walks on HCs that are embedded into larger symmetric structures. By performing numerical simulations of the discrete quantum walk and deriving a general expression for the classical hitting time, we observe an exponentially increasing gap between the expected classical and quantum hitting times, not only for walks on the bare HC, but also for a large family of embedded HCs. This suggests that the quantum speedup is stable with respect to such embeddings.

arXiv:1309.5253•Physical Review A•Aug 14, 2014•19 citations

Partition-based discrete-time quantum walks

Norio Konno, Renato Portugal, Iwao Sato +1 more

arXiv:1707.07127•Quantum Information Processing•Mar 12, 2018•28 citations
It has been proved by Kempe that discrete quantum walks on the hypercube (HC) hit exponentially faster than the classical analog. The same was also observed numerically by Krovi and Brun for a slightly different property, namely, the expected hitting time. Yet, to what extent this striking result survives in more general graphs is to date an open question. Here, we tackle this question by studying the expected hitting time for quantum walks on HCs that are embedded into larger symmetric structures. By performing numerical simulations of the discrete quantum walk and deriving a general expression for the classical hitting time, we observe an exponentially increasing gap between the expected classical and quantum hitting times, not only for walks on the bare HC, but also for a large family of embedded HCs. This suggests that the quantum speedup is stable with respect to such embeddings.