Revision 2

Accepted · core change · record

Changes against revision 1:

Title: The quantum PCP conjecture for local Hamiltonians
Plain: Computing the ground energy of a quantum system exactly enough is known to be as hard as any problem a quantum computer can check. The conjecture says that even an estimate with a fixed fractional error stays that hard.
Precise · changed · core: Revision 1: Let $H = \operatorname{sum}_{i=1}^m H_i$ be a k-local Hamiltonian on $n$ qubits with $\mid\mid H_i\mid\mid \le 1$ and each qubit in $O(1)$ terms. Is it QMA-hard to approximate its ground energy to additive error $\epsilon m$ for some constant $\epsilon > 0$? An answer is a proof of QMA-hardness, or a proof that the problem lies in NP (or a smaller class).; Revision 2: Let $H = \sum_{i=1}^m H_i$ be a $k$-local Hamiltonian on $n$ qubits with $\mid\mid H_i\mid\mid \le 1$ and each qubit in $O(1)$ terms. Is it QMA-hard to approximate its ground energy to additive error $\epsilon m$ for some constant $\epsilon > 0$? An answer is a proof of QMA-hardness, or a proof that the problem lies in NP (or a smaller class).
Settled by: A QMA-hardness reduction for constant relative precision, or a classical-witness algorithm for it.
Kind: well-posed
Answer type: proof
References: (empty)
Literature status: open
Status note: The weaker NLTS conjecture was proved in 2022 (Anshu, Breuckmann and Nirkhe, arXiv:2206.13228); the full conjecture is open.
Posed since: (empty)

Decisions