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

Write the quantum circuit as $U=U_T\cdots U_1$, and let $V_0=I$, $V_t=U_t\cdots U_1$. Use a nonlocal quantum clock with orthonormal states $|0⟩,\dots ,|T⟩$. Let the work space include the quantum witness and the ancilla qubits. The input penalty of a history Hamiltonian is built fromIt annihilates precisely the correctly initialized ancilla qubits, leaving the quantum witness unrestricted. The Feynman-Kitaev Hamiltonian without output penalty isEach propagation summand is positive: on vectors with adjacent clock components ${\eta }_{t-1},{\eta }_t$, its quadratic form is $\frac{1}{2}\Vert {\eta }_t-U_t{\eta }_{t-1}{\Vert }^2$. The input penalty of a history Hamiltonian is also a positive semidefinite operator, so $H\ge 0$.

To verify that this is a stoquastic Hamiltonian, use the work computational basis and the clock basis. Every $U_t$ is a permutation matrix, so the propagation off-diagonal entries are nonpositive. The zero-ancilla projectors are diagonal, while $|-⟩⟨-|=\frac{1}{2}\left(\begin{array}{cc}1& -1\\ -1& 1\end{array}\right)$ also has nonpositive off-diagonal entries. No positive off-diagonal entry is introduced by summing these terms. Thus $H$ is positive semidefinite and stoquastic, with no output penalty.

The construction uses the abstract $T+1$ dimensional clock space. A binary implementation needs diagonal penalties for unused clock labels. The clock transitions are nonlocal; the construction alone does not establish fixed qubit locality of an ordinary local Hamiltonian problem.

For an arbitrary vector $|\Psi ⟩={\sum }_{t=0}^T|{\eta }_t⟩|t⟩$, the preceding positive quadratic forms show that zero energy requiresThus all its clock components are generated by one correctly initialized input. Ifthen $\ker Q$ consists of $|\zeta ⟩\otimes |a⟩$, with unrestricted quantum witness $\zeta$. Normalization gives the computational history stateConversely, every such computational history state annihilates every propagation term and the input term, hence has zero energy. These states are exactly the ground space, not merely examples of its vectors. In particular, histories of computational basis quantum witnesses span the ground space; their coherent superpositions are also zero-energy states.

Another way to see the propagation constraint is to conjugate by $W={\sum }_t{V}_t\otimes |t⟩⟨t|$. Then $W^{†}{H}_{\mathrm{prop}}W=I\otimes E$, whereThe spectrum of a path propagation Hamiltonian has a unique uniform clock zero mode. This is the path with $T+1$ vertices. The upper summation index in the printed auxiliary formula must be $T-1$, rather than $T$, to agree with its stated dimension and spectrum; using $T$ would introduce an extra vertex.

Use the unitary change of basis from part (b). It reduces the Feynman-Kitaev Hamiltonian to $A+B$, whereThe positive eigenvalues of $Q$ are positive integers, since its commuting ancilla projectors act on different qubits. The positive spectral gap of $B$ is $1-\cos (\pi /(T+1))\ge 2/(T+1{)}^2$. Thus both positive spectra are bounded below by $\mu \ge 2/(T+1{)}^2$, for $T\ge 1$.

Let $|u⟩=(T+1{)}^{-1/2}{\sum }_t|t⟩$, and split the work space into $G=\ker Q$ and $G^{\perp }$. The common ground space is $K=G\otimes |u⟩$. A unit vector in $\ker B$ orthogonal to $K$ has the form $|z⟩|u⟩$, where $z\in G^{\perp }$. Its orthogonal projection onto $\ker A$ simply removes its time-zero component, so the projected norm is $\sqrt{T/(T+1)}$. Consequently the smallest angle between two subspaces, after removing their common intersection, satisfiesThe Kitaev geometrical lemma now givesHere $1-\sqrt{1-x}\ge x/2$ supplies the penultimate step. HenceIf there are no input constraints, $Q=0$ and the propagation gap is already $\Omega (T^{-2})$, which is stronger.

