# Quantum Bayesian Networks

## September 17, 2010

### Early Failures in the History of Quantum Sampling

Filed under: Uncategorized — rrtucci @ 5:35 pm

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 $P(x)$ 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 $N_B + 1$ qubits, with a starting state:

$|s'\rangle = |0^{N_B}\rangle\otimes|0\rangle$

and a target state

$|t\rangle = \frac{1}{\sqrt{2^{N_B}}}\sum_{x\in\{0,1\}^{N_B}}|x\rangle\otimes\left(\sqrt{P(x)}|0\rangle + \sqrt{1 - P(x)}|1\rangle\right)$

Once this starting state is steered to this target state, one measures the target state to sample $P(x)$. A serious problem with this method is that such a target state is useless for sampling $P(x)$, because it has a vanishingly small amplitude of size $O(1/\sqrt{2^{N_B}})$ for all $x$. Quibbs does not suffer from this defect because its target state is

$|t\rangle = \sum_{x\in\{0,1\}^{N_B}}\sqrt{P(x)}|x\rangle\otimes|0\rangle$

Thus, Quibbs’ target state has a finite amplitude at those $x$ for which $P(x)$ is finite.

ACHTUNG: (added on Oct. 11) This blog post is a scurrilous lie. See retraction here.