Feynman–Kitaev history Hamiltonian

Let a verifier circuit have $T\ge 1$ gates $U_1,\dots ,U_T$, each acting on at most two computation qubits, with its accept/reject predicate reversibly computed into one output qubit (accept is $\mathrm{\mid }1⟩$). Let $N=T+1$ and encode time $t$ by the unary clock word $\mathrm{\mid }{c}_t⟩=\mathrm{\mid }{1}^t{0}^{T-t}⟩$ on $T$ clock qubits. For an initial computation vector $\varphi$ define its history vector $\mathrm{\mid }{\eta }_{\varphi }⟩=N^{-1\mathrm{/}2}{\sum }_{t=0}^T(U_t\cdots U_1\varphi )\otimes \mathrm{\mid }{c}_t⟩,$ where the $t=0$ product is $I$. Orthogonality of the clock words and unitarity give $\mathrm{\parallel }{\eta }_{\varphi }\mathrm{\parallel }=\mathrm{\parallel }\varphi \mathrm{\parallel }$; this history is normalized exactly when $\mathrm{\parallel }\varphi \mathrm{\parallel }=1$. For each propagation edge $t=1,\dots ,T$, let $\mathrm{\mid }pr{e}_t⟩,\mathrm{\mid }pos{t}_t⟩$ be the local clock patterns which $c_{t-1},c_t$ have on their smallest common window: for $T=1$ these are $0,1$ on $C_1$; for $T\ge 2,t=1$ they are $00,10$ on $C_1{C}_2$; for $t=T$ they are $10,11$ on $C_{T-1}{C}_T$; and for $1<t<T$ they are $100,110$ on $C_{t-1}{C}_t{C}_{t+1}$. Define $H_{prop,t}=\frac{1}{2}(I\otimes \mathrm{\mid }pr{e}_t⟩⟨pr{e}_t\mathrm{\mid }+I\otimes \mathrm{\mid }pos{t}_t⟩⟨pos{t}_t\mathrm{\mid }-U_t\otimes \mathrm{\mid }pos{t}_t⟩⟨pr{e}_t\mathrm{\mid }-U_t^{\ast }\otimes \mathrm{\mid }pr{e}_t⟩⟨pos{t}_t\mathrm{\mid }),$ where each clock ket is only on the displayed local window. For each local pre/post block, its quadratic form is one half the squared norm of the difference between the post component and $U_t$ applied to the pre component, so it is positive semidefinite. On legal clock words these patterns identify exactly the adjacent times $t-1,t$. Put $H_{prop}={\sum }_t{H}_{prop,t}$. Define $H_{in}={\sum }_{a\in A}\mathrm{\mid }1⟩⟨1{\mathrm{\mid }}_a\otimes \mathrm{\mid }0⟩⟨0{\mathrm{\mid }}_{C_1},H_{out}=N\mathrm{\mid }0⟩⟨0{\mathrm{\mid }}_{out}\otimes \mathrm{\mid }1⟩⟨1{\mathrm{\mid }}_{C_T},H_{clock}={\sum }_{i=1}^{T-1}\mathrm{\mid }01⟩⟨01{\mathrm{\mid }}_{C_i{C}_{i+1}}\mathrm{.}$ Here $A$ indexes initially zero verifier workspace qubits, and the output predicate is computed into the displayed accept qubit. The history Hamiltonian is the positive sum $H_{in}+H_{prop}+H_{out}+H_{clock}$. A propagation term uses at most two computation and three clock qubits; each other summand uses at most two qubits.