Searching a quantum phone book
Abstract
Finding a phone number in a directory when one knows the name is easy; much harder is finding the name given the number. On average, a search algorithm will have to scan half the total number of entries. If the database or directory is extremely large, the search may be impossible with classical computers. New possibilities emerge, however, with quantum computing. As Brassard discusses in his Perspective, a new algorithm developed by L. K. Grover enables much faster searching of large databases if one uses a quantum computer.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
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?
Various important computer science problems can be represented in the form of finding a unique state satisfying a condition among N=2^n states.
“Various important computer science problems can be represented in this form [3] [5] [9].”
From Quantum Mechanics Helps in Searching for a Needle in a Haystack (1997) · cites this paper as [9]
Cites
Algorithms for quantum computation: discrete logarithms and factoring
Shor, P. W. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365700 · Cited by 8,713 · see citing works
Quantum theory, the Church–Turing principle and the universal quantum computer
Deutsch, D. (1985) · Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences · doi:10.1098/rspa.1985.0070 · Cited by 4,597 · see citing works
DiVincenzo, D. P. (1995) · Science · doi:10.1126/science.270.5234.255 · Cited by 1,651 · see citing works
Quantum Computers, Factoring, and Decoherence
Chuang, I. L., Laflamme, R., Shor, P. W., & Zurek, W. H. (1995) · Science · doi:10.1126/science.270.5242.1633 · Cited by 289 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
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
“Various important computer science problems can be represented in this form [3] [5] [ 9 ].”
BackgroundSymmetric Ciphers Based on Two-Dimensional Chaotic Maps
Fridrich, J. (1998) · International Journal of Bifurcation and Chaos · doi:10.1142/s021812749800098x · Cited by 1,917 · see citing works
Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
Bartschi, A., & Eidenbenz, S. (2020) · 2020 IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce49297.2020.00020 · Cited by 122 · see citing works
Botsinis, P., Ng, S. X., & Hanzo, L. (2013) · IEEE Access · doi:10.1109/access.2013.2259536 · Cited by 64 · see citing works
Freitas da Rocha, A., Pereira, A., & Bezerra Coutinho, F. A. (2001) · Progress in Neurobiology · doi:10.1016/s0301-0082(00)00069-1 · Cited by 41 · see citing works
- Authors
- Brassard, G.
- Affiliations
- The author is at the Université de Montréal, Département d'informatique et de recherche opérationnelle, Montréal, Québec, Canada H3C 3J7.
- Venue
- Science
- Published
- 1997-01-31
- Volume
- 275
- Issue
- 5300
- Pages
- 627-628
- ISSN
- 0036-8075 (ISSN-L)
- 1095-9203
- OpenAlex
- W2079092820
- Cited by
- 103
- References
- 4
- Citations by year
- 2026: 4 · 2025: 5 · 2024: 5 · 2023: 5 · 2022: 5 · 2021: 2 · 2020: 1 · 2019: 2 · 2018: 1 · 2016: 6 · 2015: 5 · 2014: 2 · 2013: 1
- FWCI
- 9.94
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- Science (publishedVersion)
- 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 search, Grover's algorithm, quantum computing, database searching, search algorithms
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
