pdf icon
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).