CoChat

Quantum Walks on the Hypercube

Moore, Cristopher, Russell, Alexander · 2002 · Lecture Notes in Computer Science
Cited by 207

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.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1007/3-540-45726-7_14

Cites

8 of 8 references verified0 citation errors · 0 not checkable

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.

A few free checks a day · papers already verified open instantly · results are public

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

Show all 8 references

Cited by

See all 207

Metadata

Authors
Moore, C., & Russell, A.
Venue
Lecture Notes in Computer Science
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.