Conjecture about Complexity of a Quantum Computation Algorithm
tu...@ar-tiste.com
Aaronson:
"The learnability of Quantum States", talk qiven at MIT, Cambridge, MA,
May 15, 2006; University of Washington, Seattle, May 25, 2006
(www.scottaaronson.com/talks/learn.ppt)
Abstract for talk: "Traditional quantum state tomography requires a
number of measurements that grows exponentially with the number of
qubits n. But using ideas from computational learning theory, I'll show
that "for most practical purposes" one can learn a state using a number
of measurements that grows only linearly with n, and polynomially with
certain error parameters. I'll then give two applications of this
learning theorem to quantum computing: first, the use of trusted
classical advice to verify untrusted quantum advice, and second, a new
simulation of quantum one-way protocols. Even though there exists an
algorithm to learn a quantum state after a small number of
measurements, that algorithm might not be efficient computationally. As
time permits, I'll discuss ongoing work on how to exploit that fact to
copy-protect and obfuscate quantum software."
I have an algorithm(http://arxiv.org/abs/quant-ph/0004028)for using
quantum computers to perform classical Bayesian Net calculations. I
conjecture that complexity theory techniques similar to those used by
Scott in his talk can be used to bound the complexity of my algorithm.
I conjecture that we will find that a quantum computer can do
classical Bayesian Net calculations, with a small error epsilon>0 in
the final answer, with a small probability delta>0 of getting the wrong
final answer, by performing a number of operations=polynomial(number
of qubits). I conjecture that doing the same calculation on a classical
computer would require a number of operations= exp(number of qubits).
I don't have time to prove my conjecture in the immediate future. If
someone proves it before I do, I will be elated. Otherwise, I will try
to prove it myself once I get some free time.
R.R. Tucci