 Solution

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.