Constant-Soundness Interactive Proofs for Local Hamiltonians
arXiv:1512.02090
Abstract
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 is replaced by a pair of functions $\Xlin, \Zlin:\{0,1\}^n\to \text{Obs}_d(\C)$, the set of -dimensional Hermitian matrices that square to identity. The test enforces that (i) each function is exactly linear, $\Xlin(a)\Xlin(b)=\Xlin(a+b)$ and $\Zlin(a) \Zlin(b)=\Zlin(a+b)$, and (ii) the two functions are approximately complementary, $\Xlin(a)\Zlin(b)\approx (-1)^{a\cdot b} \Zlin(b)\Xlin(a)$.
arXiv comment33 pages
References in corpus (9)
- Good Quantum Error-Correcting Codes Exist
- Robust Self Testing of the Singlet
- Quantum NP - A Survey
- Interactive proofs for BQP via self-tested graph states
- Self-testing in parallel
- A Survey of Quantum Property Testing
- The Quantum PCP Conjecture
- Three-player entangled XOR games are NP-hard to approximate
- Quantum Multi-Prover Interactive Proof Systems with Limited Prior Entanglement