Classical verification of quantum proofs

Publication Type:
Journal Article
Theory of Computing, 2019, 15
Issue Date:
Filename Description Size
699110.pdfPublished Version267.71 kB
Adobe PDF
Full metadata record
© 2019 Zhengfeng Ji. 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.
Please use this identifier to cite or link to this item: