= 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\rangle,\ldots,|T\rangle$. Let the work space include the <quantum witness> and the <ancilla qubits>. The <input penalty of a history Hamiltonian> is built from
$$
Q=\sum_{a\in A_0}|1\rangle\langle1|_a+\sum_{a\in A_+}|-\rangle\langle-|_a.
$$
It annihilates precisely the correctly initialized <ancilla qubits>, leaving the <quantum witness> unrestricted. The <Feynman-Kitaev Hamiltonian> without output penalty is
$$
\boxed{H=H_{\rm in}+H_{\rm prop},\qquad H_{\rm in}=Q\otimes|0\rangle\langle0|,}
$$
$$
H_{\rm prop}=\frac12\sum_{t=1}^T\left[I\otimes\bigl(|t\rangle\langle t|+|t-1\rangle\langle t-1|\bigr)-U_t\otimes|t\rangle\langle t-1|-U_t^\dagger\otimes|t-1\rangle\langle t|\right].
$$
Each propagation summand is positive: on vectors with adjacent clock components $\eta_{t-1},\eta_t$, its <quadratic form> is $\tfrac12\|\eta_t-U_t\eta_{t-1}\|^2$. The <input penalty of a history Hamiltonian> is also a <positive semidefinite operator>, so $H\geq0$.
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 $|-\rangle\langle-|=\tfrac12\begin{pmatrix}1&-1\\-1&1\end{pmatrix}$ also has nonpositive off-diagonal entries. No positive off-diagonal entry is introduced by summing these terms. \b[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>.
Back to article page
