CoChat
Sign Up
Cited by 725Quantum Computing Algorithms and ArchitectureQuantum Mechanics and ApplicationsQuantum Information and Cryptography

Spatial search by quantum walk

Open access
Childs, Andrew M., Goldstone, Jeffrey·2004·Physical Review A
DOI 10.1103/physreva.70.022314
Open this paper in CoChat — free accountOpen PDF

Abstract

Grover's quantum search algorithm provides a way to speed up combinatorial search, but is not directly applicable to searching a physical database. Nevertheless, Aaronson and Ambainis showed that a database of $N$ items laid out in $d$ spatial dimensions can be searched in time of order $\sqrt{N}$ for $d>2$, and in time of order $\sqrt{N}\phantom{\rule{0.3em}{0ex}}\text{poly}(\mathrm{log}\phantom{\rule{0.3em}{0ex}}N)$ for $d=2$. We consider an alternative search algorithm based on a continuous-time quantum walk on a graph. The case of the complete graph gives the continuous-time search algorithm of Farhi and Gutmann, and other previously known results can be used to show that $\sqrt{N}$ speedup can also be achieved on the hypercube. We show that full $\sqrt{N}$ speedup can be achieved on a $d$-dimensional periodic lattice for $d>4$. In $d=4$, the quantum walk search algorithm takes time of order $\sqrt{N}\phantom{\rule{0.3em}{0ex}}\text{poly}(\mathrm{log}\phantom{\rule{0.3em}{0ex}}N)$, and in $d<4$, the algorithm does not provide substantial speedup.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

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

Integrity signals

Registry

Crossref · 10.1103/physreva.70.022314

Cites

5 of 5 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

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

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • The continuum limit of the DTQW mapping yields the one-dimensional Dirac equation.

    “where H D is the Hamiltonian for the one-dimensional Dirac equation (with ℏ = c = 1, p = -i∂ x ) [10]:”

    From Relativistic quantum walks (2006) · cites this paper as [7]

    Section II (p. 2) defines a continuous-time quantum walk and relates its lattice Laplacian to the continuum operator ∇². Section I (p. 1) mentions discrete-time walks, but neither passage addresses a discrete-time quantum-walk mapping to the one-dimensional Dirac equation. Searches for that mapping and its continuum limit found no supporting passage in our copy. (LLM, conf=0.75)

    Experimental — accuracy not yet measured

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 2

  1. [18]G. N. Watson, Three triple integrals , Quart. J. Math. Oxford Scr. 10 , 266 (1939).
  2. [22]W. van Dam, M. Mosca, and U. Vazirani, How powerful is adiabatic quantum computation? , quant-ph/0206003, Proc. 42nd Symposium on Foundations of Computer Science, 279 (2001). · arXiv

Cited by

Sorted by citations

Authors
Childs, A. M., & Goldstone, J.
Affiliations
Massachusetts Institute of Technology (US)
ORCID
Childs, Andrew M.
Venue
Physical Review A
Publisher
American Physical Society (APS)
Published
2004-08-23
Volume
70
Issue
2
ISSN
  • 0556-2791 (ISSN-L)
  • 1050-2947
  • 1094-1622
DOI
10.1103/physreva.70.022314
OpenAlex
W2040927484
Cited by
725
References
5
Citations by year
2026: 28 · 2025: 51 · 2024: 58 · 2023: 46 · 2022: 49 · 2021: 55 · 2020: 54 · 2019: 52 · 2018: 37 · 2017: 34 · 2016: 38 · 2015: 34 · 2014: 23 · 2013: 22 · 2012: 15
FWCI
17.92
Type
journal article
Language
en
Open access
Licence
link.aps.org/licenses/aps-default-license (vor)
Locations
  • Physical Review A (publishedVersion)
  • arXiv (Cornell University) (publishedVersion)
  • CERN Document Server (European Organization for Nuclear Research) (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Mechanics and Applications
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
Keywords
continuous-time quantum walks, spatial search, quantum search, Grover's algorithm, periodic lattices, hypercube, complete graphs, search speedup, dimension dependence

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