= Solution
The <local Hamiltonian problem> is a <promise problem> specified by a sum $H=\sum_{j=1}^M h_j$ on $n$ <qubits>, where $M$ is polynomial in $n$, each Hermitian term acts on at most a fixed number $k$ of <qubits>, and the terms and two thresholds $a<b$ are described with polynomially many bits. The promise gap satisfies $b-a\geq1/\operatorname{poly}(n)$. In a convenient normalization, $0\leq h_j\leq I$. The task is to distinguish
$$
\boxed{\text{YES: }\lambda_{\min}(H)\leq a,
\qquad
\text{NO: }\lambda_{\min}(H)\geq b.}
$$
There is no required answer when the minimum energy lies between the thresholds. A formulation with Hermitian terms of polynomially bounded norm is equivalent: shift each term by a known scalar lower bound and rescale all terms by a polynomial bound to obtain <positive semidefinite> terms of norm at most one, while shifting and rescaling $a,b$ in parallel. The promise gap remains inverse-polynomial.
Back to article page
