Spatial search and the Dirac equation
Open accessAbstract
We consider the problem of searching a $d$-dimensional lattice of $N$ sites for a single marked location. We present a Hamiltonian that solves this problem in time of order $\sqrt{N}$ for $d>2$ and of order $\sqrt{N}\phantom{\rule{0.3em}{0ex}}\mathrm{log}\phantom{\rule{0.3em}{0ex}}N$ in the critical dimension $d=2$. This improves upon the performance of our previous quantum walk search algorithm (which has a critical dimension of $d=4$), and matches the performance of a corresponding discrete-time quantum walk algorithm. The improvement uses a lattice version of the Dirac Hamiltonian, and thus requires the introduction of spin (or coin) degrees of freedom.
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.
Integrity signals
Registry
Cites
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.
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 [8]
Section II (p. 2) defines the Dirac Hamiltonian in d dimensions with momentum operator p = −i∂/∂x, supporting the citing sentence’s identification of a Dirac Hamiltonian. But the paper studies a continuous-time spatial-search Hamiltonian; its Discussion (p. 4) only compares that algorithm with discrete-time quantum walks. It does not show that a continuum limit of a DTQW mapping yields the one-dimensional Dirac equation. (LLM, conf=0.83)
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
Quantum Mechanics Helps in Searching for a Needle in a Haystack
Grover, L. K. (1997) · Physical Review Letters · doi:10.1103/physrevlett.79.325 · Cited by 4,306 · see citing works
Strengths and Weaknesses of Quantum Computing
Bennett, C. H., Bernstein, E., Brassard, G., & Vazirani, U. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539796300933 · Cited by 1,470 · see citing works
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 · see citing works
Flagged first, then by citations
Research works printed but not linked: 4
- [9]G. Brassard, P. Høyer, M. Mosca, and A. Tapp, in Quantum Computation and Information , edited by S. J. Lomonaco and H. E. Brandt (AMS, Providence, RI, 2002), vol. 305 of AMS Contemporary Mathematics Series , quant-ph/0005055. · arXiv
- [11]D. A. Meyer, On the absence of homogeneous scalar unitary cellular automata , Phys. Lett. A 223 , 337 (1996), quant-ph/9604011. · arXiv
- [12]P. A. M. Dirac, The quantum theory of the electron , Proc. Roy. Soc. London A 117 , 610 (1928).
- [13]M. Creutz, Quarks, Gluons, and Lattices (Cambridge University Press, Cambridge, 1983).
Cited by
Sorted by citations
Universal Computation by Quantum Walk
Childs, A. M. (2009) · Physical Review Letters · doi:10.1103/physrevlett.102.180501 · Cited by 1,002 · see citing works
Self-citationUniversal quantum computation using the discrete-time quantum walk
Lovett, N. B., Cooper, S., Everitt, M., Trevers, M., & Kendon, V. (2010) · Physical Review A · doi:10.1103/physreva.81.042330 · Cited by 510 · see citing works
On 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 · see citing works
Self-citationQuantum algorithms for algebraic problems
Childs, A. M., & van Dam, W. (2010) · Reviews of Modern Physics · doi:10.1103/revmodphys.82.1 · Cited by 344 · see citing works
Self-citationMagniez, F., Nayak, A., Roland, J., & Santha, M. (2011) · SIAM Journal on Computing · doi:10.1137/090745854 · Cited by 294 · see citing works
Decoherence in quantum walks – a review
KENDON, V. (2007) · Mathematical Structures in Computer Science · doi:10.1017/s0960129507006354 · Cited by 252 · see citing works
Strauch, F. W. (2006) · Physical Review A · doi:10.1103/physreva.73.054302 · Cited by 115 · see citing works
The Dirac equation as a quantum walk: higher dimensions, observational convergence
Arrighi, P., Nesme, V., & Forets, M. (2014) · Journal of Physics A: Mathematical and Theoretical · doi:10.1088/1751-8113/47/46/465302 · Cited by 72 · see citing works
Relativistic effects and rigorous limits for discrete- and continuous-time quantum walks
Strauch, F. W. (2007) · Journal of Mathematical Physics · doi:10.1063/1.2759837 · Cited by 54 · see citing works
Quantum walks, quantum gates, and quantum computers
Hines, A. P., & Stamp, P. C. E. (2007) · Physical Review A · doi:10.1103/physreva.75.062321 · Cited by 54 · see citing works
- 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-10-19
- Volume
- 70
- Issue
- 4
- ISSN
- 0556-2791 (ISSN-L)
- 1050-2947
- 1094-1622
- OpenAlex
- W1968991779
- Cited by
- 146
- References
- 3
- Citations by year
- 2026: 1 · 2025: 2 · 2024: 3 · 2023: 4 · 2022: 6 · 2021: 5 · 2020: 7 · 2019: 5 · 2018: 10 · 2017: 3 · 2016: 5 · 2015: 5 · 2014: 4 · 2013: 4 · 2012: 3
- FWCI
- 8.12
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- Physical Review A (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- 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
- spatial search, quantum walks, Dirac Hamiltonian, lattice search, critical dimension, discrete-time quantum walks, spin degrees of freedom, quantum search, time complexity
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