The printed geometric-lemma notation needs a correction: the maximum overlap defines $\cos \vartheta$, not $\vartheta$, and is taken over normalized vectors in the two kernels, with the common ground space removed. The ground space restriction is essential when many quantum witnesses are allowed.

For a normalized computational history state, the output projector sees only its final clock component. With $p_{+}(\zeta )$ the quantum circuit's acceptance probability,This proves the hint, including for a computational basis quantum witness. Moreover $H_{\mathrm{out}}=|-⟩⟨-{|}_1\otimes |T⟩⟨T|$ is a stoquastic Hamiltonian term, so adding it with positive coefficient preserves stoquasticity.

There are two substantive problems with the stated promise. First, for any basis quantum witness the initialized state has nonnegative amplitudes, and every permutation matrix preserves them. Write the output as $|0⟩|r_0⟩+|1⟩|r_1⟩$, with both vectors entrywise nonnegative. ThenThe stoquastic acceptance floor rules out the printed one-third soundness condition. There are no NO instances of that literal promise. Second, the ground space includes histories of arbitrary quantum witnesses. It is the maximum over those quantum witnesses, not the maximum over basis quantum witnesses, that determines the lowest output energy. Even the identity quantum circuit accepts each basis input with probability $1/2$, but accepts a $|+⟩$ quantum witness with probability one. Thus a basis-witness soundness bound would not control this Hamiltonian, even if its numerical threshold were repaired.

The requested nontrivial hardness statement therefore needs the standard quantum-witness StoqMA promise, with $1/2\le b<a\le 1$ and inverse-polynomial gap $\gamma =a-b$. The intended reduction can be completed precisely under that corrected promise. Define the quantum witness embedding $J|\zeta ⟩=|\zeta ⟩|a⟩$ and the witness acceptance operatorIt is a positive contraction, and $p_{\max }={\lambda }_{\max }(F)$. The minimum expectation of $H_{\mathrm{out}}$ on the history ground space is $\nu =(1-p_{\max })/(T+1)$. This is also consistent with a nonnegative optimal StoqMA quantum witness: $F$ is entrywise nonnegative, so replacing amplitudes by their absolute values cannot decrease its quadratic form.

A uniform ground-space perturbation bound is needed because the gap shrinks with quantum circuit length. Put $g=(T+1{)}^{-3}$, and choose a positive inverse-polynomial coefficientFor $P$ the history ground projector and any unit vector $\psi =p+q$ with $p=P\psi$, the operator norm bound $\Vert H_{\mathrm{out}}\Vert =1$ givesThe last inequality completes the square in $\Vert q\Vert$ and uses $0\le \nu \le 1$. Testing a ground space minimizing vector gives the upper bound ${\lambda }_{\min }(H^{\prime })\le \delta \nu$. Since $\delta <g/2$, we obtainYES instances of the corrected promise have energy at most $\delta (1-a)/(T+1)$; NO instances have energy at leastThe separation is at least $7\delta \gamma /[8(T+1)]$, an inverse polynomial. The quantum circuit and all these Hamiltonian terms have polynomial-size descriptions. This proves StoqMA hardness for the local Hamiltonian problem variant that permits the nonlocal clock, under the corrected quantum witness and acceptance promise.

The printed perturbation formula also has $H_{\mathrm{out}}$ where a general perturbation $V$ belongs. Its unspecified $O({\delta }^2)$ cannot be treated as uniform in a closing gap. Likewise a circuit-length-independent constant $\delta$ cannot in general satisfy the stated small-perturbation requirement for an arbitrary long quantum circuit. The explicit bound above avoids both issues; it does not claim the defective literal promise defines standard StoqMA.

BQP consists of promise problems decided by a uniform family of polynomial-size quantum circuits. On input $x$, with polynomially many zero-initialized ancilla qubits, a designated output measurement accepts with probability at least $2/3$ on YES inputs and at most $1/3$ on NO inputs. Uniformity means a classical polynomial-time procedure produces the quantum circuit description from the input length, or equivalently produces the verifier quantum circuit with $x$ supplied as input.

