Quantum Walks on the Hypercube
The DOI matches its Crossref record; 8 of the 8 references it cites were found in a registry or an index.
Abstract
Recently, it has been shown that one-dimensional quantum walks can mix more quickly than classical random walks, suggesting that quantum Monte Carlo algorithms can outperform their classical counterparts. We study two quantum walks on the n-dimensional hypercube, one in discrete time and one in continuous time. In both cases we show that the instantaneous mixing time is (π/4)n steps, faster than the Θ(n log n) steps required by the classical walk. In the continuous-time case, the probability distribution is exactly uniform at this time. On the other hand, we show that the average mixing time as defined by Aharonov et al. [AAKV01] is Ω(n 3/2) in the discrete-time case, slower than the classical walk, and nonexistent in the continuous-time case. This suggests that the instantaneous mixing time is a more relevant notion than the average mixing time for quantum walks on large, well-connected graphs. Our analysis treats interference between terms of different phase more carefully than is necessary for the walk on the cycle; previous general bounds predict an exponential average mixing time when applied to the hypercube.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A fast quantum mechanical algorithm for database search
Grover, L. K. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237866 · Cited by 8,830
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472
Group representations in probability and statistics
Diaconis, P. (1988) · doi:10.1214/lnms/1215467407 · Cited by 1,381
Quantum computation and decision trees
Farhi, E., & Gutmann, S. (1998) · Physical Review A · doi:10.1103/physreva.58.915 · Cited by 1,215 · cited 3×
“THE CONTINUOUS-TIME WALK: This model, introduced in [ FG98 ], works directly on L G . The walk evolves by treating the adjacency matrix of the graph as a Hamiltonian and using the Schr ¨ odinger equation.”
BackgroundMethodInfluentialAharonov, D., Ambainis, A., Kempe, J., & Vazirani, U. (2001) · Proceedings of the thirty-third annual ACM symposium on Theory of computing · doi:10.1145/380752.380758 · Cited by 654
Ambainis, A., Bach, E., Nayak, A., Vishwanath, A., & Watrous, J. (2001) · Proceedings of the thirty-third annual ACM symposium on Theory of computing · doi:10.1145/380752.380757 · Cited by 562 · cited 16×
“(Since a unitary process cannot be mixing, we define a stochastic process from a quantum one by performing a measurement at a given time or a distribution of times.) Several recent articles [ AAKV01 , ABN 01, NV00] have answered this question in the affirmative, showing, for example, that a quantum walk on the n-cycle…”
BackgroundMethodInfluentialAn Example of the Difference Between Quantum and Classical Random Walks
Childs, A. M., Farhi, E., & Gutmann, S. (2002) · Quantum Information Processing · doi:10.1023/a:1019609420309 · Cited by 481
A probabilistic algorithm for k-SAT and constraint satisfaction problems
Schoning, T. (2003) · 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039) · doi:10.1109/sffcs.1999.814612 · Cited by 433 · cited 1×
“As algorithmic tools, they have been applied to a variety of central problems, such as estimation of the volume of a convex body [DFK91, LK99], approximation of the permanent [JS89, JSV00], and discovery of satisfying assignments for Boolean formulae [ Sch99 ].”
Cited by
Quantum walks: a comprehensive review
Venegas-Andraca, S. E. (2012) · Quantum Information Processing · doi:10.1007/s11128-012-0432-5 · Cited by 934
Exponential algorithmic speedup by a quantum walk
Childs, A. M., Cleve, R., Deotto, E., Farhi, E., Gutmann, S., & Spielman, D. A. (2003) · Proceedings of the thirty-fifth annual ACM symposium on Theory of computing · doi:10.1145/780542.780552 · Cited by 825
“... traversal algorithm for the n-dimensional hypercube (where entrance and exit are two vertices whose distance apart is n). For a description of the algorithm, see Appendix A. This means that there can be no exponential algorithmic speedup using quantum walks to traverse the hypercube, even though both continuous an…”
BackgroundOn the Relationship Between Continuous- and Discrete-Time Quantum Walk
Childs, A. M. (2010) · Communications in Mathematical Physics · doi:10.1007/s00220-009-0930-1 · Cited by 411
“Finally, I discuss limitations of the method for simulating Hamiltonians with negative matrix elements, and present two problems that motivate attempting to circumvent these limitations.”
MethodMoore, C., & Mertens, S. (2011) · doi:10.1093/acprof:oso/9780199233212.001.0001 · Cited by 347
Self-citationQuantum Random Walks in One Dimension
Konno, N. (2002) · Quantum Information Processing · doi:10.1023/a:1023413713008 · Cited by 302
Metadata
- Authors
- Moore, C., & Russell, A.
- Venue
- Lecture Notes in Computer Science
- Publisher
- Springer Berlin Heidelberg
- Published
- 2002
- Pages
- 164-178
- ISSN
- 0302-9743 (ISSN-L)
- OpenAlex
- W1854045309
- Cited by
- 207
- References
- 8
- FWCI
- 11.69
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Quantum Walks on the Hypercube. https://app.cochat.ai/papers/10.1007/3-540-45726-7_14
- The paper
- Moore, C., & Russell, A. (2002). Quantum Walks on the Hypercube. Lecture Notes in Computer Science. https://doi.org/10.1007/3-540-45726-7_14
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.