Past exam of the mathematics course of the University of Cambridge / 2015 / iii / Paper 67 / 2

Define the orthonormal history basiswhere ${\psi }_t=U_t\cdots U_1{\psi }_0$. Orthogonality follows from the distinct unary quantum clock strings, regardless of overlaps between the computational states.

The initialization term acts diagonally:Each propagation term only couples the two clock strings adjacent to its step. The gate and its adjoint giveand $H_t|e_j⟩=0$ for $j\notin \{t-1,t\}$. The same calculation covers the two endpoint terms.

Thus both Hamiltonians preserve $\mathcal{L}$, and in the history basis their restrictions areThis history-subspace propagation Hamiltonian is a path graph Laplacian with a factor $1/2$. The specified two-clock endpoint formulas assume $T\ge 2$; a shorter circuit can first be padded with identity gates.

The matrix $D=I-|e_0⟩⟨e_0|$ is an orthogonal projection. Its eigenvalues areIts unique ground state in $\mathcal{L}$ is $|e_0⟩=|{\psi }_0⟩|0{⟩}^{\otimes T}$, and its spectral gap is one.

The history-subspace propagation Hamiltonian has diagonal entries $1/2$ at the endpoints and $1$ in the interior, and nearest-neighbour entries $-1/2$. The spectrum of a path propagation Hamiltonian isTo see the indexing directly, set $q_k=\pi k/(T+1)$ and $f_t=\cos [q_k(t+1/2)]$. The interior difference equation gives $Ef=(1-\cos q_k)f$. The endpoint equations correspond to $f_{-1}=f_0$ and $f_{T+1}=f_T$, both satisfied by these $q_k$. The $T+1$ distinct eigenvalues and their nonzero eigenvectors exhaust the matrix.

The zero eigenvalue is simple, soThe inequality uses $\sin x\ge 2x/\pi$ on $[0,\pi /2]$ and $1-\cos q=2{\sin }^2(q/2)$.

The supplied path-matrix hint sums through $i=N$ while listing a basis ending at $N$. That last summand would introduce an extra vertex. The matrix derived in (a) has exactly $T$ edges and $T+1$ vertices, as used here; this also proves the needed spectrum without relying on the misindexed summation.

Because each term in the history-subspace propagation Hamiltonian is positive semidefinite, the uniform history vector has zero energy and is a ground state:Indeed every edge term annihilates the uniform coefficients. Conversely, a zero-energy vector must have equal coefficients across every edge of the connected path, so this computational history state is the unique ground state in $\mathcal{L}$. It coherently records every intermediate state of the quantum circuit.

In the history basis, $M(s)=(1-s)D+sE$ is a Hermitian tridiagonal matrix. Its first diagonal entry is $s/2$, its interior entries are $1$, its last entry is $1-s/2$, and each off-diagonal entry is $-s/2$.

The Gershgorin disc theorem confines the first row's eigenvalue to $[0,s]$, the interior rows to $[1-s,1+s]$, and the last row to $[1-s,1]$. For $0\le s\le 1/3$, the first disc is disjoint from all the others and therefore contains exactly one eigenvalue. Since $M(s)$ is positive semidefinite, that eigenvalue is the ground state energy. All other eigenvalues are at least $1-s$, while the lowest is at most $s$. Hence the Gershgorin gap bound for an adiabatic history path givesThis argument also covers $s=0$, where the first disc is the isolated point zero.

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.