Relationship between MIP*[$\log(n),O(1)$] and NP

Question

MIP* is the multi-prover interactive proof system where provers can share arbitrary many entanglements. My question is what is the relationship between MIP*[$\log(n),O(1)$] and NP? MIP*[$\log(n),O(1)$] means the question length is $\log(n)$ and the answer length is constant. The second question is that are there any results about the relationship between MIP*[$\log(n),O(1)$] with 2 players 1 round and NP?

From the classical PCP theorem we have $MIP[\log(n),O(1)]=NP$ and for MIP*[$\log(n),O(1)$] system ,the honest provers can use classical strategy and the problem is how to prevent the provers from cheating.

Due to the game version of QPCP conjecture, I believe that MIP∗[log(),(1)] should be very large( possibly something like QMA or even RE), but I haven't found references explicitly showing that it contains NP.

Answer 1

What you are asking about is closely related to the "games version" of the Quantum PCP Conjecture, a significant open problem in quantum complexity theory.

As mentioned in the comments, it was not known if entanglement (without communication) would help provers, and it was a nontrivial result of Ito and Vidick that MIP$^*\supset $ MIP=NEXP.

On the other hand, by some improvements to the landmark result of Ji-Natarajan-Vidick-Wright-Yuen by Dong-Fu-Natarajan-Qin-Xu-Yao and Fu-Zhang, it's now claimed (see https://arxiv.org/abs/2503.04517) that $$\text{MIP}^*[\text{polylog}(n),O(1)]=\text{RE}.$$ Furthermore, it's well known that $\text{RE}\supsetneq \text{NP}$. The separation is obviously strict because, unlike NP, RE contains undecidable problems. This already suggests that $\text{MIP}^*[\text{log}(n),O(1)]$ is considerably more powerful than NP. Furthermore, several experts suspect that with some work, the question size in the MIP$^*$ protocol can be further reduced to $O(\text{log}(n))$ while still yielding RE (see, for instance, https://arxiv.org/abs/2403.13084).

To many folks, the ''correct'' quantum analogue of NP is the complexity class QMA. In 2018, Natarajan and Vidick purported that $\text{QMA}\subseteq \text{MIP}^*[\text{log}(n),\text{log}(n)]$, but their proof turned out to have an error, and the containment remains open. It's worth remarking that although QMA$\subset$ RE, even if $\text{MIP}^*[\text{log}(n),O(1)]$ does equal RE (and thus contains QMA trivially), we won't have solved the games' version of the quantum PCP conjecture due to some very nontrivial technicalities involving the complexity of honest provers (the interested reader should consult https://arxiv.org/abs/2403.13084).

It's also worth mentioning that a recent result of Dong, Fu, Natarajan, Qin, Xu, and Yao shows that $\text{MIP}_{noisy}^*[\text{log}(n),O(1)]\subseteq \text{NP}$, where $\text{MIP}_{noisy}^*$ is the complexity class $\text{MIP}^*$ but the entangled states have a certain type of noise (small defects). The details are in the work https://arxiv.org/abs/2312.04360.

Note: everything I have stated is in the case of 2-prover, one round MIP and MIP$^*$ protocols with constant soundness parameters and perfect completeness. There are likely other results in the case where these parameters are allowed to differ.