Past exam of the mathematics course of the University of Cambridge / 2015 / iii / Paper 67 (Advanced Quantum Information Theory)

Let $R=X(l)$ and $C$ be its complement, with Hilbert-space dimension $d_C$. Use Haar twirling conditional expectation to defineThis is an operator supported on $R$. The normalization $1/d_C$ is essential: the partial trace alone would not fix an operator already supported on $R$.

Subtract the integrand from $A_X(t)$ and use the operator norm triangle inequality. Since $A-UA{U}^{†}=[A,U]U^{†}$ and every unitary operator has norm one, the assumed Lieb-Robinson bound, applied to a unitary supported on the entire complement, givesThe factor $\min (|X|,|C|)$ was bounded by $|X|$; there is no sum over sites and hence no volume-dependent prefactor.

ChooseFor $t,l\ge 0$, $e^{2kst}-1\le 2kst{e}^{2kst}$, and thereforeThus $A_{X(l)}(t)=A_R(t)$ is the desired Lieb-Robinson localization by Haar twirling. The displayed choice assumes the usual positive constants $\mu ,s$; if the interaction bound has $s=0$, the error is identically zero and any positive $v$ works. For negative times the same argument uses $|t|$.

Write $P_0=|{\psi }_0⟩⟨{\psi }_0|$ and $Q_0=I-P_0$. Frustration freeness implies that every local orthogonal projection fixes $|{\psi }_0⟩$ on both the left and right. HenceThe spectral gap makes $\mathrm{supp}H=Q_0\mathcal{H}$. The supplied detectability lemma givesConsequentlyNo assumption that $K$ is Hermitian or normal is needed.

A stronger estimate will keep this same $\alpha$ when we count the two projection layers in (ii). On $Q_0\mathcal{H}$, put $P=P_{\mathrm{odd}}-P_0$ and $Q=P_{\mathrm{even}}-P_0$. They are orthogonal projections, with $\Vert PQ\Vert \le q$. For $m\ge 1$,so the powers of a product of two orthogonal projections satisfyThis extra estimate uses the projection structure, rather than generic submultiplicativity alone.

Fix an integer radius $m\ge 0$ and put $r=\lfloor m/2\rfloor$. Starting with $A_x$, scan the $2r$ layers of $K^r$ from right to left. In each layer retain precisely those bond orthogonal projections whose supports meet the current support; multiply them onto the current operator and enlarge that support to include their bonds. Discard every other projection: it commutes through the current operator and acts as the identity on $|{\psi }_0⟩$, by frustration freeness.

If $L_r$ denotes the ordered product of the retained projections, defineEach layer expands the support by at most one lattice spacing. Therefore the local projector cone in a frustration-free chain lies within radius $2r\le m$ of $x$, andThe last equality holds because every retained projection also fixes the ground-state bra.

For $r\ge 1$, the stronger estimate from (i) givesFor $r=0$, choose $A_{x(m)}=A_x$; the error is at most $\Vert A_x\Vert$, so the same bound holds. HenceHere $\alpha$ is exactly the value in (i), and the prefactor is independent of $m$ and chain length. Counting $K^r$ as $r$ rather than $2r$ layers would give an incorrect support claim; the powers of a product of two orthogonal projections are what avoid a lost factor of two in the decay rate.

Let $d=|x-y|\ge 1$ and take $m=d-1$, so the local projector cone in a frustration-free chain for $A_{x(m)}$ does not contain $y$. It follows that $[A_{x(m)},B_y]=0$. The exact bra identity from (ii) and this commutation giveSince $P_0{A}_x|{\psi }_0⟩=⟨A_x⟩|{\psi }_0⟩$, subtracting the product of expectations yieldsThus the exponential clustering from layered projectors bound isThe connected correlation function therefore has correlation length at most $1/\alpha$ in lattice-spacing units. In particular $\alpha =\Delta /6+O({\Delta }^2)$ for a small spectral gap. The same-site case is covered by the elementary bound $2\Vert A_x\Vert \Vert B_y\Vert$.

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.

A promise problem $(L_{\mathrm{yes}},L_{\mathrm{no}})$ belongs to QMA if there are polynomials $p,q$ and a uniform family of quantum circuits $V_x$ of size at most $q(|x|)$, taking a $p(|x|)$-qubit witness and clean ancillas, with one output qubit interpreted as acceptance, such thatNo condition is imposed outside the promise. The witness may be an arbitrary density operator, and the verifier is efficient but need not know how to prepare an honest witness. Pure witnesses suffice for completeness because the acceptance probability is linear in the witness. QMA is quantum verification with polynomially many witness qubits and a constant completeness-soundness gap.

Interpret the high-success formulation as completeness at least $1-\delta (n)$ and soundness at most $\delta (n)$, where $\delta (n)\le 1/p(n)$ for a growing polynomial $p$. This is the standard error-reduction claim. Literally placing $O$ around a success probability approaching one supplies no useful lower bound; it is the failure probability that must be inverse-polynomially small.

