Rapid sampling though quantum computing
Lov K. Grover · 2000
This paper extends the quantum search class of algorithms to the multiple solution case.It is shown that, like the basic search algorithm, these too can be represented as a rotation in an appropriately defined two dimensional vector space.This yields new applicationsan algorithm is presented that can create an arbitrarily specified quantum superposition on a space of size N in o(4r-N) steps.By making a measurement on this superposition, it is possible to obtain a sample according to an arbitrarily specified classical probability distribution in O(,f-N) steps.A classical algorithm would need f2(N) steps.