The study of interactive proofs in the quantum setting has yielded profound insights into complexity theory and quantum information. A curious feature of these results is that the computational advantage of quantum models over their classical counterparts usually stems from entanglement phenomena, rather than from quantum communication with the verifier. For example, it is known that QIP = IP = PSPACE, and that QMIP with unentangled provers is equal to NEXP = MIP; on the other hand, MIP* = RE. We initiate the general study of quantum positional multi-prover interactive proofs, or (Q)PMIPs, in which provers and verifiers positioned in space communicate freely, except for the constraints imposed by the speed of light. We establish a classical–quantum separation by studying the classes of languages decidable by PMIPs and QPMIPs in the no pre-shared entanglement model.
Joint work with Nicholas Spooner, Krishna Agaram
