QIP = PSPACE

Efficient proof verification is a fundamental notion in theoretical computer science, where an all powerful prover tries to convince a verifier that a proof of a certain hypothesis is correct. The prover can do anything but the verifier can only run an efficient procedure (called the verification process) such that if the proof is correct, then the verifier always accepts and if the proof is incorrect, then the verifier accepts with very small probability. The interactive proof system is one of the several models of computation based on the notions of proof verification where a resource bounded verifier interacts with an all powerful prover with the objective of verifying whether a purported proof is correct or not. It is known that the class of computational problems having an interactive proof system (denoted $\mathsf{IP}$) is precisely the class of problems that can be solved using polynomial space on a classical computer (denoted $\mathsf{PSPACE}$). In other words, \[ \mathsf{IP} = \mathsf{PSPACE}. \] The quanutm variant of interactive proof systems is defined similarly except that the prover and the verifier are allowed to exchange and process quantum information. For the past decade, it was known that the class of computational problems that admit a quantum interactive proof system (denoted $\mathsf{QIP}$) contains the class of problems in $\mathsf{IP}$. In computer science terms, $\mathsf{IP} = \mathsf{PSPACE} \subseteq \mathsf{QIP}$. In this talk, I will show that the other containment also holds. That is, any computational problem that admits a quantum interactive proof system also admits a classical interactive proof system. This establishes that efficient quantum verification is equivalent to efficient classical verification and hence providing an alternate characterization of $\mathsf{PSPACE}$ from the quantum information perspective: \[ \mathsf{QIP} = \mathsf{PSPACE}. \] This is a joint work with Rahul Jain (National University of Singapore), Zhengfeng Ji (Perimeter Institute for Theoretical Physics), and John Watrous (University of Waterloo).