For BQP error reduction, run independent copies with freshly initialized registers. If the completeness and soundness thresholds are any constants $a>b$, accept when the fraction of accepting trials exceeds $(a+b)/2$. A Hoeffding inequality bounds either error by $\exp [-r(a-b{)}^2/2]$, with $r$ repetitions. The threshold need not be a simple majority when both $a$ and $b$ lie on the same side of $1/2$.

Choosing $r$ sufficiently large gives the usual $2/3,1/3$ thresholds, or any other fixed separated thresholds. Even an inverse-polynomial gap can be amplified using polynomially many repetitions. Classical threshold evaluation can be incorporated into the uniform computation. Thus fixed separated acceptance probabilities define the same BQP class. This argument concerns unrestricted BQP quantum circuits and does not assume such amplification is available for restricted stoquastic circuits.

The class $C$ uses polynomial-register real-arithmetic computation: its storage restriction counts real registers, without limiting their precision or the running time. Use the usual decision-model interpretation that computed real values may be compared with fixed thresholds, and that the fixed universal gate set's real constants are available. Without a way to test values, arithmetic instructions alone would not specify the intended decision model.

Let a BQP quantum circuit use $q=\mathrm{poly}(n)$ qubits and $T=\mathrm{poly}(n)$ gates. A matrix element can be evaluated by depth-first quantum circuit path summation:Enumerate the intermediate $q$-bit strings recursively. Store the current strings and loop positions, a partial product, and the partial sum at each depth. There are at most $T$ active levels, using $O(qT)$ registers or bits of loop information, not an exponentially long state vector. Each fixed-locality gate matrix element is computed from its few affected bits. Represent a complex number by two real registers; complex multiplication and addition require only real addition, subtraction and multiplication.

Recompute this amplitude separately for every final string $z$ whose output bit is one, accumulating the Born rule probabilityThe outer enumeration needs only another $O(q)$ bits and a real accumulator. Arbitrarily large running time is allowed, so repeated recomputation is harmless. Compare $p_1$ with $1/2$ to distinguish the promised BQP cases. This proves $\mathrm{BQP}\subseteq C$ using polynomial storage.

The printed probability hint omits the squares of the amplitude moduli. Summing their absolute values alone is not the Born rule and can exceed one. The corrected sum above is necessary for the containment proof. The argument is about the stated real-register model, rather than a claim that exponential-precision numbers are free in an ordinary bit-cost model.

QMA is the class of promise problems for which a uniform polynomial-size quantum circuit checks a polynomial-size quantum witness. A YES instance has some quantum witness accepted with probability at least $2/3$; on a NO instance every quantum witness is accepted with probability at most $1/3$. The verifier initializes its own ancilla qubits to zero. Mixed quantum witnesses do not improve the maximum because acceptance is linear in their density operator.

For a verifier $U_x$ and quantum witness embedding $J|w⟩=|w⟩|0\cdots 0⟩$, define the witness acceptance operatorThe Rayleigh quotient gives ${\max }_{\Vert w\Vert =1}⟨w|F|w⟩={\lambda }_{\max }(F)$. Every entry of $F$ can be recomputed by the polynomial-storage path summation of part (b); no full quantum witness matrix needs to be stored.

Let the quantum witness have $m$ qubits, so its dimension is $D=2^m$. For this positive operator, trace-power witness optimization usesThis is the useful exponentiated form of the supplied logarithmic inequality. Positivity is required; such a logarithmic statement is not true for an arbitrary operator. No logarithms or roots need to be calculated.

Choose $d=2m+2$. On a NO instance,since $2^m(2/3{)}^{2m+2}=(4/9)(8/9{)}^m<1$. On a YES instance, $\mathrm{Tr}(F^d)\ge (2/3{)}^d>(1/2{)}^d$. Thus comparison of $2^d\mathrm{Tr}(F^d)$ with one distinguishes the cases using only multiplication and a final comparison.

