Volume 15 (2019) Article 5 pp. 1-42
Classical Verification of Quantum Proofs
Revised: March 26, 2018
Published: September 15, 2019
We present a classical interactive protocol that checks the validity of a quantum witness state for the local Hamiltonian problem. It follows from this protocol that approximating the nonlocal value of a multi-player one-round game to inverse polynomial precision is $\textsf{QMA}$-hard. Our result makes a connection between the theory of $\textsf{QMA}$-completeness and Hamiltonian complexity on one hand and the study of nonlocal games and Bell inequalities on the other.