This work is licensed under a
Creative Commons License.
|
Tuesday, December 20, 2005
Pulling Out The Quantumness
Posted by Lance
A recent comment made the mistaken assumption that if NP is in BQP (efficient quantum algorithms) then the whole polynomial-time hierarchy lies in BQP. We do know if NP is in BPP (efficient probabilistic algorithms) then PH is in BPP. Why the proof doesn't work for BQP illustrates an interesting difference between probabilistic and quantum computation.How do we prove NP in BPP implies PH in BPP? Let me just do NPNP ⊆ BPP, the rest is an easy induction. We use the following inclusions.
NPNP ⊆ NPBPP ⊆ BPPNP ⊆ BPPBPP = BPP The first and third "⊆" are by assumption, the "=" is by simulation. To get NPBPP ⊆ BPPNP we first make the error of the BPP algorithm so small that a randomly chosen string will give, with high probability, the correct answer for every query made on every computation path of the NP algorithm. We can then safely pick a random string r first and then make an NP query that simulates the NP algorithm which will use r to simulate the BPP queries.
Now suppose we wanted to show NP in BQP implies PH in BQP. We just need to show NPBQP ⊆ BQPNP, the rest works as before. Like the BPP case we can make the error of the BQP algorithm very small, but we have no quantum string that we can choose ahead of time. In probabilistic algorithms we can pull out randomness and leave a deterministic algorithm with a random input but we don't know any way to pull the quantumness, even with quantum bits, out of a quantum algorithm.
Whether NPBQP ⊆ BQPNP remains an open question. Showing NPBQP ⊆ BQPNP or finding a relativized world where NPBQP is not contained in BQPNP would give us a better understanding of the mysterious nature of quantum computation.
9:48 AM
# 2 comments
-
You ask whether there's an oracle relative to which NP^BQP is not in BQP^NP. Isn't NP^(AM intersect coAM) just the same as AM? If so, then there's a very good reason why this problem is hard: if BQP is in AM, then NP^BQP is in AM is in BQP^NP. Therefore any such oracle would also yield an oracle relative to which BQP is not in AM.
On the other hand, I can give an oracle relative to which BQP^NP and even P^NP are not in NP^BQP. :) (ODDMAXBIT.)
-
Quantum zero-knowledge proofs have to deal with this issue, as well. One of the most popular techniques for constructing a simulator to show a protocol is zero-knowledge is "rewinding" : that is, we fix the random string used by a cheating verifier and restart the verifier whenever anything goes "wrong" in the attempted simulation. Then we can try again; because the random string is fixed, we know that so long as the simulator gives the cheating verifier the same messages, it will have the same answers. Then we can look for the "right" place to answer differently on the new run. With a quantum cheating verifier, you can't do this.
Nevertheless, there is some recent progress on quantum zero-knowledge proofs. It's a long shot, but maybe that'd be worth looking at in the context of this question.
Links to this post:
Weblog Home
Archives
