The encoded Local Hamiltonian problem belongs to QMA

Let $N=\mathrm{\mid }x\mathrm{\mid }$. Because $n$ is polynomially bounded in $N$, choose fixed polynomial envelopes $P(N)\ge \max \{1,p(n)\}$ and $Q(N)\ge 1$ bounding both $m$ and $B$ on every valid length-$N$ input; these envelopes are computable in polynomial time from $1^N$. Put $g_{\ast }(N)=1\mathrm{/}(4Q(N{)}^{2}P(N))$. Since $d<2m$ for $m>1$ and $d=1$ for $m=1$, the exact gap $g=(b-a)\mathrm{/}(2dB)$ satisfies $g\ge g_{\ast }(N)$. Prepare the address uniformly with Hadamards using [F8]. A fixed polynomial-time classical compiler on the encoded instance builds the verifier gate list: compute each equality predicate, apply the selector-controlled local Naimark test, and reject invalid addresses. The controlled target has fixed dimension at most $2^{k+2}$; [F2] supplies its Cauchy matrix description, and [F6] compiles each full selector-controlled block to operator error at most $g_{\ast }(N)\mathrm{/}(32m)$, up to a whole-circuit scalar. Telescoping the $m$ block replacements gives total operator error at most $g_{\ast }(N)\mathrm{/}32$, hence acceptance error at most $g_{\ast }(N)\mathrm{/}16$ for the complete address test; this also bounds leakage from approximate selector controls. The compiler's full output list has polynomial length because $m,B$ are polynomially bounded and each matrix encoding has the uniform polynomial-time approximation routine of [F10]. The compiler is uniformized by [F7] with operator error $\delta (N)=g_{\ast }(N)\mathrm{/}32$ after appending the threshold normalization below; the single full-list family generated from $1^N$ computes the complete list from $x$ and interprets it. A fixed polynomial time limit makes the classical compiler total, emitting a fixed rejecting circuit on malformed input or overrun; promised encodings satisfy the established bounds.

In the address basis, the acceptance effect on the witness is the direct sum average $d^{-1}{\sum }_{j<m}{E}_j$. The finite outcome law [F9] and trace linearity [F5] give $p(\rho )=d^{-1}{\sum }_{j<m}\mathrm{Tr}(E_j\rho )=\frac{m}{2d}-\frac{\mathrm{Tr}(H\rho )}{2dB}\mathrm{.}$ For a YES instance use a ground-state eigenvector from the finite spectral theorem; for a NO instance every density matrix has energy at least $b$. Thus the exact acceptance gap is $(b-a)\mathrm{/}(2dB)$. If $m>1$, $d<2m$; if $m=1$, $d=1$, so in either case it is at least $(b-a)\mathrm{/}(4mB)$.

By [F2] and [F7], the implemented energy test has acceptance error at most $g_{\ast }(N)\mathrm{/}16+2(g_{\ast }(N)\mathrm{/}32)=g_{\ast }(N)\mathrm{/}8$. Its ideal instance-dependent thresholds are $c_x=m\mathrm{/}(2d)-a\mathrm{/}(2dB)$ and $s_x=m\mathrm{/}(2d)-b\mathrm{/}(2dB)$, with $c_x-s_x=g$. Compute $t_x=(c_x+s_x)\mathrm{/}2$ exactly. If $t_x<0$, then $s_x<0$, so no NO instance can occur because acceptance is nonnegative; accept deterministically. If $t_x>1$, then $c_x>1$, so no YES instance can occur; reject deterministically. For $0\le t_x\le 1$, use a fair branch coin: on one branch perform the energy test, and on the other accept with probability $1-t_x$. The ideal combined acceptance is $q=(p+1-t_x)\mathrm{/}2$, at least $1\mathrm{/}2+g\mathrm{/}4$ on YES and at most $1\mathrm{/}2-g\mathrm{/}4$ on NO. The second coin is prepared by synthesizing the one-qubit real rotation with first column $(\sqrt{t_x},\sqrt{1-t_x}{)}^T$ to probability error at most $g_{\ast }(N)\mathrm{/}16$ using [F6]; square-root Cauchy evaluation, including zero endpoints, is supplied by the rounded Newton construction in [F2]. All branch and outcome bits are measured only at termination, with a polynomial-time final predicate. Apply the interpreter once to this complete input-generated circuit. Its energy-block error contributes at most $g_{\ast }\mathrm{/}32$ after the half mixture, the second coin contributes at most $g_{\ast }\mathrm{/}32$, and interpreter error contributes at most $g_{\ast }\mathrm{/}16$, for total error at most $g_{\ast }\mathrm{/}8$. Thus the length-only rational thresholds $c(N)=1\mathrm{/}2+g_{\ast }(N)\mathrm{/}8$ and $s(N)=1\mathrm{/}2-g_{\ast }(N)\mathrm{/}8$ apply to every promised length-$N$ input. Both lie in $[0,1]$ since $g_{\ast }\le 1\mathrm{/}4$, and their gap is inverse polynomial. Amplify this uniform verifier using [F4]; witness width, initialized workspace, size and generator time remain polynomial.