I'm curious, how do the authors use the fact that the number of provers is k>=2? Otherwise one would get (for the special case of k=1 prover) an alternative proof of QIP=IP, which would be pretty amazing.

Also, I think it should be emphasized that QMIP is the class with entanglement (I prefer the name QMIP^*); QMIP has been used before to denote the class without entanglement. Finally, the proof seems to significantly increase the number of rounds, so apparently these results do not apply to one-round games? (I wish they included a clear and precise statement of the transformation they obtain...)

Hi Oded,



The reason that we require at least two provers is that we use the two entangled provers to implement quantum computation "blindly", meaning that they execute a quantum computation without learning anything other than an upper bound on the circuit dimensions. It is still an open question whether this can be done with a single prover, but it seems very unlikely to me and would imply BQP = IP_BQP (which is still open). Thus we can manage any number of provers greater than 1, but the case of QIP is not covered. In fact I believe we mention that whether or not this approach can work for QIP is an open problem.



As regards notation, there seems to be a lot of differing notation for the class we refer to as QMIP, and we simply went with the notation on the complexity zoo (where QMIP potentially has unbounded entanglement). That said, I am aware of at least 2 other forms of notation appearing in the literature.



As regards the number of rounds, our current proof does indeed increase the number of rounds polynomially in the size of the verifiers circuits. While I believe it may be possible to get around this, I don't yet have an explicit proof that it is possible. Even this, however, is unlikely to work in the extreme case of one-round games.

As regards the results we obtain, they are explicitly in the statement of Theorem 1, though I take your point that we should have echoed this in the abstract/introduction/conclusions. We obtain QMIP(k,m,c,s) contained within MIP(k,m',c,s'), where s'=max(s,2^-d) (with d being a security parameter) and m'=m*poly(n,d) where n is the problem size. The polynomial here is linear in the circuit dimensions (and so at least linear in n).

Thanks, Joseph! This is very helpful!

Perhaps to prevent confusion in the future, you might want to add "k >= 2" to the sentence:
"More precisely, we show that for any number k of provers, QMIP[k] = MIP*[k]"
(since you do not show it for k=1)

Also, note that Theorem 1 starts with "If there exists...", and that in order to get the statement above, one probably needs to combine Theorem 1 with Theorem 2 (and perhaps some other stuff).

Regarding notation, it's purely a matter of taste, but I personally find it more logical to have the "Q" indicate quantum communication, and the "*" indicate entanglement (in analogy to MIP^*).

Thanks for the feedback. I'll be sure to tweak the intro as you suggest before it reaches publication anywhere. Feel free to email me if you have any more questions or comments. We certainly welcome the feedback.