Past exam of the mathematics course of the University of Cambridge / 2015 / iii / Paper 67 / 2 / c / 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))\ge c/(T+1{)}^2$ for a constant $c>0$. The matrix $E-D$ has diagonal entries $1/2,0,\dots ,0,-1/2$ and off-diagonal entries $-1/2$. Its Gershgorin discs all lie in $[-1,1]$, so $\Vert E-D\Vert \le 1$. Thus the runtime criterion for adiabatic preparation of a computational history state is satisfied bywith a sufficiently large constant.

Starting from the supplied initial ground state $|e_0⟩$, the resulting state ${\rho }_{\mathrm{out}}$ obeysHere 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 ${ϵ}^{-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.