Volume 15 (2019) Article 5 pp. 1-42
Classical Verification of Quantum Proofs
Received: January 30, 2017
Revised: March 26, 2018
Published: September 15, 2019
Download article from ToC site:
[PDF (391K)]    [PS (2367K)]    [PS.GZ (460K)]
[Source ZIP]
Keywords: quantum interactive proofs, local Hamiltonian problem, nonlocal games, entanglement, Bell inequalities
ACM Classification: F.1.2, F.1.3
AMS Classification: 68Q10, 68Q12, 81P40, 81P68

Abstract: [Plain Text Version]

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.

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

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