History state and padded output

Fix an assignment to all clock bits outside the local support of $h_{\mathrm{\ell }}$. The subspace with that fixed spectator assignment and local clock state in $\{a_{\mathrm{\ell }},b_{\mathrm{\ell }}\}$ is invariant; in the order $(a_{\mathrm{\ell }},b_{\mathrm{\ell }})$ the block is ${\displaystyle \frac{1}{2}\left(\begin{array}{cc}I& -U_{\mathrm{\ell }}^{\ast }\\ -U_{\mathrm{\ell }}& I\end{array}\right)\mathrm{.}}$ The term is zero on every local pattern outside this pair. These mutually orthogonal blocks, together with the subspaces for those other local patterns, decompose the full register, so it suffices to inspect each displayed block and the zero action on the rest. For any data vectors $x,y$, its quadratic form is $\frac{1}{2}\mathrm{\parallel }y-U_{\mathrm{\ell }}x{\mathrm{\parallel }}^2\ge 0$, and its kernel consists exactly of paired amplitudes $(x,U_{\mathrm{\ell }}x)$. Hence $h_{\mathrm{\ell }}$ is positive semidefinite on the full clock register.

On legal unary clocks, $a_{\mathrm{\ell }}$ occurs only at $c_{\mathrm{\ell }-1}$ and $b_{\mathrm{\ell }}$ only at $c_{\mathrm{\ell }}$. Define the unitary $W={\sum }_{j=0}^N{V}_j\otimes \mathrm{\mid }{c}_j⟩⟨c_j\mathrm{\mid }$ on that space. Since $V_{\mathrm{\ell }}=U_{\mathrm{\ell }}{V}_{\mathrm{\ell }-1}$, conjugating the block from step 1.1 by $W$ makes every adjacent block $\frac{1}{2}\left(\begin{array}{cc}I& -I\\ -I& I\end{array}\right)$. Summing over edges gives $W^{\ast }{H}_{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{p}}W=I_{\mathrm{d}\mathrm{a}\mathrm{t}\mathrm{a}}\otimes L_N\mathrm{/}2$.

The quadratic form of $L_N$ is $⟨z,L_{N}z⟩={\sum }_{j=0}^{N-1}\mathrm{\mid }{z}_j-z_{j+1}{\mathrm{\mid }}^2$, so its kernel is the constant clock vectors. Step 2.1 therefore gives exactly the displayed propagation kernel, with arbitrary data vector $\xi$.

On a legal clock, $H_{\mathrm{i}\mathrm{n}\mathrm{p}\mathrm{u}\mathrm{t}}$ vanishes except at $c_0$, where it is the data Hamming-weight operator $N_1={\sum }_i\mathrm{\mid }1⟩⟨1{\mathrm{\mid }}_i$. Since $V_0=I$, conjugation by $W$ leaves this block unchanged. For a kernel vector with data vector $\xi$, its input energy is $⟨\xi ,N_1\xi ⟩\mathrm{/}(N+1)$, which is zero exactly when $\xi$ lies in the one-dimensional span of $\mathrm{\mid }{0}^n⟩$. Thus $H_{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{p}}+H_{\mathrm{i}\mathrm{n}\mathrm{p}\mathrm{u}\mathrm{t}}$ has the unique normalized kernel vector $\mathrm{\mid }\eta ⟩$.

The clock penalty $H_{\mathrm{c}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}}$ is positive semidefinite and has kernel exactly the legal unary strings: a binary string has no adjacent pattern $01$ exactly when all its $1$ bits precede all its $0$ bits. Each term of $H_{\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{l}}$ is positive semidefinite by step 1.1 and the definitions of $H_{\mathrm{i}\mathrm{n}\mathrm{p}\mathrm{u}\mathrm{t}},H_{\mathrm{c}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}}$. A zero-energy vector must therefore lie in the clock-penalty kernel and in the kernel identified in step 4.1. This proves uniqueness for the full final Hamiltonian.

Tracing the clock out of $\mathrm{\mid }\eta ⟩⟨\eta \mathrm{\mid }$ and using [F1] removes all cross terms between distinct $c_{\mathrm{\ell }}$, giving ${\displaystyle {\rho }_{\mathrm{d}\mathrm{a}\mathrm{t}\mathrm{a}}=\frac{1}{N+1}\sum _{\mathrm{\ell }=0}^N\mathrm{\mid }{V}_{\mathrm{\ell }}{0}^n⟩⟨V_{\mathrm{\ell }}{0}^n\mathrm{\mid }\mathrm{.}}$ For each $\mathrm{\ell }\ge L$, the appended gates are identities, so $V_{\mathrm{\ell }}\mathrm{\mid }{0}^n⟩=\mathrm{\mid }{\psi }_{\mathrm{o}\mathrm{u}\mathrm{t}}⟩:=U_L\cdots U_1\mathrm{\mid }{0}^n⟩$. There are $K+1$ such indices, and the other $L$ terms form a density operator $\sigma$ after normalization. Hence ${\rho }_{\mathrm{d}\mathrm{a}\mathrm{t}\mathrm{a}}=\frac{L}{N+1}\sigma +\frac{K+1}{N+1}\mathrm{\mid }{\psi }_{\mathrm{o}\mathrm{u}\mathrm{t}}⟩⟨{\psi }_{\mathrm{o}\mathrm{u}\mathrm{t}}\mathrm{\mid }$.

By homogeneity of the trace norm in the definition of trace distance, the distance from $\mathrm{\mid }{\psi }_{\mathrm{o}\mathrm{u}\mathrm{t}}⟩⟨{\psi }_{\mathrm{o}\mathrm{u}\mathrm{t}}\mathrm{\mid }$ is $\frac{L}{N+1}D(\sigma ,\mathrm{\mid }{\psi }_{\mathrm{o}\mathrm{u}\mathrm{t}}⟩⟨{\psi }_{\mathrm{o}\mathrm{u}\mathrm{t}}\mathrm{\mid })\le L\mathrm{/}(N+1)$ by [F3]. Since $K=\lceil 2L\mathrm{/}\epsilon \rceil$ and $N=L+K$, we have $L\mathrm{/}(N+1)\le L\mathrm{/}K\le \epsilon \mathrm{/}2$.