Pulling Out The Quantumness

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 NP^NP ⊆ BPP, the rest is an easy induction. We use the following inclusions.

NP^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.