It is well-known that $\mathsf{MIP} = \mathsf{NEXPTIME}$, and recently there was a breakthrough stating that $\mathsf{MIP^*} = \mathsf{RE}$.

This was very confusing because it seemed like the (malicious) provers should become more powerful about fooling the verifier, for the provers was equipped with a new toy, namely quantum entanglement.

My intuition was this: Since quantum entanglement cannot be used for communication anyway, the correlation is actually restricting what the provers observe.

Still, if that's the case, couldn't the provers simply ignore what the toy gives?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.