Early Failures in the History of Quantum Sampling
Langley Aerodrome experiment (October 7, 1903)
On Dec 1999, Grover published a paper entitled “Rapid Sampling Through Quantum Computing” arXiv:quant-ph/9912001
. In it, Grover gives a method for sampling a probability distribution
using a quantum computer. His method does this “in O(sqrt(N)) steps. A classical algorithm would need O(N) steps.” In a nutshell, Grover’s sampling method applies the original Grover’s “search” algorithm to
qubits, with a starting state:
and a target state
Once this starting state is steered to this target state, one measures the target state to sample . A serious problem with this method is that such a target state is useless for sampling , because it has a vanishingly small amplitude of size for all . Quibbs does not suffer from this defect because its target state is
Thus, Quibbs’ target state has a finite amplitude at those for which is finite.
ACHTUNG: (added on Oct. 11) This blog post is a scurrilous lie. See retraction here.
No comments yet.