Let $M_x$ be the quantum verifier acceptance operator acting on one witness register:Acceptance on $\rho$ is $\mathrm{Tr}(M_x\rho )$. On a NO instance, $\Vert M_x\Vert \le 1/3$; on a YES instance, an honest witness has acceptance at least $2/3$.

Ask for $r$ witness registers, with $r$ odd, run $V_x$ independently on each register with fresh ancillas, and accept a strict majority. The QMA parallel repetition with entangled witnesses acceptance operator isDiagonalize $M_x$. In the tensor-product eigenbasis, an eigenvalue of $M_x^{(r)}$ is the majority probability for independent Bernoulli random variables with parameters equal to the selected eigenvalues of $M_x$. On a NO instance every parameter is at most $1/3$. Coupling these variables using independent uniform random numbers shows that their upper majority tail is bounded by the tail with every parameter $1/3$. This bounds the operator norm and therefore covers every supplied witness, including a witness entangled across the registers. No independence assumption about a dishonest witness is being made.

For a valid Chernoff bound, if $S$ is a sum of $r$ independent Bernoulli variables of parameter at most $1/3$, Markov's inequality applied to $2^S$ yieldsAn honest product witness on a YES instance gives independent trials with rejection probability at most $1/3$, so its failure probability has the same bound. The printed concentration bound is not valid as stated: for five trials at parameter $1/3$, the upper-majority probability is $17/81>e^{-5/3}$. The valid bound above suffices for a rigorous proof.

Choose the next odd integer above $c^{-1}\ln p(n)$. ThenThe witness length and circuit size increase by only $O(\log p(n))$; the majority calculation has polynomial overhead. Conversely, inverse-polynomial failure probability is at most $1/3$ for all sufficiently large input lengths. Finitely many smaller lengths can be handled by hard-wired verifiers, giving the usual constants. Hence the two definitions give the same class QMA. The same QMA error reduction argument also yields exponentially small failure with polynomially many copies.

The local Hamiltonian problem is a promise problem specified by a sum $H={\sum }_{j=1}^M{h}_j$ on $n$ qubits, where $M$ is polynomial in $n$, each Hermitian term acts on at most a fixed number $k$ of qubits, and the terms and two thresholds $a<b$ are described with polynomially many bits. The promise gap satisfies $b-a\ge 1/\mathrm{poly}(n)$. In a convenient normalization, $0\le h_j\le I$. The task is to distinguishThere is no required answer when the minimum energy lies between the thresholds. A formulation with Hermitian terms of polynomially bounded norm is equivalent: shift each term by a known scalar lower bound and rescale all terms by a polynomial bound to obtain positive semidefinite terms of norm at most one, while shifting and rescaling $a,b$ in parallel. The promise gap remains inverse-polynomial.

Use an $n$-qubit state as the witness. Uniformly choose a term $h_j$ and perform the two-outcome positive operator-valued measure $\{I-h_j,h_j\}$. Regard the second outcome as an energy flag. For witness $\rho$, its probability isThis is an efficient local-energy measurement verification: a unitary operator on the $k$ relevant qubits and one ancilla qubit can implement the measurement using the isometryThe local dimension is constant; the term matrices and the measurement can be approximated to inverse-polynomial accuracy. Uniform choice of $j$ and the classical threshold comparison also have polynomial overhead.

SetIn the nontrivial case $0\le a<b\le M$, $\delta$ is inverse-polynomial. Cases outside this energy range are decided directly from $0\le H\le MI$.

Ask for $r$ witness registers, measure an independently sampled local term on each, and accept if the mean number of energy flags is at most $\theta$. An honest product ground state on a YES instance has flag probability at most $p_{\mathrm{y}}$. The Hoeffding inequality gives failure at most $e^{-r{\delta }^2/2}$. For completeness, the required Bernoulli concentration estimate follows by bounding the centered log moment-generating function $f(\lambda )=\ln \mathbb{E}{e}^{\lambda (Y-p)}$: $f(0)=f^{\prime }(0)=0$ and $f^{\prime \prime }(\lambda )$ is a tilted Bernoulli variance, at most $1/4$. Hence $f(\lambda )\le {\lambda }^2/8$; exponential Markov's inequality optimized at $\lambda =4u$ yields $\mathrm{Pr}(\overline{Y}-p\ge u)\le e^{-2r{u}^2}$, and the lower-tail version follows in the same way.

Soundness must also cover entangled witness registers. The averaged flag effect is $R=H/M$. All its eigenvalues are at least $p_{\mathrm{n}}$ on a NO instance. The repeated verifier's acceptance effect is a polynomial in the commuting tensor-factor operators $R_j$ and $I-R_j$. In their product eigenbasis its eigenvalues are lower-tail probabilities of independent Bernoulli variables whose parameters are each at least $p_{\mathrm{n}}$. Their lower tail is bounded by the identical-parameter tail at $p_{\mathrm{n}}$, using the same uniform-variable coupling as in QMA parallel repetition with entangled witnesses. Therefore its operator norm is at most $e^{-r{\delta }^2/2}$, which bounds acceptance for any entangled witness.

