This paper defines and characterizes a new form of quantum multi-prover interactive proof system. The authors consider a quantum verifier who can interact with multiple unentangled quantum provers. The twist is that the provers are allowed to exchange unlimited amounts of classical communication. Even so, the authors show that such a proof system can still recognize languages in NEXP. This is a wonderful result: the model is novel, the outcome is surprising, and there are some nice ideas used to devise the protocol.

The result probably also has implications for quantum information processing. There are a number of situations where one would like to find the optimal protocol for some task using LOCC (local operations with classical communication), e.g., LOCC state discrimination, entanglement distillation. The sentiment in the community is that these problems are difficult, and the result in this paper is a first indication as to why. I'm not aware of earlier work about the classical complexity of finding an optimal LOCC protocol.

The main idea is start with classical 2-prover proof system for NEXP and to modify it so that the verifier asks the questions from the classical proof system in superposition with fake questions, the answers of which he doesn't actually care about. To gain classical information about what the questions are, a prover would have to decohere the superposition, and the verifer can detect this.