Anand Natarajan, Chinmay Nirkhe (Mar 21 2024).
Abstract: In classical complexity theory, the two definitions of probabilistically checkable proofs – the constraint satisfaction and the nonlocal games version – are computationally equal in power. In the quantum setting, the situation is far less clear. The result MIP* = RE of Ji et. al. (arXiv:2001.04383) and refinements by Natarajan and Zhang (arXiv:2302.04322) show that multiprover interactive proof systems with polylogarithmically long messages can solve any decision problem in RE, including undecidable problems like the halting problem. These results show that any connection between the “constraint satisfaction” or “Hamiltonian” quantum PCP conjecture and nonlocal games must involve restricting the players in the game to be computationally efficient. This note contains two main results: (1) we give a “quantum games PCP for AM” in the form of a new construction of a succinct MIP* protocol with efficient provers for the canonical AM-complete problem, and (2) we explain an error in the energy amplification procedure of Natarajan and Vidick (arXiv:1710.03062) which invalidates their claim to have constructed a quantum games PCP for a QMA-complete problem. In surveying the obstacles remaining towards a quantum games PCP for QMA, we highlight the importance and challenge of understanding gap amplification for Hamiltonians even when locality is replaced by much weaker constraints, such as bounds on the “Pauli spectrum” of the Hamiltonian. We hope these questions will motivate progress towards new “baby versions” of Hamiltonian quantum PCP conjecture.