If P = BQP, does this imply that PSPACE (= IP) = AM?

Question

Recently, Watrous et al proved that QIP(3) = PSPACE a remarkable result. This was a surprising result to myself to say the least and it set me off thinking...

I wondered what if Quantum Computers could be efficiently simulated by Classical Computers. Could this be SIMPLY related to the Divide between IP and AM? What I mean is that IP is characterized by Polynomial number of rounds of classical interaction, while AM has 2 rounds of classical interaction. Could simulating a Quantum Computing reduced the amount of interaction for IP from polynomial to a constant value?

Answer 1

Great question! Short answer: no implication like $$ \mathsf{P} = \mathsf{BQP} \Rightarrow \mathsf{IP} = \mathsf{AM} $$ is known; but that doesn't mean it's not worth trying to prove...

I would say, though, that finding such an implication seems unlikely. I think the message of much quantum complexity theory is that, while quantum computers are not an all-purpose panacea for solving hard problems, they can be much more powerful than classical computers in certain specific circumstances.

For example, in query complexity, quantum algorithms can efficiently solve certain problems classical ones provably cannot, when the input is promised to obey some nice global structure. E.g., Shor's algorithm is based on an algorithm to quickly find the unknown period of a function promised to be periodic. On the other hand, quantum query algorithms are not too much stronger than classical ones for solving problems in which there is no special structure assumed on the input. (See Buhrman and de Wolf's survey on query complexity for this last point.)

Similarly, I think the results $\mathsf{QIP}(3) = \mathsf{QIP} = \mathsf{IP}$ tell us, not that interaction is unexpectedly weak (even if $\mathsf{P} = \mathsf{BQP}$), but that quantum computation is unexpectedly strong, specifically in the context of interaction with computationally-unbounded provers.

Answer 2

I agree with what Andy has written and I wanted this "answer" to be a comment to his answer, but it is evidently too long for a comment...

Anyway, it may be helpful to say something more about what aspect of quantum computation (or perhaps quantum information) allows for the containment of PSPACE in QIP(3) to be proved. Known proofs of this containment do not follow from the verifier's ability to compute functions that happen to be quantum polynomial-time computable. A more accurate explanation is that the proofs make use of the specific ways that a prover can manipulate entangled quantum states it shares with the verifier. If the prover were not able to manipulate quantum information, or if it could somehow magically manipulate shared entangled states in a stronger way than quantum information theory allows, the proofs would not work.

So, in my view the containment of PSPACE in QIP(3) says nothing about the relationship between AM and PSPACE.

Answer 3

The answers of John Watrous and Andy Drucker are excellent for understanding some of the issues involved.

I'll just add to Andy's answer that, not only is no such implication known, but showing such an implication requires non-relativizing techniques (of which essentially only one--arithmetization--is known). Lance Fortnow and John Rogers [1] constructed an oracle where $P = BQP$ but $PH$ is infinite (and in particular that means $PSPACE \supseteq PH \supset\neq AM$ in such a world).

We know that $IP = PSPACE$ doesn't relativize, but it does algebrize. I do not know if the Fortnow--Rogers result shows (or can be extended to show) that such an implication would require non-algebrizing techniques.

[1] L. Fortnow and J. Rogers. Complexity limitations on quantum computation. Journal of Computer and System Sciences, 59(2):240-252, 1999. Special issue for selected papers from the 13th IEEE Conference on Computational Complexity. Also available here.

Answer 4

The other answers are excellent, and this is not meant to replace or contradict any of them, merely to offer some intuition for why P=BQP does not necessarily imply equality between quantum and classical interactive proof systems (for fixed rounds etc.). We do now, however, know that QIP=IP thanks to the work of Jain, Ji, Upadhyay and Watrous, so I am certainly not trying to claim that such equalities never happen.

If we only assume that P=BQP then we learn something only about the which decision problems can be answered by the quantum and classical models. It is not the same as implying that the models are actually the same. The main difference is that quantum computers can process states in superposition, which means that their input and output need not be restricted to classical states. This is a very important difference between quantum and classical models, since the quantum input/output makes it possible to query oracles with superpositions of classical states or to communicate quantum states (which may potentially have exponential classical descriptions) between a verifier and prover. Indeed, oracles do exist which separate BQP from P, and quantum communication leads to reduced communications complexity for a number of problems. Thus, the quantum model is strictly more powerful than having a classical computer supplemented with an oracle for BQP: A quantum computer can do everything a classical computer can do, but a classical computer cannot do everything a quantum computer can do.

For this reason, the question of whether P=BQP is not the deciding factor in whether quantum and classical models are equal in situations which make use of communication/oracle queries.