Encoded k-local Hamiltonian promise problem

Fix an integer $k\ge 1$. An encoded instance of input length $N$ gives $n,m\ge 1$, with $n$ polynomially bounded in $N$ and $m$ polynomially bounded in $n$. For each term it lists a support set $S_j\subseteq \{0,\dots ,n-1\}$ of size $r_j\le k$ and a Hermitian $2^{r_j}\times 2^{r_j}$ matrix $H_j$ in the computational basis of those qubits, ordered by increasing index in $S_j$. It also gives a positive rational polynomial bound $B$ with $\mathrm{\parallel }{H}_j\mathrm{\parallel }\le B$ for every exact term. Matrix descriptions and their approximation procedures use Effective finite matrix encodings for local Hamiltonians. Embed each term as $H_j$ on the factors indexed by $S_j$ in increasing order and the identity on every other qubit, and put $H={\sum }_{j=1}^m{H}_j$ on $({\mathbb{C}}^2{)}^{\otimes n}$. Given rational thresholds $a<b$ with $b-a\ge 1\mathrm{/}p(n)$ for a polynomial $p$, the promise problem has YES instances when ${\lambda }_{\min }(H)\le a$ and NO instances when ${\lambda }_{\min }(H)\ge b$. Inputs violating the format or promise are outside the promise; no behavior is required there. A matrix description is not a free measurement oracle: a verifier must generate every local test circuit from the finite encoding.