Choosinggives completeness at least $2/3$ and soundness at most $1/3$. A slightly larger constant absorbs implementation errors; for example, approximate each flag effect in norm to at most $\delta /8$, retain a gap at least $3\delta /4$, and increase $r$ by a constant factor. The total witness length $rn$ and circuit size are polynomial. Thus

Here is a finite-dimensional form of the Kitaev geometrical lemma. Let $A,B$ be positive operators, with nullspaces $S_A,S_B$ and all positive eigenvalues at least $\gamma >0$. First assume $S_A\cap S_B=\{0\}$. Let $P,Q$ be the orthogonal projections onto those nullspaces, and define their smallest angle between two subspaces byIf either nullspace is zero, set $\cos \vartheta =0$. Then

To prove it, spectral decomposition gives $A\ge \gamma (I-P)$ and $B\ge \gamma (I-Q)$. Write $C=P+Q$ and $c=\cos \vartheta$. For every vector $z$,Thus $C^2\le (1+c)C$. Since $C$ is positive semidefinite, each of its eigenvalues lies in $[0,1+c]$, so $2I-C\ge (1-c)I$. Consequentlyas claimed.

If there is a common nullspace $S=S_A\cap S_B$, restrict to $S^{\perp }$ and define the angle between $S_A\cap S^{\perp }$ and $S_B\cap S^{\perp }$ there. The same proof bounds the smallest positive eigenvalue of $A+B$ by $2\gamma {\sin }^2(\vartheta /2)$, while $S$ is its zero-energy subspace. This version gives a spectral gap above a possibly degenerate ground state space.

Use the Fourier transform convention $\hat{w}(E)={\int }_{\mathbb{R}}w(t)e^{itE}dt$ and define the spectral filtering of Hamiltonian terms byThe normalization $\hat{w}(0)=1$ means $\int w=1$. Since $w$ is real and nonnegative, $\hat{w}(-E)=\overline{\hat{w}(E)}$. Thus the stated positive-frequency cutoff also implies $\hat{w}(E)=0$ for $E\le -\Delta$. The integral exists in operator norm, because its integrand has norm at most $w(t)\Vert h_Z\Vert$.

Let $H|{\varphi }_i⟩=E_i|{\varphi }_i⟩$, with $E_i-E_0\ge \Delta$ for $i>0$. In this eigenbasis,Every matrix element coupling the unique ground state to an excited state vanishes, in either direction. HenceMoreover, linearity and conservation of $H$ under its own Heisenberg picture evolution giveEach filtered term is Hermitian, but it need not remain supported on its original set $Z$. The tail assumption supplies stronger long-time control than the integrability used here; no additional tail estimate is needed for the requested identities.

For each interaction neighbourhood, setThen the shell term is $g^{(Z,s)}=G_s^{(Z)}-G_{s-1}^{(Z)}$. Since $H_0=h_Z$, its conjugation leaves $h_Z$ fixed, so $G_0^{(Z)}=h_Z\int w=h_Z$. Since $H_D=H$, $G_D^{(Z)}$ is precisely the choice of $g^{(Z)}$ from (b). Therefore the telescoping local-shell decomposition givesNo limiting interchange is needed: the sum has finitely many shells. Each $G_s^{(Z)}$ is supported within the union of supports appearing in $H_s$ together with $Z$, because its unitary time evolution acts trivially outside that neighbourhood. The individual shell terms need not commute with the full ground state projector; the full filtered sum does.

The filtered decomposition is not necessarily frustration-free. Commuting with $P_0$ makes $|{\varphi }_0⟩$ an eigenvector of each term; it does not make that eigenvector a lowest-energy state of each term. This is the distinction expressed by commuting with a ground projector does not imply frustration freeness.

For an explicit positive, two-local counterexample on three qubits, let $P_0^{(i)}=|0⟩⟨0{|}_i$ and $P_1^{(i)}=|1⟩⟨1{|}_i$, and use the two distinct interaction sets $\{1,2\}$ and $\{2,3\}$:Both are positive semidefinite and commute with their sum. The total energy on a computational basis vector isThus $H=h_{12}+h_{23}$ has unique ground state $|000⟩$, energy $1$, and spectral gap $1$. Since $[H,h_{12}]=[H,h_{23}]=0$, spectral filtering of Hamiltonian terms leaves both terms unchanged for every normalized filter:But $h_{12}|000⟩=|000⟩$, whereas $h_{12}|010⟩=0$. The global ground state therefore does not minimize $g^{(12)}$, proving that the resulting decomposition is not a frustration-free Hamiltonian.

There is a useful positive result if the original decomposition already is a frustration-free Hamiltonian. If $a_Z={\lambda }_{\min }(h_Z)$ and $h_Z|{\varphi }_0⟩=a_Z|{\varphi }_0⟩$, then $h_Z-a_{Z}I\ge 0$. Averaging its unitary conjugates with nonnegative $w$ gives $g^{(Z)}-a_{Z}I\ge 0$, while $g^{(Z)}|{\varphi }_0⟩=a_Z|{\varphi }_0⟩$. Thus filtering preserves existing frustration freeness; it does not create it for an arbitrary gapped Hamiltonian.