If you have heard me talk in the last couple of months you may know that I have been working on trying to characterize the power of quantum interactive proofs with multiple provers. Well, I am delighted to say that our paper is finally on the arXiv here. I am quite chuffed with it since it is the first time I have been able to use an equation as the title of a paper, and is also the first time one of my results can be neatly captured by a single simple equation. Some how I feel it lends me more cred as a theorist!

Recently Jain, Ji, Upadhyay and Watrous proved the rather amazing result (here) that interactive proofs with quantum verifiers can only prove problems in PSPACE, and so are identical in power to interactive proofs with classical verifiers. Our result proves an equivalent statement for interactive proofs with more than one prover, basically showing that any interactive proof with potentially entangled (but non-communicating) provers can be simulated using only a classical verifier and some extra entanglement. The case for non-entangled provers had previously been proved by Kobayashi and Matsumoto (here).

Taken together these three results show something interesting, and quite counter intuitive: the availability of quantum verifiers does not change the power of any interactive proof system. Now, this result doesn’t necessarily hold when we fix the number of rounds (our MIP* protocols requires polynomially more rounds than than the equivalent QMIP protocol), but I find the symmetry in these three results pretty remarkable.

As Oded Regev pointed out to me on SciRate, some authors have used QMIP* to denote the quantum equivalent of MIP* and QMIP to denote the quantum equivalent of MIP. Although we were aware of this, there are at least two conflicting notations used, and we simply followed the convention used on the Complexity Zoo, to try to minimize confusion. One nice property of the notation Oded suggests, however, is that the three results mentioned above can be expressed as:

1. QIP=IP
2. QMIP=MIP
3. QMIP*=MIP*

Neat, no? So, how should I feel about QMA now?

This entry was posted on Thursday, April 15th, 2010 at 12:16 am and is filed under Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.