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
Revised: March 26, 2018
Published: September 15, 2019
Keywords: quantum interactive proofs, local Hamiltonian problem, nonlocal games, entanglement, Bell inequalities
Categories: quantum computing, interactive proofs, quantum interactive proofs, Hamiltonian, 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).
Licensed under a Creative Commons Attribution License (CC-BY)