Theory of Computing
-------------------
Title     : Classical Verification of Quantum Proofs
Authors   : Zhengfeng Ji
Volume    : 15
Number    : 5
Pages     : 1-42
URL       : https://theoryofcomputing.org/articles/v015a005

Abstract
--------

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
QMA-hard. Our result makes a connection between the theory of
QMA-completeness and Hamiltonian complexity on one hand and
the study of nonlocal games and Bell inequalities on the other.

----------------

An extended abstract of this paper appeared in the Proceedings
of the 48th annual ACM Symposium on Theory of Computing (STOC'16).