First my background about computational complexity is still beginner.

Recent paper published by Klauck and Podder [KP14] 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] conjecture that QMA = QCMA in the Turing model.

[KP14] state the following open problem: enter image description here

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

  • 2
    $\begingroup$ 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. $\endgroup$ Dec 12, 2014 at 15:55
  • $\begingroup$ @PeterShor Thanks, you just make me understand the question much better; $\endgroup$
    Dec 14, 2014 at 6:01

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.