Faster quantum-walk algorithm for the two-dimensional spatial search
Open accessAbstract
We consider the problem of finding a desired item out of $N$ items arranged on the sites of a two-dimensional lattice of size $\sqrt{N}\ifmmode\times\else\texttimes\fi{}\sqrt{N}$. The previous quantum-walk based algorithms take $O(\sqrt{N}\text{ }\text{ln}\text{ }N)$ steps to solve this problem, and it is an open question whether the performance can be improved. We present an algorithm which solves the problem in $O(\sqrt{N\text{ }\text{ln}\text{ }N})$ steps, thus giving an $O(\sqrt{\text{ln}\text{ }N})$ improvement over the known algorithms. The improvement is achieved by controlling the quantum walk on the lattice using an ancilla qubit.
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?
Quantum search algorithms based on quantum walks overcome their classical counterparts solely when the spatial dimension of the lattice is equal or greater than two.
“As an example, quantum search algorithms based on QWs overcome their classical counterparts solely when the spatial dimension of the lattice is equal or greater than two 31 .”
From Quantum walks of two correlated photons in a 2D synthetic lattice (2022) · cites this paper as [31]
The Introduction (p. 1) and Discussion (p. 5) show that the paper’s quantum-walk algorithm speeds up two-dimensional spatial search; the Introduction also says it applies in higher dimensions. But our copy does not establish the claim’s exclusive threshold: it does not show that quantum-walk search fails to outperform classical search in one dimension. (LLM, conf=0.84)
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
Quantum random-walk search algorithm
Shenvi, N., Kempe, J., & Whaley, K. B. (2003) · Physical Review A · doi:10.1103/physreva.67.052307 · Cited by 1,150 · see citing works
Flagged first, then by citations
Research works printed but not linked: 2
Cited by
Sorted by citations
Universal 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
Quantum walks on a programmable two-dimensional 62-qubit superconducting processor
Gong, M., Wang, S., Zha, C., Chen, M.-C., Huang, H.-L., Wu, Y., Zhu, Q., Zhao, Y., Li, S., Guo, S., et al. (2021) · Science · doi:10.1126/science.abg7812 · Cited by 331 · see citing works
Magniez, F., Nayak, A., Roland, J., & Santha, M. (2011) · SIAM Journal on Computing · doi:10.1137/090745854 · Cited by 294 · see citing works
Experimental realization of a delayed-choice quantum walk
Jeong, Y.-C., Di Franco, C., Lim, H.-T., Kim, M. S., & Kim, Y.-H. (2013) · Nature Communications · doi:10.1038/ncomms3471 · Cited by 76 · see citing works
Quantum walks of two correlated photons in a 2D synthetic lattice
Esposito, C., Barros, M. R., Durán Hernández, A., Carvacho, G., Di Colandrea, F., Barboza, R., Cardano, F., Spagnolo, N., Marrucci, L., & Sciarrino, F. (2022) · npj Quantum Information · doi:10.1038/s41534-022-00544-0 · Cited by 36 · see citing works
Asymptotic properties of the Dirac quantum cellular automaton
Pérez, A. (2016) · Physical Review A · doi:10.1103/physreva.93.012328 · Cited by 18 · see citing works
- Authors
- Tulsi, A.
- Affiliations
- Indian Institute of Science Bangalore (IN)
- Corresponding author
- Tulsi, Avatar
- Venue
- Physical Review A
- Publisher
- American Physical Society (APS)
- Published
- 2008-07-09
- Volume
- 78
- Issue
- 1
- ISSN
- 0556-2791 (ISSN-L)
- 1050-2947
- 1094-1622
- OpenAlex
- W1980458533
- Cited by
- 185
- References
- 3
- Citations by year
- 2026: 4 · 2025: 9 · 2024: 7 · 2023: 10 · 2022: 9 · 2021: 12 · 2020: 8 · 2019: 11 · 2018: 12 · 2017: 8 · 2016: 12 · 2015: 19 · 2014: 3 · 2013: 12 · 2012: 11
- FWCI
- 19.56
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- Physical Review A (publishedVersion)
- NOT FOUND REPOSITORY (Indian Institute of Science Bangalore) (acceptedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Mechanics and Applications
- Keywords
- quantum walks, spatial search, two-dimensional lattice, search algorithms, ancilla qubits, Grover's algorithm
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
