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.


Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Blog at WordPress.com.

%d bloggers like this: