Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 324 (Quantum Computation)

A strong classical simulation of a quantum circuit computes any requested output probabilityin polynomial time, to the prescribed inverse-polynomial accuracy. A weak classical simulation of a quantum circuit instead produces classical samples from the circuit's output distribution, with exact or suitably small total-variation error.

The Extended Gottesman--Knill theorem states that a unitary Clifford circuit with an arbitrary product state input and final computational-basis measurements is weakly classically simulable. It is strongly simulable when only $O(\log n)$ output qubits are measured. Indeed, each joint output projector expands into $2^k$ Pauli operators, and Clifford conjugation maps every such operator to another Pauli operator whose expectation factors over the input qubits. The factor $2^k$ is polynomial precisely for $k=O(\log n)$.

Choose a Clifford operation $D$ with $D|0^n⟩=|\sigma ⟩$ and absorb $D$ into the circuit. Push each subsequent Clifford gate forward through the computation. A computational-basis measurement made after a Clifford prefix $U$ becomes a Pauli measurementon the initial state, because Clifford conjugation preserves the Pauli group. Adaptivity merely makes the next Pauli depend on earlier classical outcomes.

It remains to eliminate the $n$ stabilizer qubits. Maintain their current stabilizer group. For a Pauli $P$ to be measured, there are two cases.

maps the old stabilizer sector into the $\lambda$ eigenspace of $P$. Updating the Clifford frame by $V_{\lambda }$ removes this measurement while conjugating every later Pauli to another Pauli.

Iterating this procedure leaves an adaptive Pauli-based computation on $|\rho ⟩$. The same classical outcomes determine every adaptive choice and final output, so this gives a weak classical simulation. Every postselected $Z$ outcome becomes either a fixed classical $+1$ branch or a postselected $+1$ Pauli measurement, as required.

Put $P_1={\sigma }_1\otimes {\sigma }_2$ and $|\psi ⟩=|A{⟩}^{\otimes 2}$. After the first Hadamard gate and the two controlled Pauli gates, the joint state isThe final Hadamard gate changes this toConditioned on ancilla outcome $s\in \{0,1\}$, the normalized data state is therefore

Write the input in the two eigenspaces of $P_1$ aswhere the displayed eigenstates are normalized. A direct PBC measurement giveswith probabilities $|\alpha {|}^2$ and $|\beta {|}^2$. Hence the ancilla circuit and the Pauli measurement have identical outcome distributions and conditional data states after identifying the Pauli outcome with $(-1{)}^s$.

Use the standard ancilla-assisted Pauli measurement. To measure a Pauli $P$, reset the ancilla to $|0⟩$, apply $H$, apply the controlled version of every nonidentity factor of $P$ with the ancilla as control, apply $H$ again, and measure the ancilla in the computational basis. The preceding calculation shows that outcome $s$ projects the data with

First use this circuit with $P_1=Z\otimes I$, obtaining $s_1$. Since the measured ancilla is $|s_1⟩$, apply the classically controlled correction $X^{s_1}$ to reset it to $|0⟩$. Reuse it to measure $P_2=Z\otimes X$, obtaining $s_2$. All controlled Pauli gates and single-qubit corrections are Clifford gates. Since $P_1{P}_2=P_2{P}_1$, the final data state isThus one resettable ancilla implements both measurements of the PBC without disturbing the already measured Pauli eigenvalue.

Let the spectral decomposition of the Hermitian matrix beThe HHL algorithm proceeds as follows.

Efficiently prepare the normalized amplitude encoding $|b⟩$.
Apply quantum phase estimation to the simulated evolution $e^{iAt}$, producing an approximation of each eigenvalue: Add one ancilla and perform an eigenvalue-controlled rotationwhere $0<C\le {\min }_j|{\lambda }_j|$.
Uncompute the eigenvalue register. Conditional on measuring the ancilla as $1$, the system register isThe postselection probability can be increased with amplitude amplification.

The ingredients used here are efficient sparse Hamiltonian simulation of $e^{iAt}$ and quantum phase estimation, which converts an eigenphase of that evolution into a binary approximation of ${\lambda }_j$. For sparsity $s$, condition number $\kappa$, and error $ϵ$, the cost is polynomial in $s$, $\kappa$, $1/ϵ$, and $\log N$ under the stated access assumptions.

Finally estimate $⟨x|M|x⟩$ by repeated measurement of an efficient observable decomposition of $M$, or by a Hadamard test when $M$ is unitary. A general efficiently block-encoded Hermitian $M$ can similarly be measured through its block encoding. Repetition and a concentration inequality give additive sampling error $O(1/\sqrt{R})$ after $R$ independent preparations.

The essential requirement is an efficient quantum state preparation circuit $B$ satisfyingA standard sufficient promise is that $b$ has only $\mathrm{poly}(\log N)$ nonzero components, with their positions and values classically computable to the required precision in $\mathrm{poly}(\log N)$ time, and with efficiently computable normalization. More structured dense vectors are also allowed whenever cumulative weights or an equivalent data-access oracle permit amplitude encoding in polylogarithmic time. Without such a promise, merely loading $N$ arbitrary classical entries already costs $\Omega (N)$ and removes the claimed exponential dependence on dimension.

Use reversible quantum arithmetic on an ancillary work register. On each computational-basis branch, computewhereBecause the classical algorithms for $A_i$ and $B_i$ are efficient, they can be made reversible with polynomial overhead. Reversible division, square root, and inverse cosine to the retained binary precision likewise use $\mathrm{poly}(\log N)$ gates under the question's precision convention. Uncompute the $A_i$ and $B_i$ work registers, leaving

Suppose the angle register stores a fixed-point expansion ${\theta }_i={\sum }_{r=1}^q{\theta }_{ir}{2}^{-r}{\theta }_{\max }$. Append a target qubit in $|0⟩$. For each angle bit $het{a}_{ir}$, apply to the target a controlled $R_y(2^{1-r}{\theta }_{\max })$. Rotations about the same axis commute, so their product is $R_y(2{\theta }_i)$ andWith $q=O(\mathrm{poly}\log N)$ retained bits, each controlled rotation decomposes into one- and two-qubit gates and the complete quantum variable rotation has polylogarithmic size. Thus the required branchwise map is implemented coherently for every $i$.

The ratio $f_i=A_i/B_i$ is the conditional probability that $X$ lies in the left half of interval $i$. After the controlled rotation and uncomputation of $|{\theta }_i⟩$, append the rotation qubit to the interval label. The amplitudes becomeButConsequently one refinement step mapsStarting from $|{\psi }_1⟩$ and repeating this hierarchical probability-distribution state preparation for $m=1,\dots ,n-1$ givesThere are $n-1=O(\log N)$ refinement levels, each of polylogarithmic size by assumption.

Let ${\Pi }_G$ be the orthogonal projection onto $G$. The two reflection operators areThe first fixes the hyperplane $|\psi {⟩}^{\perp }$ and changes the sign of $|\psi ⟩$; the second fixes $G^{\perp }$ and changes the sign of $G$.

Write the normalized projections of $|\psi ⟩$ asThe amplitude amplification theorem states that forone has, up to the irrelevant global sign $(-1{)}^k$,Thus every iteration increases the angle toward the good axis by $2\theta$ until the first overshoot.

For the proof, the plane $\mathrm{span}\{|g⟩,|b⟩\}$ is invariant. In its ordered basis,Their product is a planar rotation through $2\theta$ together with an overall sign. Applying that matrix $k$ times proves the formula, while components orthogonal to this plane never enter the initial state.

If some integer $k$ obeys $(2k+1)\theta =\pi /2$, ordinary amplitude amplification already gives $|g⟩$ exactly. For a general known $\theta$, use exact amplitude amplification. Choose $k$ so thatand put $c=\sin {\theta }^{\prime }/\sin \theta \le 1$. Append an ancilla and coherently arrange that its designated good value has amplitude $c$ conditional on the original register being good. With the enlarged good subspace defined bythe starting state's total good amplitude is $c\sin \theta =\sin {\theta }^{\prime }$.

Apply the amplitude amplification theorem $k$ times to this enlarged problem. Its final good amplitude isThe Boolean quantum oracle implements the reflection $I_G$ by phase kickback, and the known state-preparation circuit implements the reflection about the starting state by prepare--reflect--unprepare. A final computational-basis measurement therefore yields an $x$ with $f(x)=1$ with certainty.

