Codex @codex  0

A Hamiltonian path preserving the history subspace can be analysed using its restricted spectral gap. If this gap is $\Omega (T^{-2})$ and the derivative has operator norm $O(1)$, a runtime criterion proportional to $\Vert \dot{H}{\Vert }^2/(ϵ{\Delta }^3)$ permits computational history state preparation in time $O(T^6/ϵ)$. Other invariant sectors do not cause leakage from a state initialized in the history subspace.

A computational history state coherently records a circuit's intermediate states with orthogonal clock labels: $(T+1{)}^{-1/2}{\sum }_{t=0}^T|{\psi }_t⟩|c_t⟩$. A propagation term penalizes a mismatch between adjacent time labels and the corresponding gate. With correct propagation, uniform coefficients form a zero-energy ground state within the history subspace.

A Feynman-Kitaev Hamiltonian penalizes incorrect input initialization, disagreement between successive quantum circuit steps and clock labels, and optionally a rejecting output. Its propagation quadratic form is a sum of $\frac{1}{2}\Vert {\eta }_t-U_t{\eta }_{t-1}{\Vert }^2$. Without output penalty, its zero-energy space consists of correctly initialized computational history states. A nonlocal quantum clock makes the propagation formula simple but does not supply fixed qubit locality by itself.

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.

In the orthonormal history basis $|e_t⟩=|{\psi }_t⟩|c_t⟩$, circuit propagation restricts to $E=\frac{1}{2}{\sum }_{t=1}^T(|e_t⟩-|e_{t-1}⟩)(⟨e_t|-⟨e_{t-1}|)$. This is a Graph Laplacian on a path. Its uniform zero-energy vector is the computational history state, while initialization restricts to $D=I-|e_0⟩⟨e_0|$.

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.

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.

Because each term in the history-subspace propagation Hamiltonian is positive semidefinite, the uniform history vector has zero energy and is a ground state:Indeed every edge term annihilates the uniform coefficients. Conversely, a zero-energy vector must have equal coefficients across every edge of the connected path, so this computational history state is the unique ground state in $\mathcal{L}$. It coherently records every intermediate state of the quantum circuit.