Constant-Soundness Interactive Proofs for Local Hamiltonians

Understand

$ \newcommand{\Xlin}{\mathcal{X}} \newcommand{\Zlin}{\mathcal{Z}} \newcommand{\C}{\mathbb{C}} $We give a quantum multiprover interactive proof system for the local Hamiltonian problem in which there is a constant number of provers, questions are classical of length polynomial in the number of qubits, and answers are of constant length.

• The main novelty of our protocol is that the gap between completeness and soundness is directly proportional to the promise gap on the (normalized) ground state energy of the Hamiltonian.
• This result can be interpreted as a concrete step towards a quantum PCP theorem giving entangled-prover interactive proof systems for QMA-complete problems.
• The key ingredient is a quantum version of the classical linearity test of Blum, Luby, and Rubinfeld, where the function $f:\{0,1\}^n\to\{0,1\}$ is replaced by a pair of functions $\Xlin, \Zlin:\{0,1\}^n\to \text{Obs}_d(\C)$, the set of $d$-dimensional Hermitian matrices that square to identity.