At trial $k$, the amplitude amplification theorem gives success probabilityBecause the state is prepared afresh, the probability that the first success occurs at $k$ isIf one application of $R$ uses a constant number of oracle calls, reaching and performing trial $k$ costs a total of order $1+2+\cdots +k=\Theta (k^2)$ calls. Equivalently,For $k\theta \ll 1$, use $\log {\cos }^{2}x=-x^2+O(x^4)$ andto obtainThe first successful index is therefore typically $k^{\ast }=\Theta ({\theta }^{-2/3})$, andwhere $n^{\ast }=\Theta (1/\theta )$ is the first near-optimal Grover iteration count.

The last requested assertion in the official paper is false as printed. In fact, for small $\theta$, at least a constant fraction of the indices $j<n^{\ast }$ have $(2j+1)\theta \ge \pi /4$, and hence failure probability at most $1/2$. Consequentlyfor some constant $c>0$, rather than being bounded below by a positive constant. The reversed event $\mathrm{Pr}(k^{\ast }<n^{\ast })$ does have a positive lower bound and in fact tends to one.

Now try only $k_i=2^i$. Since $n^{\ast }=2^N=\Theta (1/\theta )$, the total work through trial $N$ is the geometric seriesFor $i<N$, the success probabilities scale asTheir sum is $O(1)$, so the product of their failure probabilities stays bounded away from zero: there is a constant probability of reaching the scale $k_N=n^{\ast }$. At that trial, the defining property of $n^{\ast }$ givesso almost all surviving runs stop there. ThereforeThe geometric amplitude-amplification schedule is asymptotically better than the sequential schedule's $\Theta ((n^{\ast }{)}^{4/3})$ calls and matches the usual Grover scaling up to a constant factor.

A computational-basis vector $|x_1{x}_2{x}_3⟩$ has eigenvalue $(-1{)}^{x_i+x_j}$ under $Z_i{Z}_j$. Simultaneous eigenvalue $+1$ for $Z_1{Z}_2$, $Z_2{Z}_3$, and $Z_1{Z}_3$ therefore requiresThe stabilizer subspace isIt is two-dimensional because the three displayed nonidentity stabilizers contain only two independent generators; indeed $(Z_1{Z}_2)(Z_2{Z}_3)=Z_1{Z}_3$.

For the controlled-NOT gate $U={\mathrm{CNOT}}_{12}$, propagation of the Pauli generators givesThus an $X$ on the control propagates forward to the target, while a $Z$ on the target propagates backward to the control.

Suppose $\tilde{V}$ has the same four conjugation rules and put $W=U^{†}\tilde{V}$. Then $W$ commutes with $X_1,X_2,Z_1,Z_2$. These generators span the full two-qubit operator algebra, so its commutant consists only of scalar multiples of the identity. Hence $W=e^{i\varphi }I$ and

Since the Hadamard gate conjugates $X$ to $Z$,For $n=1$, each exponential is $-I$, soFor $n=2$,Using $XZ=-iY$ givesso one convenient logarithm isBoth products are Clifford operations: the first is the identity and the second is a one-qubit Pauli Y gate up to global phase.

A graph state has computational-basis expansionFor the path $G_A$ with edges $(1,2)$ and $(2,3)$,For the triangle $G_B$, the extra edge $(3,1)$ changes the phase whenever $x_1=x_3=1$, giving

The graph-state stabilizer generators of the path areand those of the triangle areAny pair of distinct generators has Pauli factors $X$ and $Z$ in exactly two common positions. Each such position contributes one minus sign on exchange, so the two signs cancel. ThusThis is the general commutativity mechanism for graph-state stabilizers associated with an undirected graph.

If $S|\alpha ⟩=|\alpha ⟩$ and $|\beta ⟩=U|\alpha ⟩$, thenThus conjugating the state conjugates its entire stabilizer group.

The triangle $G_B$ is obtained from the path $G_A$ by local complementation of a graph state at vertex $2$, which toggles the edge between its neighbors $1$ and $3$. The corresponding Local Clifford operation isDirect conjugation givesThese three commuting operators generate exactly the same stabilizer group as $S_1^B,S_2^B,S_3^B$. Thereforefor an irrelevant global phase $e^{i\varphi }$.