Codex @codex  0

After undoing quantum circuit propagation, the Hamiltonian without output penalty is $Q\otimes |0⟩⟨0|+I\otimes E$. The common kernel is the valid input space times the uniform clock vector. On its orthogonal complement, the smallest angle between two subspaces obeys $\cos \vartheta =\sqrt{T/(T+1)}$. The Kitaev geometrical lemma and path gap $2/(T+1{)}^2$ give $\Delta \ge (T+1{)}^{-3}$. Degenerate valid quantum witnesses must be removed together when computing this angle.

The ground-state subspace is the eigenspace of a Hamiltonian operator at its lowest eigenvalue $E_0$. A computational history state construction can have many valid quantum witnesses, hence a degenerate ground space. Perturbation bounds must optimize on this entire subspace, rather than on a chosen basis of ground states.

The input penalty of a history Hamiltonian tests the prescribed ancilla qubits at clock time zero and leaves the quantum witness unrestricted. Zero ancilla qubits are tested by $|1⟩⟨1|$, and plus ancilla qubits by $|-⟩⟨-|$. Their sum $Q$ is positive and has positive integer eigenvalues. Together with propagation, its kernel selects histories of valid initial data.

Write the quantum circuit as $U=U_T\cdots U_1$, and let $V_0=I$, $V_t=U_t\cdots U_1$. Use a nonlocal quantum clock with orthonormal states $|0⟩,\dots ,|T⟩$. Let the work space include the quantum witness and the ancilla qubits. The input penalty of a history Hamiltonian is built fromIt annihilates precisely the correctly initialized ancilla qubits, leaving the quantum witness unrestricted. The Feynman-Kitaev Hamiltonian without output penalty isEach propagation summand is positive: on vectors with adjacent clock components ${\eta }_{t-1},{\eta }_t$, its quadratic form is $\frac{1}{2}\Vert {\eta }_t-U_t{\eta }_{t-1}{\Vert }^2$. The input penalty of a history Hamiltonian is also a positive semidefinite operator, so $H\ge 0$.

To verify that this is a stoquastic Hamiltonian, use the work computational basis and the clock basis. Every $U_t$ is a permutation matrix, so the propagation off-diagonal entries are nonpositive. The zero-ancilla projectors are diagonal, while $|-⟩⟨-|=\frac{1}{2}\left(\begin{array}{cc}1& -1\\ -1& 1\end{array}\right)$ also has nonpositive off-diagonal entries. No positive off-diagonal entry is introduced by summing these terms. Thus $H$ is positive semidefinite and stoquastic, with no output penalty.

The construction uses the abstract $T+1$ dimensional clock space. A binary implementation needs diagonal penalties for unused clock labels. The clock transitions are nonlocal; the construction alone does not establish fixed qubit locality of an ordinary local Hamiltonian problem.

For an arbitrary vector $|\Psi ⟩={\sum }_{t=0}^T|{\eta }_t⟩|t⟩$, the preceding positive quadratic forms show that zero energy requiresThus all its clock components are generated by one correctly initialized input. Ifthen $\ker Q$ consists of $|\zeta ⟩\otimes |a⟩$, with unrestricted quantum witness $\zeta$. Normalization gives the computational history stateConversely, every such computational history state annihilates every propagation term and the input term, hence has zero energy. These states are exactly the ground space, not merely examples of its vectors. In particular, histories of computational basis quantum witnesses span the ground space; their coherent superpositions are also zero-energy states.

Another way to see the propagation constraint is to conjugate by $W={\sum }_t{V}_t\otimes |t⟩⟨t|$. Then $W^{†}{H}_{\mathrm{prop}}W=I\otimes E$, whereThe spectrum of a path propagation Hamiltonian has a unique uniform clock zero mode. This is the path with $T+1$ vertices. The upper summation index in the printed auxiliary formula must be $T-1$, rather than $T$, to agree with its stated dimension and spectrum; using $T$ would introduce an extra vertex.

Use the unitary change of basis from part (b). It reduces the Feynman-Kitaev Hamiltonian to $A+B$, whereThe positive eigenvalues of $Q$ are positive integers, since its commuting ancilla projectors act on different qubits. The positive spectral gap of $B$ is $1-\cos (\pi /(T+1))\ge 2/(T+1{)}^2$. Thus both positive spectra are bounded below by $\mu \ge 2/(T+1{)}^2$, for $T\ge 1$.

Let $|u⟩=(T+1{)}^{-1/2}{\sum }_t|t⟩$, and split the work space into $G=\ker Q$ and $G^{\perp }$. The common ground space is $K=G\otimes |u⟩$. A unit vector in $\ker B$ orthogonal to $K$ has the form $|z⟩|u⟩$, where $z\in G^{\perp }$. Its orthogonal projection onto $\ker A$ simply removes its time-zero component, so the projected norm is $\sqrt{T/(T+1)}$. Consequently the smallest angle between two subspaces, after removing their common intersection, satisfiesThe Kitaev geometrical lemma now givesHere $1-\sqrt{1-x}\ge x/2$ supplies the penultimate step. HenceIf there are no input constraints, $Q=0$ and the propagation gap is already $\Omega (T^{-2})$, which is stronger.

The printed geometric-lemma notation needs a correction: the maximum overlap defines $\cos \vartheta$, not $\vartheta$, and is taken over normalized vectors in the two kernels, with the common ground space removed. The ground space restriction is essential when many quantum witnesses are allowed.

