Classical Verification of Quantum Proofs

Understand

We present a classical interactive protocol that verifies the validity of a quantum witness state for the local Hamiltonian problem.

• It follows from this protocol that approximating the non-local value of a multi-player one-round game to inverse polynomial precision is QMA-hard.
• Our work makes an interesting connection between the theory of QMA-completeness and Hamiltonian complexity on one hand and the study of non-local games and Bell inequalities on the other.