<p>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...</p>

<p>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.</p>

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

CC BY-SA 2.5
2010-11-02T23:53:50.223Z
2010-11-02T23:53:50.223Z
John Watrous
<p>The answers of John Watrous and Andy Drucker are excellent for understanding some of the issues involved.</p>

<p>I'll just add to Andy's answer that, not only is no such implication known, but <em>showing such an implication requires non-relativizing techniques</em> (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).  </p>

<p>We know that $IP = PSPACE$ doesn't relativize, but it does <a href="http://dx.doi.org/10.1145/1490270.1490272">algebrize</a>.  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. </p>

<p>[1] L. Fortnow and J. Rogers. <a href="http://dx.doi.org/10.1006/jcss.1999.1651">Complexity limitations on quantum computation</a>. 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 <a href="http://www.cs.uchicago.edu/~fortnow/papers/quantum.pdf">here</a>.</p>

CC BY-SA 2.5
2010-11-03T01:41:11.817Z
2010-11-03T01:41:11.817Z
Joshua Grochow
<p>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.</p>

<p>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. </p>

<p>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.</p>

CC BY-SA 2.5
2010-11-04T06:52:23.640Z
2010-11-04T06:52:23.640Z
Joe Fitzsimons
<p>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... </p>

<p>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.  </p>

<p>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 <em>period</em> 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 <a href="http://portal.acm.org/citation.cfm?id=606909" rel="noreferrer">survey</a> on query complexity for this last point.)</p>

<p>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, <em>specifically</em> in the context of interaction with computationally-unbounded provers.</p>

CC BY-SA 2.5
2010-11-02T18:46:30.863Z
2010-11-02T18:46:30.863Z
Andy Drucker
<p>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...</p>

<p>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?</p>

CC BY-SA 2.5
2010-11-02T19:38:49.527Z
I changed “PSPACE(IP)” in the title to “PSPACE (= IP)” because “A(B)” is a less common way to denote the class “$A^B$.”
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-02T19:50:48.503Z
By the way, strictly speaking, I think that your intuition is based on the direction QIP(3)⊇PSPACE, which was known in 1999: [Watrous 2003](http://dx.doi.org/10.1016/S0304-3975%2801%2900375-9), http://arxiv.org/abs/cs.CC/9901015.  In fact, that is the first paper discussing quantum interactive proofs.
Tsuyoshi Ito
<cc.complexity-theory><quantum-computing><space-bounded><conditional-results><interactive-proofs>
If P = BQP, does this imply that PSPACE (= IP) = AM?
Zelah 02
# If P = BQP, does this imply that PSPACE (= IP) = AM?

(Asked by: username_0 on 2010-11-02)

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?

**Tags:** cc.complexity-theory, quantum-computing, space-bounded, conditional-results, interactive-proofs

> **Comments:**
> **username_1**: I changed “PSPACE(IP)” in the title to “PSPACE (= IP)” because “A(B)” is a less common way to denote the class “$A^B$.”  
> **username_1**: By the way, strictly speaking, I think that your intuition is based on the direction QIP(3)⊇PSPACE, which was known in 1999: [Watrous 2003](http://dx.doi.org/10.1016/S0304-3975%2801%2900375-9), http://arxiv.org/abs/cs.CC/9901015.  In fact, that is the first paper discussing quantum interactive proofs.  

---

## 4 answers

### Answer by username_5 on 2010-11-02. Score: 18 | Accepted answer

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](http://portal.acm.org/citation.cfm?id=606909) 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 by username_2 on 2010-11-02. Score: 16

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 by username_3 on 2010-11-03. Score: 11

The answers of username_2 and username_5 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](http://dx.doi.org/10.1145/1490270.1490272). 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](http://dx.doi.org/10.1006/jcss.1999.1651). 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](http://www.cs.uchicago.edu/~fortnow/papers/quantum.pdf).


---

### Answer by username_4 on 2010-11-04. Score: 6

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.


---