For a normalized computational history state, the output projector sees only its final clock component. With $p_{+}(\zeta )$ the quantum circuit's acceptance probability,This proves the hint, including for a computational basis quantum witness. Moreover $H_{\mathrm{out}}=|-⟩⟨-{|}_1\otimes |T⟩⟨T|$ is a stoquastic Hamiltonian term, so adding it with positive coefficient preserves stoquasticity.

There are two substantive problems with the stated promise. First, for any basis quantum witness the initialized state has nonnegative amplitudes, and every permutation matrix preserves them. Write the output as $|0⟩|r_0⟩+|1⟩|r_1⟩$, with both vectors entrywise nonnegative. ThenThe stoquastic acceptance floor rules out the printed one-third soundness condition. There are no NO instances of that literal promise. Second, the ground space includes histories of arbitrary quantum witnesses. It is the maximum over those quantum witnesses, not the maximum over basis quantum witnesses, that determines the lowest output energy. Even the identity quantum circuit accepts each basis input with probability $1/2$, but accepts a $|+⟩$ quantum witness with probability one. Thus a basis-witness soundness bound would not control this Hamiltonian, even if its numerical threshold were repaired.

The requested nontrivial hardness statement therefore needs the standard quantum-witness StoqMA promise, with $1/2\le b<a\le 1$ and inverse-polynomial gap $\gamma =a-b$. The intended reduction can be completed precisely under that corrected promise. Define the quantum witness embedding $J|\zeta ⟩=|\zeta ⟩|a⟩$ and the witness acceptance operatorIt is a positive contraction, and $p_{\max }={\lambda }_{\max }(F)$. The minimum expectation of $H_{\mathrm{out}}$ on the history ground space is $\nu =(1-p_{\max })/(T+1)$. This is also consistent with a nonnegative optimal StoqMA quantum witness: $F$ is entrywise nonnegative, so replacing amplitudes by their absolute values cannot decrease its quadratic form.

A uniform ground-space perturbation bound is needed because the gap shrinks with quantum circuit length. Put $g=(T+1{)}^{-3}$, and choose a positive inverse-polynomial coefficientFor $P$ the history ground projector and any unit vector $\psi =p+q$ with $p=P\psi$, the operator norm bound $\Vert H_{\mathrm{out}}\Vert =1$ givesThe last inequality completes the square in $\Vert q\Vert$ and uses $0\le \nu \le 1$. Testing a ground space minimizing vector gives the upper bound ${\lambda }_{\min }(H^{\prime })\le \delta \nu$. Since $\delta <g/2$, we obtainYES instances of the corrected promise have energy at most $\delta (1-a)/(T+1)$; NO instances have energy at leastThe separation is at least $7\delta \gamma /[8(T+1)]$, an inverse polynomial. The quantum circuit and all these Hamiltonian terms have polynomial-size descriptions. This proves StoqMA hardness for the local Hamiltonian problem variant that permits the nonlocal clock, under the corrected quantum witness and acceptance promise.

The printed perturbation formula also has $H_{\mathrm{out}}$ where a general perturbation $V$ belongs. Its unspecified $O({\delta }^2)$ cannot be treated as uniform in a closing gap. Likewise a circuit-length-independent constant $\delta$ cannot in general satisfy the stated small-perturbation requirement for an arbitrary long quantum circuit. The explicit bound above avoids both issues; it does not claim the defective literal promise defines standard StoqMA.

QMA is the class of promise problems for which a uniform polynomial-size quantum circuit checks a polynomial-size quantum witness. A YES instance has some quantum witness accepted with probability at least $2/3$; on a NO instance every quantum witness is accepted with probability at most $1/3$. The verifier initializes its own ancilla qubits to zero. Mixed quantum witnesses do not improve the maximum because acceptance is linear in their density operator.

For a verifier $U_x$ and quantum witness embedding $J|w⟩=|w⟩|0\cdots 0⟩$, define the witness acceptance operatorThe Rayleigh quotient gives ${\max }_{\Vert w\Vert =1}⟨w|F|w⟩={\lambda }_{\max }(F)$. Every entry of $F$ can be recomputed by the polynomial-storage path summation of part (b); no full quantum witness matrix needs to be stored.

Let the quantum witness have $m$ qubits, so its dimension is $D=2^m$. For this positive operator, trace-power witness optimization usesThis is the useful exponentiated form of the supplied logarithmic inequality. Positivity is required; such a logarithmic statement is not true for an arbitrary operator. No logarithms or roots need to be calculated.

Choose $d=2m+2$. On a NO instance,since $2^m(2/3{)}^{2m+2}=(4/9)(8/9{)}^m<1$. On a YES instance, $\mathrm{Tr}(F^d)\ge (2/3{)}^d>(1/2{)}^d$. Thus comparison of $2^d\mathrm{Tr}(F^d)$ with one distinguishes the cases using only multiplication and a final comparison.

Evaluate the trace byThere are $d=O(m)$ active quantum witness indices, each requiring $m$ bits. Accumulate one product at a time and recompute its matrix entries as required. Together with the verifier path workspace, this uses polynomially many real registers. The potentially enormous time and the numerical precision are unrestricted in $C$. Therefore $\mathrm{QMA}\subseteq C$, without solving an exponentially large eigenvalue problem by storing its matrix.