Past exam of the mathematics course of the University of Cambridge / 2014 / iii / Paper 63 / 1

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.