= Solution
Part (a) shows that $\mathcal L$ is invariant throughout the interpolation. As the Hamiltonians are Hermitian, $\mathcal L^\perp$ is invariant as well: evolution starting in $\mathcal L$ has no leakage into other sectors. The <quantum adiabatic theorem> may therefore be applied using the restricted <spectral gap>, even if other sectors of the full Hamiltonian have different low-energy levels.
Combining (b)(iv) with the supplied bound for $s>1/3$ gives $\min_s\Delta(M(s))\geq c/(T+1)^2$ for a constant $c>0$. The matrix $E-D$ has diagonal entries $1/2,0,\ldots,0,-1/2$ and off-diagonal entries $-1/2$. Its <Gershgorin discs> all lie in $[-1,1]$, so $\|E-D\|\leq1$. Thus the runtime criterion for <adiabatic preparation of a computational history state> is satisfied by
$$
\boxed{\tau=O\!\left(\frac{(T+1)^6}{\epsilon}\right)}
$$
with a sufficiently large constant.
Starting from the supplied initial <ground state> $|e_0\rangle$, the resulting state $\rho_{\rm out}$ obeys
$$
\boxed{\|\rho_{\rm out}-|\varphi\rangle\langle\varphi|\|_1\leq\epsilon.}
$$
Here the trace norm follows the question's convention; the conventional <trace distance> is half this norm. The Hamiltonian has $O(T)$ explicitly specified terms, each acting on at most five <qubits>, so its description and the runtime are polynomial in circuit size. If $\epsilon^{-1}$ is polynomially bounded, the whole preparation has polynomial cost. The initial computational input is assumed to have been prepared, as in the premise of the <quantum adiabatic theorem>.
Back to article page
