A fast quantum mechanical algorithm for database search
arXiv:quant-ph/9605043
Abstract
Imagine a phone directory containing N names arranged in completely random order. In order to find someone's phone number with a 50% probability, any classical algorithm (whether deterministic or probabilistic) will need to look at a minimum of N/2 names. Quantum mechanical systems can be in a superposition of states and simultaneously examine multiple names. By properly adjusting the phases of various operations, successful computations reinforce each other while others interfere randomly. As a result, the desired phone number can be obtained in only O(sqrt(N)) steps. The algorithm is within a small constant factor of the fastest possible quantum mechanical algorithm.
8 pages, single postscript file. This is an updated version of a paper that was originally presented at STOC 1996. The algorithm is the same; however, the proof has been simplified by using a new interpretation termed "inversion about average." Also a few recently discovered insights have been added. Journal Ref.: Proceedings, 28th Annual ACM Symposium on the Theory of Computing (STOC), May 1996, pages 212-219
Cited by in corpus (15)
- Quantum Software Engineering: Roadmap and Challenges Ahead
- Quantum anomaly detection in the latent space of proton collision events at the LHC
- Quantum Computation Beyond the Circuit Model
- Quantum algorithms with local particle number conservation: noise effects and error correction
- Can quantum computing solve classically unsolvable problems?
- Device-Independent Quantum Secure Direct Communication Under Non-Markovian Quantum Channels
- Qibolab: an open-source hybrid quantum operating system
- Dancing the Quantum Waltz: Compiling Three-Qubit Gates on Four Level Architectures
- A quantum algorithm for solving 0-1 Knapsack problems
- Qompress: Efficient Compilation for Ququarts Exploiting Partial and Mixed Radix Operations for Communication Reduction
- Quantum Pathways for Charged Track Finding in High-Energy Collisions
- Span-program-based quantum algorithm for evaluating unbalanced formulas
- Localization of space-inhomogeneous three-state quantum walks
- Quantum Computation
- Quantum counting, and a relevant sign