Circuit-to-adiabatic simulation

Write $H(s)=(1-s)H_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}+s{H}_{\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{l}}$. The common $H_{\mathrm{i}\mathrm{n}\mathrm{p}\mathrm{u}\mathrm{t}}$ and $J{H}_{\mathrm{c}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}}$ terms cancel in $H^{\mathrm{\prime }}$, leaving $H^{\mathrm{\prime }}=H_{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{p}}-H_{\mathrm{c}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}0}$, so $\mathrm{\parallel }{H}^{\mathrm{\prime }}\mathrm{\parallel }\le 3N$ from the term bounds, and $H^{\mathrm{\prime }\mathrm{\prime }}=0$. By [F3], the full ground gap is at least $\gamma :=3{\mathrm{\Delta }}_0\mathrm{/}4=1\mathrm{/}[288(N+1{)}^3]$ throughout the path. Each term of $H_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}=H_{\mathrm{i}\mathrm{n}\mathrm{p}\mathrm{u}\mathrm{t}}+H_{\mathrm{c}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}0}+J{H}_{\mathrm{c}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}}$ is positive semidefinite. A binary string has no adjacent $01$ pair exactly when all of its $1$ bits precede all of its $0$ bits, so $H_{\mathrm{c}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}}$ vanishes exactly on the legal unary clocks. On those clocks $H_{\mathrm{c}\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{k}0}$ vanishes only at $c_0$; at $c_0$, the input penalty vanishes exactly on $\mathrm{\mid }{0}^n⟩$. Thus the unique initial ground vector is $\mathrm{\mid }{0}^n⟩\mathrm{\mid }{c}_0⟩$, whose supplied preparation is included in [F1].

In the rank-one JRS expression from [F4], each endpoint term is at most $3N\mathrm{/}{\gamma }^2$, and the integral term is at most $7(3N{)}^2\mathrm{/}{\gamma }^3$ because $H^{\mathrm{\prime }\mathrm{\prime }}=0$. Put ${\displaystyle B_T=\frac{6N}{{\gamma }^2}+\frac{63N^2}{{\gamma }^3},T=\lceil \frac{4B_T}{\epsilon }\rceil \mathrm{.}}$ Then $A_1(1)\le B_T\mathrm{/}T\le \epsilon \mathrm{/}4$. Since ${\gamma }^{-1}=288(N+1{)}^3$, we have $B_T=O(N^{11})$ and $T=O(N^{11}\mathrm{/}\epsilon )$. Also $K=\mathrm{\Theta }(L\mathrm{/}\epsilon )$ and $N=\mathrm{\Theta }(L\mathrm{/}\epsilon )$ for $L\ge 1$, $\epsilon \le 1$, giving the stated $O(L^{11}{\epsilon }^{-12})$ bound.

Let ${\psi }_T$ be the ideal evolved unit vector and $\eta$ the final ground vector. The JRS projector estimate gives $\mathrm{\parallel }\mathrm{\mid }{\psi }_T⟩⟨{\psi }_T\mathrm{\mid }-\mathrm{\mid }\eta ⟩⟨\eta \mathrm{\mid }\mathrm{\parallel }\le \epsilon \mathrm{/}4$. For rank-one projections the operator norm of their difference equals their trace distance: on the span of the two vectors the difference has eigenvalues $\pm \sqrt{1-\mathrm{\mid }⟨{\psi }_T,\eta ⟩{\mathrm{\mid }}^2}$, and it vanishes on the orthogonal complement. Thus their full-register trace distance is at most $\epsilon \mathrm{/}4$.

Run the proved simulator [F6] with tolerance $\epsilon \mathrm{/}4$ and execute its schedule on the supplied initial vector. If ${\tilde{\psi }}_T$ is the resulting unit vector, operator-norm error gives $\mathrm{\parallel }{\tilde{\psi }}_T-{\psi }_T\mathrm{\parallel }\le \epsilon \mathrm{/}4$. Put $c=⟨{\psi }_T,{\tilde{\psi }}_T⟩$. By [F5], the pure-state trace distance squared is $(1-\mathrm{\mid }c\mathrm{\mid })(1+\mathrm{\mid }c\mathrm{\mid })\le 2(1-\mathrm{\mid }c\mathrm{\mid })\le 2-2\mathrm{Re}c=\mathrm{\parallel }{\tilde{\psi }}_T-{\psi }_T{\mathrm{\parallel }}^2$, so it is at most $\epsilon \mathrm{/}4$. By partial-trace contractivity, tracing out the clock does not increase either this error or the adiabatic error in step 3.1.

The data marginal of $\mathrm{\mid }\eta ⟩$ is within $\epsilon \mathrm{/}2$ of the target circuit output by [F2]. By [F7], the triangle inequality for trace distance, steps 3.1–4.1, and the padding estimate give total output distance at most $\epsilon \mathrm{/}4+\epsilon \mathrm{/}4+\epsilon \mathrm{/}2=\epsilon$.

The term list has $M=n+N+N+(N-1)=n+3N-1\le n+3N$ terms: $n$ input projectors, $N$ clock-potential projectors, $N$ propagation terms, and $N-1$ clock-penalty projectors. Each has norm at most $1$ by the local block calculation in the proof of the full-gap lemma and the projection form of the other terms. Set the certified derivative bound to $M_1=3N$. The coefficient functions are the constants $1$, $J$, and the affine functions $s$ and $1-s$; at rational grid points they are exactly computable rationals, so take zero coefficient error. For every sample, each coefficient has magnitude at most $J$ and each term norm is at most $1$, whence ${\sum }_{p<q}\mathrm{\parallel }[A_p,A_q]\mathrm{\parallel }\le 2\left(\genfrac{}{}{0px}{}{M}{2}\right)J^2\le M^2{J}^2$; use the finite rational certificate $B=M^2{J}^2$. The value of $J=2K_0+864K_0^2(N+1{)}^3+1$ is polynomial in $n,N$, so $M_1,B$ and all coefficient encodings have polynomial bit length. With $T=\lceil 4B_T\mathrm{/}\epsilon \rceil =O(N^{11}\mathrm{/}\epsilon )$ and $M_1=3N$, the grid count $q=O(TN\mathrm{/}\epsilon )$ is polynomial. Since $\tau =T\mathrm{/}q\le \epsilon \mathrm{/}(9N)$, the product-formula count $r_{\mathrm{P}\mathrm{F}}\le 1+3q{\tau }^{2}B\mathrm{/}\epsilon =1+3T\tau B\mathrm{/}\epsilon$ is polynomial as well. Thus [F6] executes finitely many, polynomially many term calls, and by hypothesis their requested-error providers, coefficient procedures and output operation have polynomial charged cost. Preparation cost, queries, gates, ancillas, coefficient precision, circuit-description bits and generator time are all separately recorded; no spectral projector is used to prepare the initial state.