Thursday, September 04, 2014

Favorite Theorems: Quantum Interactive Proofs

Practical quantum computing still has many hurdles to jump through, but the quantum computing model does generate great complexity questions and often surprising answers.
QIP = PSPACE by Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay and John Watrous. 
QIP is the quantum analogue of interactive proof systems. Since IP = PSPACE we get the consequence QIP = IP, that quantum doesn't give an advantage over classical randomness in the interactive proof model. I wouldn't read too much into that interpretation, more that we have a strange situation where IP is far more powerful than we initially suspected and that QIP is weaker than expected and so we get the collision at PSPACE.

QIP ⊇ PSPACE follows from IP = PSPACE. In an earlier paper, Kitaev and Watrous show QIP ⊆ EXP by reducing QIP to an exponential-sized semi-definite program. This papers applies a clever matrix multiplicative weight algorithm to approximate a subclass of SDPs to achieve QIP ⊆ PSPACE.

We've also seen progress on QMIP, quantum interactive proof with multiple entangled provers who cannot otherwise communicate. QMIP containing MIP=NEXP remained open for a long time because the provers might use entanglement to cheat. Ito and Vidick show that entangled provers can't get an advantage on the multilinear test used in the original MIP=NEXP paper, and thus QMIP does contain NEXP. QMIP contained in NEXP remains open.

1 comment:

  1. See also Quantum Multiprover Interactive Proofs with Communicating Provers. Even if the provers have a classical communication channel, but the verifier sends quantum messages, it still contains NEXP.