Nice article (and a pretty cool photo) in The Record about my dear friend and collaborator Anne Broadbent.

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?

If you know me personally or follow me on twitter then this may not be a big surprise, but I thought I would repeat the news here, since I am so happy. On the 2^nd of March I asked my wonderful girlfriend Amy to be my wife. I am delighted to say that she agreed!

We haven’t set a date yet, but we are planning to get married in summer 2011. I will post more plans as we make them, in the mean time if you are bored, you can check out our new wedding blog here.