Tuesday, January 26, 2016

searching a database?

wikipedia |  Grover's algorithm is a quantum algorithm that finds with high probability the unique input to a black box function that produces a particular output value, using just O(N1/2) evaluations of the function, where N is the size of the function's domain.
The analogous problem in classical computation cannot be solved in fewer than O(N) evaluations (because, in the worst case, the Nth member of the domain might be the correct member). At roughly the same time that Grover published his algorithm, Bennett, Bernstein, Brassard, and Vazirani published a proof that no quantum solution to the problem can evaluate the function fewer than O(N1/2) times, so Grover's algorithm is asymptotically optimal.[1]
Unlike other quantum algorithms, which may provide exponential speedup over their classical counterparts, Grover's algorithm provides only a quadratic speedup. However, even quadratic speedup is considerable when N is large. Grover's algorithm could brute force a 128-bit symmetric cryptographic key in roughly 264 iterations, or a 256-bit key in roughly 2128 iterations. As a result, it is sometimes suggested that symmetric key lengths be doubled to protect against future quantum attacks.
Like many quantum algorithms, Grover's algorithm is probabilistic in the sense that it gives the correct answer with a probability of less than 1. Though there is technically no upper bound on the number of repetitions that might be needed before the correct answer is obtained, the expected number of repetitions is a constant factor that does not grow with N.
Grover's original paper described the algorithm as a database search algorithm, and this description is still common. The database in this analogy is a table of all of the function's outputs, indexed by the corresponding input.