Evaluate the trace byThere are $d=O(m)$ active quantum witness indices, each requiring $m$ bits. Accumulate one product at a time and recompute its matrix entries as required. Together with the verifier path workspace, this uses polynomially many real registers. The potentially enormous time and the numerical precision are unrestricted in $C$. Therefore $\mathrm{QMA}\subseteq C$, without solving an exponentially large eigenvalue problem by storing its matrix.

First take disjoint supports $X,Y$, the setting in which the displayed Lieb-Robinson bound can hold with an $e^{2kst}-1$ factor. For overlapping supports a nonzero equal-time commutator is possible, whereas that factor vanishes at $t=0$.

Iterate the given integral inequality for $C_A(Y,t)$. At time zero, $C_A(Y,0)=0$ if $Y$ misses $X$, and in general $C_A(Y,0)\le 2\Vert A_X\Vert$. Define the positive interaction-chain weightsThe Lieb-Robinson interaction-chain expansion givesThe ordered time integrations produce $|t{|}^n/n!$. For a finite system the iterative remainder tends to zero, since the total interaction weights are finite and the factorial dominates repeated integrations.

For the interaction distance convention counting the fewest interacting hyperedges needed to connect disjoint supports, $a_n=0$ when $n<d(X,Y)$. The per-site interaction bound givesDropping the final endpoint restriction consequently bounds $a_n\le |Y|(ks{)}^n{e}^{-\mu n}$. Reversing the chains gives the same estimate with $|X|$. ThereforeMultiply by $\Vert B_Y\Vert$ and sum the exponential series to obtainFor overlapping supports, retain the initial term. A valid general version adds $2\Vert A_X\Vert \Vert B_Y\Vert 1_{X\cap Y\ne \varnothing }$ to the right side. A coarser bound with $e^{2ks|t|}$ in place of $e^{2ks|t|}-1$ is also sufficient for later shell estimates, with the conventional support distance zero on overlaps. Thus the printed bound needs disjoint supports or an equal-time term. The printed $C(Z,s)$ and $O_Z$ inside a supremum over $O_Y$ are also inconsistent labels; the iteration uses $C_A(Z,\tau )$ and $O_Y$.

Let $U(t)=e^{-itH}$. Define the second initial state by $|{\tilde{\psi }}_0⟩=U(t{)}^{†}|{\psi }_2⟩$, while $|{\psi }_0⟩=U(t{)}^{†}|{\psi }_1⟩$. The unitary time evolution preserves their inner product:Both initial states are normalized and evolve to the chosen final pair. This supplies the orthogonal partner needed for topological quantum order. The remaining requirement is local indistinguishability, which is proved in the next condition's solution.

Write the final topological quantum order constants as $a>0$ and $\epsilon <1$, to avoid confusing the allowed support diameter with the small time coefficient. For any initial operator $A_X$ of operator norm at most one,and similarly for the partner state. The minus sign follows from $|{\psi }_0⟩=e^{itH}|{\psi }_1⟩$ and the Heisenberg picture convention $A_X(t)=e^{itH}{A}_X{e}^{-itH}$. The Lieb-Robinson bound and its localization corollary apply to either time direction, using $|t|$.

Choose $\mathrm{diam}(X)\le aL/4$, $t=\tau L$ with $v\tau \le a/8$, and localization buffer $l=aL/8$. The enlarged support $X^{\prime }$ obeysThe Lieb-Robinson localization by Haar twirling corollary supplies an operator $B_{X^{\prime }}$ approximating $A_X(-t)$ withDo not assume that the approximate operator has norm at most one: it only has $\Vert B_{X^{\prime }}\Vert \le 1+{\delta }_L$. Apply final-state local indistinguishability to $B_{X^{\prime }}/(1+{\delta }_L)$. The two approximation errors then giveIf the lattice has polynomially many sites in its diameter, $N(L)=O(L^p)$, the error tends to zero uniformly in these supports. For sufficiently large $L$, take ${\delta }_L\le (1-\epsilon )/[2(\epsilon +2)]$. The initial pair is then indistinguishable within ${\epsilon }^{\prime }=(1+\epsilon )/2<1$ on supports of diameter at most $aL/4$. Together with the exact orthogonality from condition (i), this proves the initial state is topologically ordered for sufficiently small linear-time coefficient. The constants for initial and final order need not be identical.

