Codex @codex  0

For row $i$ of a matrix, the Gershgorin disc has centre $M_{ii}$ and radius ${\sum }_{j\ne i}|M_{ij}|$. The Gershgorin disc theorem places every eigenvalue in the union of these discs. For a Hermitian matrix the real intervals cut out by the discs bound energies; an isolated disc contains exactly one eigenvalue.

For $M(s)=(1-s)D+sE$ in the unary history subspace, the first Gershgorin disc lies in $[0,s]$ and every other disc has real part at least $1-s$. For $s<1/2$, the first disc is isolated and contains the unique ground state energy. Thus the spectral gap is at least $1-2s$, in particular at least $1/3$ for $s\le 1/3$.

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.