<p>Consider two complexity classes, say P and NP. To show that a proof that P=NP would need non-relativizing techniques, one has to describe an oracle relative to which the classes are not equal. For this the usual approach is to take an exponential separation between deterministic and non-deterministic query complexity and then use a standard argument to turn this into the oracle separation.</p>

<p>For algebrization one needs the stronger statement that even if the weaker class (here P) is given access to the polynomial extension of the oracle the classes remain different. Aaronson and Wigderson give some direct constructions for that, but the easiest argument is that a separation in communication complexity (e.g. an exponential separation between deterministic and non-deterministic communication complexity) can take the place of the query complexity separation. Compare Theorem 4.11 in the algebrization paper.</p>

<p>Of course many such separations are known (e.g. non-disjointness is easy for non-deterministic protocols but hard for deterministic protocols).
The separation that is left open in our paper is QCMA- vs. QMA-communication complexity (in the two-way model). Giving an exponential separation would immediately imply that any proof that QMA=QCMA (for Turing machines) would need non-algebrizing techniques (of course this inclusion might not be true).</p>

<p>Again, the reasoning here is that an algebrizing proof of QCMA=QMA would (by definiton) also work for the algebraic oracle model (for any oracle) and algorithms in this one could be simulated in the communication complexity model, contradicting a separation result there.</p>

CC BY-SA 3.0
2014-12-16T10:19:02.410Z
2014-12-16T10:19:02.410Z
Hartmut Klauck
<p>First my background about computational complexity is still beginner. </p>

<p>Recent paper published by Klauck and Podder <a href="http://arxiv.org/abs/1402.4312" rel="noreferrer">[KP14]</a> show that for the first time an exponential gap between computing partial Boolean functions in a QCMA and QMA in communication model. However, Aharonov and Naveh <a href="http://arxiv.org/abs/quant-ph/0210077" rel="noreferrer">[AN02]</a> conjecture that QMA = QCMA in the Turing model. </p>

<p>[KP14] state the following open problem:
<img src="https://i.sstatic.net/hdTjV.png" alt="enter image description here"></p>

<p>Thus, in order to show that QCMA = QMA; we need nonalgebrizing techniques. </p>

<p>I just don't understand how they relate the communication model with the Turing model? </p>

<p>According to my understanding is that communication model is different than Turing model. that is, we have different results, proofs, etc. therefore, [KP14] argue that any separation in the two-way communication model would imply using non-algebrizing techniques, how could it be?</p>

<p>thanks in advance</p>

CC BY-SA 3.0
2014-12-12T15:55:26.457Z
What they are saying would follow if any proof that QCMA = QMA in the Turing model ***that uses algebrizable techniques*** would also apply to the communication complexity model. I don't see why this is true, but maybe somebody else will explain it. Anyway, it doesn't contradict the fact that the two models are different.
Peter Shor 
CC BY-SA 3.0
2014-12-14T06:01:45.910Z
@PeterShor Thanks, you just make me understand the question much better;
YOUSEFY
<cc.complexity-theory><quantum-computing><communication-complexity>
The relationship between QCMA and QMA in the Turing and Communication model
YOUSEFY
# The relationship between QCMA and QMA in the Turing and Communication model

(Asked by: username_0 on 2014-12-12)

First my background about computational complexity is still beginner.

Recent paper published by Klauck and Podder [[KP14]](http://arxiv.org/abs/1402.4312) show that for the first time an exponential gap between computing partial Boolean functions in a QCMA and QMA in communication model. However, Aharonov and Naveh [[AN02]](http://arxiv.org/abs/quant-ph/0210077) conjecture that QMA = QCMA in the Turing model.

[KP14] state the following open problem:
![enter image description here](https://i.sstatic.net/hdTjV.png)

Thus, in order to show that QCMA = QMA; we need nonalgebrizing techniques.

I just don't understand how they relate the communication model with the Turing model?

According to my understanding is that communication model is different than Turing model. that is, we have different results, proofs, etc. therefore, [KP14] argue that any separation in the two-way communication model would imply using non-algebrizing techniques, how could it be?

thanks in advance

**Tags:** cc.complexity-theory, quantum-computing, communication-complexity
> **Comments:**
> **username_1**: What they are saying would follow if any proof that QCMA = QMA in the Turing model ***that uses algebrizable techniques*** would also apply to the communication complexity model. I don't see why this is true, but maybe somebody else will explain it. Anyway, it doesn't contradict the fact that the two models are different.  
> **username_0**: @PeterShor Thanks, you just make me understand the question much better;  

---

## 1 answers

### Answer by username_2 on 2014-12-16. Score: 4 | Accepted answer

Consider two complexity classes, say P and NP. To show that a proof that P=NP would need non-relativizing techniques, one has to describe an oracle relative to which the classes are not equal. For this the usual approach is to take an exponential separation between deterministic and non-deterministic query complexity and then use a standard argument to turn this into the oracle separation.

For algebrization one needs the stronger statement that even if the weaker class (here P) is given access to the polynomial extension of the oracle the classes remain different. Aaronson and Wigderson give some direct constructions for that, but the easiest argument is that a separation in communication complexity (e.g. an exponential separation between deterministic and non-deterministic communication complexity) can take the place of the query complexity separation. Compare Theorem 4.11 in the algebrization paper.

Of course many such separations are known (e.g. non-disjointness is easy for non-deterministic protocols but hard for deterministic protocols).
The separation that is left open in our paper is QCMA- vs. QMA-communication complexity (in the two-way model). Giving an exponential separation would immediately imply that any proof that QMA=QCMA (for Turing machines) would need non-algebrizing techniques (of course this inclusion might not be true).

Again, the reasoning here is that an algebrizing proof of QCMA=QMA would (by definiton) also work for the algebraic oracle model (for any oracle) and algorithms in this one could be simulated in the communication complexity model, contradicting a separation result there.


---