The backward preservation of local indistinguishability has an explicit finite-system qualification: it holds whenever the displayed $L|X|e^{-\mu aL/16}$ error is small enough. The conventional bounded-density, fixed-dimensional lattice interpretation supplies that condition. The question leaves growth control implicit; for an arbitrary collection of qudits one cannot discard the $|X|$ prefactor merely because $L$ is large. This identifies exactly the assumption needed by the supplied localization proof.

Use the Fourier transform convention $\hat{w}(E)={\int }_{\mathbb{R}}w(t)e^{itE}dt$. Since $w\ge 0$, it is real, so $\hat{w}(-E)=\hat{w}(E{)}^{\ast }$. The positive-frequency cutoff therefore also eliminates frequencies at or below $-\Delta$. Normalization gives $\int w=\hat{w}(0)=1$.

For spectral filtering of Hamiltonian terms, chooseIn an energy eigenbasis, its matrix elements areAt $i=j=0$ the frequency is zero, so the normalization preserves the ground-state expectation:The spectral filter is a positive weighted average of unitary conjugations; in particular the integral is bounded in operator norm by $\Vert h_Z\Vert$. We can choose it even without an extra assumed tail bound: the evenization of a nonnegative bandlimited filter proved in part (e) produces another admissible spectral filter with the same type of positive-time decay. Make that choice consistently in all the filtered terms and shell definitions below.

For an excited eigenstate, $E_i-E_0\ge \Delta$. The matrix-element identity in condition (i), together with the two-sided Fourier cutoff, givesThe reverse matrix element has frequency $E_0-E_i\le -\Delta$ and also vanishes. Equivalently, $A^{(Z)}$ is Hermitian because $h_Z$ is Hermitian and $w$ is real, so the two elements are conjugate. ThusThe spectral gap eliminates precisely the couplings needed to make the unique ground state an eigenvector of every filtered term. Couplings between excited states with smaller energy differences can remain; the spectral filter need not diagonalize the whole operator.

Sum the spectral filtering of Hamiltonian terms over the original finite decomposition. The total Hamiltonian operator commutes with its own evolution, soThe absence of all ground-to-excited matrix elements, proved in part (a), makes each filtered term block diagonal relative to $P_0=|{\varphi }_0⟩⟨{\varphi }_0|$ and its orthogonal complement. ThereforeA filtered term may act on the whole system, since unitary time evolution spreads its original support. Neither commutation with $P_0$ nor preservation of its ground-state expectation asserts that the global ground state minimizes each individual term. In particular, this construction does not generally turn a frustrated decomposition into a frustration-free Hamiltonian.

For a fixed original term, define $F_d(h_Z)=\int w(t)e^{it{H}_d}{h}_Z{e}^{-it{H}_d}dt$. The shell increment is exactly $A^{(Z,d)}=F_d(h_Z)-F_{d-1}(h_Z)$. Hence the telescoping local-shell decomposition givesUse the printed endpoint convention $H_0=h_Z$ and $H_D=H$. The first endpoint is $F_0(h_Z)=h_Z\int w=h_Z$, because $h_Z$ commutes with its own evolution, and the second is the operator chosen in part (b). ThusThere is a distance-convention issue in the endpoint assertion. The usual minimum distance between supports is zero for overlapping distinct interactions, so a literal $H_0={\sum }_{Y:d(Z,Y)=0}{h}_Y$ need not equal $h_Z$ or commute with it. To realize the stated $H_0=h_Z$, index the neighborhoods by distance between interaction terms: the central term has shell zero, and other terms begin in positive shells. For example, for distinct terms use one plus their support interaction distance. With the ordinary overlapping-support convention left unchanged, the exact formula instead begins with $F_0(h_Z)$, not necessarily with $h_Z$. The telescoping identity itself is valid in either convention.

