Classical veriﬁcation of quantum proofs
- Publication Type:
- Journal Article
- Theory of Computing, 2019, 15
- Issue Date:
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is new to OPUS and is not currently available.
© 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: