arXiv:quant-ph/9605043quant-ph
A fast quantum mechanical algorithm for database search
Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.
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.
After quickly reading through the paper it seems that the algorithm they employ is very similar to Grover search [1], which provides a quadratic/square-root speed-up for generic search problems, so O(2^m) -> O(2^(n/2)). Basically, they perform the following three steps: 1)…
ThePhysicistView on HNParent context