Quantum search of spatial regions
Open accessThe DOI matches its Crossref record; 19 of the 19 references it cites were found in a registry or an index.
Abstract
Can Grover's quantum search algorithm speed up search of a physical region - for example a 2D grid of size /spl radic/n x /spl radic/n? The problem is that /spl radic/n time seems to be needed for each query, just to move amplitude across the grid. Here we show that this problem can be surmounted, refuting a claim to the contrary by Benioff. In particular, we show how to search a d-dimensional hypercube in time 0(/spl radic/n) for d /spl ges/ 3, or 0(/spl radic/n log/sup 3/ n) for d = 2. More generally, we introduce a model of quantum query complexity on graphs, motivated by fundamental physical limits on information storage, particularly the holographic principle from black hole thermodynamics. Our results in this model include almost-tight upper and lower bounds for many search tasks; a generalized algorithm that works for any graph with good expansion properties, not just hypercubes; and relationships among several notions of locality for unitary matrices acting on graphs. As an application of our results, we give an 0(/spl radic/n)-qubit communication protocol for the disjointness problem, which improves an upper bound of Hoyer and de Wolf and matches a lower bound of Razborov.
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
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
Microscopic origin of the Bekenstein-Hawking entropy
Strominger, A., & Vafa, C. (1996) · Physics Letters B · doi:10.1016/0370-2693(96)00345-0 · Cited by 3,072
Microscopic Origin of the Bekenstein-Hawking Entropy
Strominger, A., & Vafa, C. (1996) · arXiv · doi:10.48550/arxiv.hep-th/9601029 · Cited by 3,071
Gaussian elimination is not optimal
Strassen, V. (1969) · Numerische Mathematik · doi:10.1007/bf02165411 · Cited by 2,509 · cited 1×
“ogn) steps. To us this illustrates why one should not assume an algorithm is optimal on heuristic grounds. Painful experience—for example, the “obviously optimal” O n3 matrix multiplication algorithm [27]—is what taught computer scientists to see the proving of lower bounds as more than a formality. Our setting is rel…”
BackgroundBousso, R. (2002) · Reviews of Modern Physics · doi:10.1103/revmodphys.74.825 · Cited by 1,741
Quantum amplitude amplification and estimation
Brassard, G., Høyer, P., Mosca, M., & Tapp, A. (2002) · Contemporary Mathematics · doi:10.1090/conm/305/05215 · Cited by 1,680
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
Universal upper bound on the entropy-to-energy ratio for bounded systems
Bekenstein, J. D. (1981) · Physical Review D · doi:10.1103/physrevd.23.287 · Cited by 1,182
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
Nonlocality and communication complexity
Buhrman, H., Cleve, R., Massar, S., & de Wolf, R. (2010) · Reviews of Modern Physics · doi:10.1103/revmodphys.82.665 · Cited by 622
(2004) · doi:10.1109/focs.2004.53 · Cited by 599
Quantum Walk Algorithm for Element Distinctness
Ambainis, A. (2004) · 45th Annual IEEE Symposium on Foundations of Computer Science · doi:10.1109/focs.2004.54 · Cited by 216
Self-citationSpatial search and the Dirac equation
Childs, A. M., & Goldstone, J. (2004) · Physical Review A · doi:10.1103/physreva.70.042312 · Cited by 146
“Aaronson and Ambainis gave an algorithm that finds a marked item in the optimal time O( √ N) for a lattice in d > 2 dimensions, and in time O( √ N log(2)N) for a two-dimensional lattice [3].”
BackgroundUnitarity plus causality implies localizability
Arrighi, P., Nesme, V., & Werner, R. (2011) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2010.05.004 · Cited by 99
Metadata
- Authors
- Aaronson, S., & Ambainis, A.
- Venue
- 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings.
- Publisher
- IEEE Computer. Soc
- Published
- 2004-03-02
- Pages
- 200-209
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W2143541668
- Cited by
- 121
- References
- 19
- FWCI
- 4.99
- Type
- conference paper
- Language
- en
- Open access
- green
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
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.