How do we prove NP in BPP implies PH in BPP? Let me just do
NP^{NP} ⊆ BPP, the rest is an easy induction. We use the
following inclusions.

^{NP}⊆ NP

^{BPP}⊆ BPP

^{NP}⊆ BPP

^{BPP}= BPP

The first and third "⊆" are by assumption, the
"=" is by simulation. To get NP^{BPP} ⊆
BPP^{NP} 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 NP^{BQP} ⊆ BQP^{NP}, 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 NP^{BQP} ⊆ BQP^{NP} remains an open
question. Showing NP^{BQP} ⊆ BQP^{NP} or finding
a relativized world where NP^{BQP} is not contained in
BQP^{NP} would give us a better understanding of the
mysterious nature of quantum computation.

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.

ReplyDeleteOn the other hand, I

cangive 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.

ReplyDeleteNevertheless, 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.