Put $\lambda =2ks$. For $t\ge 0$, apply a valid Lieb-Robinson bound to each commutator in the supplied comparison of the two evolutions. For a disjoint shell at support distance $d$,In the usual uniform interaction-norm setting, truncation preserves the strength bound, so the same constants apply to $H_d$. The given polynomial shell-weight hypothesis and $e^{\lambda \tau }-1\le e^{\lambda t}$ now giveConsequentlyThe question explicitly supplies a bound for the full $H$; such a bound alone should not be assumed to transfer to $H_d$. A full-evolution comparison for truncated dynamics avoids that additional assumption. The Duhamel comparison formula givesNow use only the full-Hamiltonian bound, and sum the shell weights. Since ${\sum }_{q\ge d}{q}^{\alpha }{e}^{-\mu q}=O(d^{\alpha }{e}^{-\mu d})$, the errors for $j=d$ and $j=d-1$ are each bounded by $O(\Vert h_Z\Vert |t|d^{\alpha }{e}^{-\mu d+\lambda |t|})$. The triangle inequality comparing both evolutions to ${\tau }_t^H(h_Z)$ proves the same boxed estimate from the stated full-system assumption. Negative times follow by the reverse-time Duhamel formula; the commutator bounds use $|t|$.

For the interaction-term shells used to enforce $H_0=h_Z$, shell $d$ corresponds to support distance $d-1$ for distinct terms. Replace the displayed commutator estimate by the coarser bound with $e^{\lambda \tau }$, retaining the equal-time contribution for overlaps. Its distance factor is $e^{-\mu (d-1)}=e^{\mu }{e}^{-\mu d}$, and the fixed factor $e^{\mu }$ is absorbed by the big-O constant. This supplies the same claimed shell estimate without incorrectly using a zero equal-time bound for overlapping terms.

The filtered shell integral uses both signs of time, while the stated decay hypothesis controls only positive time. Here is a way to choose an even admissible spectral filter from the given one, rather than silently assume that its negative tail is controlled. Call the supplied spectral filter $f$. Reality and its Fourier cutoff imply that $\hat{f}$ is supported in $[-\Delta ,\Delta ]$. It is bounded and integrable in frequency, so Fourier inversion supplies a bounded continuous representative of $f$. That representative is real analytic, since its Fourier support is compact, and is not identically zero.

Define the evenization of a nonnegative bandlimited filter byThe normalizing integral is finite and positive: boundedness and integrability give finiteness, while a nonzero real-analytic nonnegative function cannot vanish on an interval, so the product is positive on some interval. The new spectral filter is even, nonnegative and normalized. Each factor has Fourier support in $[-\Delta /2,\Delta /2]$, and the convolution rule for the product therefore gives support in $[-\Delta ,\Delta ]$, including vanishing at the outer endpoints. Its positive tail is bounded byIt has the same required tail form, with a rescaled positive constant $\beta$. Since $w$ is even, its two-sided tail is twice its positive tail. The preceding parts use this chosen $w$ consistently.

For the almost-exponential locality of filtered Hamiltonian terms, split the integral defining $A^{(Z,d)}$ at $|t|=T_d$. Write $\lambda =2ks>0$ and choose $T_d=\mu d/(2\lambda )$. On the short-time part, part (d) and $\int w=1$ giveFor the long-time part, each conjugated operator has norm $\Vert h_Z\Vert$, so their difference has norm at most $2\Vert h_Z\Vert$. The two-sided spectral filter tail givesLet $c=\beta \mu /(2\lambda )>0$, so $\beta T_d=cd$. The logarithmic prefactor is bounded by $O(d^{\alpha +1})$, and the first, exponentially decaying contribution is asymptotically smaller than this almost-exponential contribution. ThereforeThis is an asymptotic statement for large $d$; small shells have the elementary bound $2\Vert h_Z\Vert$, avoiding the meaningless substitution $cd=1$ into the logarithmic expression. If $ks=0$, there is no dynamical spreading and the shell increments vanish. Filtering gives almost-exponentially decaying shells despite the filtered operator's potentially global support.