Past exam of the mathematics course of the University of Cambridge / 2014 / iii / Paper 61 (Quantum Computation)

Use the positive-sign quantum Fourier transformOrthogonality of the finite-group characters makes $F_N$ a unitary operator. Here $r$ is the least positive period. The injectivity within one period implies $r\mid N$: write $N=qr+s$, $0\le s<r$. Periodicity gives $f(s)=f(N)=f(0)$, and injectivity forces $s=0$. Put $L=N/r$.

Start with two available computational basis states $|0⟩|0⟩$. Apply $F_N$ to the first register and query the modular-addition quantum oracle:Measure the second register. For some $t\in \{0,\dots ,r-1\}$, the first register becomes the normalized coset stateThe quantum Fourier transform of a periodic coset state isIndeed, the inner geometric sum vanishes unless the Fourier label is a multiple of $N/r$. Measuring that label gives $j=sN/r$ for a uniformly random $s$. Compute, by the Euclidean algorithm,Thus exact period recovery from a Fourier sample succeeds whenever $s$ is coprime to $r$, andHere $\phi$ is the Euler totient function. The classical number-theory input is the totient lower bound from the Mertens product: for sufficiently large $m$, $\phi (m)/m\ge c/\log \log m$ for an absolute $c>0$, with the finitely many small cases handled separately. For $r=1$ recovery is certain; for $r=2$ its probability is $1/2$. The useful asymptotic probability statement is a lower bound, hence $\Omega$ notation; it can be much larger for particular periods, for example a prime period.

There is one oracle query, two Fourier transforms and two measurements. The final greatest common divisor and division use polynomial time in $\log N$. This meets the specified primitive-operation model without assuming that an arbitrary-$N$ Fourier gate is free in another gate model. If a constant success probability is wanted, repeat independently $O(\log \log N)$ times and return the least common multiple of the candidates: each candidate divides $r$, and one successful sample makes that least common multiple exactly $r$.

Prepare an additional qubit in $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$ by applying $X$ and then the Hadamard gate to $|0⟩$. Apply $H^{\otimes n}$ to the data register. The Boolean quantum oracle then produces quantum phase kickback:A final Walsh-Hadamard transform gives an amplitude for $z$ equal toTo see this identity, the sum factors over the bits; any position at which $a$ and $z$ differ contributes $1-1=0$. This is Bernstein-Vazirani phase kickback, and its output isThere is exactly one oracle query, $O(n)$ fixed quantum gates, and no probabilistic intermediate step. The ancilla qubit can be left in $|A⟩=|-⟩$ or reset to $|0⟩$ using its known inverse preparation. The construction includes the case $a=0$.

The linear decoding must be done coherently, so its output is available inside the next Boolean quantum oracle call. Use registers $Z,X$ of $n$ qubits and a shared phase ancilla qubit in $|-⟩$. Define the Bernstein-Vazirani decoding controlled by a quantum registerThe ancilla qubit is implicit. For every computational index $x$, the Walsh-Hadamard transform calculation givesIn particular $W_g^2=I$ on these states. Initialize $Z$ to $|0⟩$ and $X$ to $H^{\otimes n}|0⟩$. The three query stages areThe middle equality uses the matching index $z=a_x$, not a classical guess of that string. The second $W_g$ performs uncomputation, removing the hidden-string register without losing its phase on $X$. Apply $H^{\otimes n}$ to $X$ to obtainThis requires precisely two queries to $U_g$ and one to $U_f$, and only $O(n)$ additional fixed quantum gates. No measurement of $a_x$ is made: such a measurement would spoil the required coherence. Preparing all registers and the phase ancilla qubit uses only the initially available zero states.

Assume $|\xi ⟩$ is normalized and the Hilbert space has dimension $d$. The rank-one orthogonal projection $P=|\xi ⟩⟨\xi |$ satisfies $P^{†}=P$ and $P^2=P$.

For $d>1$, $P$ has eigenvalue zero on the orthogonal complement of $|\xi ⟩$, so it cannot be a unitary operator. The complementary orthogonal projection $I-P$ kills $|\xi ⟩$ and is not unitary in any positive dimension. In contrast, the Householder reflectionis Hermitian and obeys $R^{†}R=R^2=I-4P+4P^2=I$. Its eigenvalues are $-1$ along $|\xi ⟩$ and $+1$ on the orthogonal complement.

Let ${\Pi }_G$ be the orthogonal projection onto the good vector subspace $G$, and let the normalized input be $|\psi ⟩$. Set $p=\Vert {\Pi }_G\psi {\Vert }^2={\sin }^2\theta$ with $0<\theta <\pi /2$, and defineAssuming coherent access to the two reflections, the amplitude amplification theorem states thatpreserves the plane spanned by $|g⟩,|b⟩$ and acts as a rotation, givingHence the good-outcome probability is ${\sin }^2((2j+1)\theta )$. When $p$ is known, choose the nearest nonnegative integer to $\pi /(4\theta )-1/2$. The resulting angle is within $\theta$ of $\pi /2$, so the good probability is at least ${\cos }^2\theta =1-p$. For small $p$ this is close to one and requires $O(1/\sqrt{p})$ iterations. Exact success occurs when $(2j+1)\theta =\pi /2$. Known $p$ also allows exact amplitude amplification by ancilla qubit dilution or selective phase adjustment when ordinary integer iterations would overshoot.

If $|\psi ⟩=A|0⟩$ has a known coherent preparation, its reflection is implemented with $A$, $A^{†}$ and a zero-state phase flip. A coherent membership test supplies the reflection about $G$. Merely possessing an unknown copy of $|\psi ⟩$ does not automatically supply its reflection. For $p=1$ the state is already good; for $p=0$ this two-reflection construction cannot generate a good component. These cases delimit the theorem's algorithmic assumptions.

Prepare the two data qubits in $|s⟩=\frac{1}{2}{\sum }_{x\in B_2}|x⟩$ and a phase ancilla qubit in $|-⟩$. A single Boolean quantum oracle query flips only the marked amplitude. Its success fraction is $p=1/4$, so $\theta =\pi /6$ in amplitude amplification. The fixed diffusion reflection $D=2|s⟩⟨s|-I$ gives $\sin (3\theta )=1$ after one iteration.

Directly, after the query the marked amplitude is $-1/2$ and the other three are $1/2$. Their mean is $1/4$. The diffusion reflection replaces each amplitude $c_x$ by $2(1/4)-c_x$, yielding one at the marked input and zero elsewhere. ThusHere $U_f$ is understood with its target ancilla qubit, and $D$ acts only on the data. It is independent of $f$: $D=H^{\otimes 2}(2|00⟩⟨00|-I)H^{\otimes 2}$, with the central diagonal gate implementable using two Pauli Z gates and one Controlled-Z gate. Measuring the data in the computational basis therefore finds the unique marked string with certainty after one oracle query.

Write $Q=2^n$, $t=(p-1)(q-1)$ and $a=t/Q$. The easy starting state is uniform over all $n$-bit labels, so its good fraction is $a$, not $t/N$. For distinct primes one has $a\ge 1/4$. If both primes are odd, $t/N\ge (1-1/3)(1-1/5)=8/15$ and $N/Q\ge 1/2$, giving $a\ge 4/15$. If one prime is two, the other is an odd prime $q$; since $2q$ has $n$ bits, $q>2^{n-2}$, and $t=q-1\ge 2^{n-2}=Q/4$.

The uniform coprime state for a semiprime can now be prepared by one exact Grover rotation. SetPrepareUse the good subspace spanned by $|k⟩|1⟩$ with $1\le k<N$ and $\gcd (k,N)=1$. Its squared overlap with $|\Psi ⟩$ is exactly $a\lambda =1/4$. The Euclidean algorithm supplies a reversible computation of the membership predicate, including the range check; condition a sign flip on membership and the extra qubit being one, then uncompute the workspace. This implements $S_G=I-2{\Pi }_G$.

The starting-state reflection $D_{\Psi }=2|\Psi ⟩⟨\Psi |-I$ uses the inverse of its known preparation and a reflection on the all-zero state. Applying $D_{\Psi }{S}_G$ once invokes exact amplitude amplification at $\theta =\pi /6$, and givesThe extra qubit factors off, and the arithmetic workspace is returned to zero. Although the stated range includes $N$, that label is not coprime to itself, so the predicate $k<N$ is equivalent and avoids admitting labels outside the intended range.

The supplied $p,q$ determine $t$ in polynomial time; no factoring procedure is needed. Binary arithmetic, range comparison, the reversible greatest common divisor, the two starting-state reflections and the controlled sign flip all have polynomial-size circuits. Thus the construction takes polynomial time in $n$ in the ideal model allowing the specified one-qubit state preparation. Exactness uses the rotation with known amplitudes $\sqrt{\lambda },\sqrt{1-\lambda }$; with a fixed finite approximate gate library one obtains arbitrary accuracy with precision overhead, rather than an automatic promise of exact state preparation. In the ideal model the preparation succeeds with certainty, without rejection sampling. If desired, the extra $|1⟩$ can be reset by a Pauli X gate.

Let $L=2^n$ and use an $n$-qubit phase register. Begin with $|0^n⟩|v⟩$ and apply $H^{\otimes n}$ to the phase register, creating $L^{-1/2}{\sum }_{m=0}^{L-1}|m⟩|v⟩$. Controlled powers implementFor phase qubit $j$, counted from the most significant bit, the controlled power is $U^{2^{n-j}}$. It can be built from $2^{n-j}$ calls to the supplied controlled-$U$ gate. By quantum phase kickback, the phase-register state isApply the inverse quantum Fourier transform to obtain the exact quantum phase estimation mappingA computational basis measurement of the first register determines $y$ with certainty, hence $\varphi =y/L$ and the eigenvalue $e^{2\pi i\varphi }$. Exactness follows from the promised dyadic phase; no approximation or continued-fraction reconstruction is needed.

With only controlled-$U$ available as a query, the repeated-power construction uses $L-1=2^n-1$ oracle calls. The other Fourier-transform circuitry has polynomial size in $n$ in the ideal phase-gate model. The cost of exact phase estimation on a dyadic spectrum is therefore not polynomial in $n$ in this primitive-query model unless powered queries have additional implementations. The task does not require such a polynomial bound.

Since $U$ is a unitary operator, its eigenstates form an orthonormal basis. Expand $|\xi ⟩={\sum }_j{c}_j|v_j⟩$, with eigenphases ${\varphi }_j=y_j/2^n$. By linearity, the unmeasured quantum phase estimation output isThis is generally an entangled state, not a phase label attached to an unchanged pure system state. The distinct eigenvalues give distinct phase labels, so a computational basis measurement yields $y_j$ with Born rule probability $|c_j{|}^2$ and leaves $|v_j⟩$ in the system register. Before measurement, all relative phases remain coherent; that is essential for the following spectral transformation. If phases were degenerate, a measured label would instead select the corresponding eigenspace component.

The binary phase is $\varphi =0.i_1\cdots i_n={\sum }_{j=1}^n{i}_j{2}^{-j}$. ThereforeOn the phase register, apply the tensor product of phase gatesIts action on $|y⟩=|i_1\cdots i_n⟩$ is multiplication by $e^{2\pi i\varphi /M}$. Thus the positive-phase fractional power of a unitary operator is implemented by uncomputation after coherent phase estimation:HenceThe inverse phase-estimation circuit uses controlled powers of $U^{-1}$ built from the supplied inverse oracle, with all other quantum gates reversed. No phase-register measurement is made, so arbitrary superpositions are preserved and the ancilla qubits return to zero. The straightforward implementation uses $2(2^n-1)$ controlled-unitary queries plus the Fourier and phase circuitry; the arbitrary phase gates are accepted exactly as stipulated.

The branch convention matters. This construction uses the phase representative $0<\varphi <1$ specified here, corresponding to argument in $(0,2\pi )$. It implements that explicitly defined root, even for $\varphi >1/2$. The usual complex principal branch with argument in $(-\pi ,\pi ]$ would choose a different root on some eigenvalues. No substitution of that alternative branch is implicit.

The J gate is $J(\alpha )=HP(\alpha )$, with $P(\alpha )=\mathrm{diag}(1,e^{i\alpha })$. Prepare a fresh qubit in $|+⟩$ and apply the Controlled-Z gate $E$ between it and the input $|\psi ⟩=u|0⟩+v|1⟩$. The resulting state isMeasure the input in the equatorial qubit measurement basis $|{\alpha }_s⟩=(|0⟩+(-1{)}^s{e}^{-i\alpha }|1⟩)/\sqrt{2}$. The unnormalized output isEach outcome has probability $1/2$. Thus one-bit teleportation realizeson the new qubit. Apply the known Pauli X gate correction $X^s$ for the literal $J(\alpha )$ output, or keep the correction in a Pauli frame and adapt later measurements. The old qubit is measured, so this is not cloning the input.

Direct multiplication of the given matrices gives $J(\alpha )X^s=e^{+is\alpha }{Z}^{s}J((-1{)}^s\alpha )$. The displayed negative exponent in the supplied relation has the wrong sign for exact matrix equality. The discrepancy is only a global phase in a fixed measurement branch, so it does not change this measurement implementation or its outcome probabilities. The positive-sign identity is used when tracking exact matrices.

An explicit measurement-based quantum computation pattern uses six vertices $u_0,u_1,u_2,v_0,v_1,v_2$. Prepare a graph state with every vertex in $|+⟩$ and apply a Controlled-Z gate for each edgeThe first two links on each wire permit graph-state preparation of a computational-basis input followed by the logical J gate. Use the following single-qubit measurements:

All entangling edges can be made at preparation time because Controlled-Z gates commute. A future edge that does not touch a currently measured vertex can equivalently be deferred, which allows the one-bit teleportation identities to be applied in their logical order.

The two initial $X$ measurements implement $H|+⟩=|0⟩$ with Pauli frames $X^{s_0},X^{t_0}$ on the logical inputs. The first adaptive J gate then has output frame $X^{s_1}{Z}^{s_0}$ on $u_2$. Propagating through $E_{u_2{v}_1}$ gives framesup to branchwise global phase. The second adaptive J gate converts the latter intoA $Z$ correction does not alter a computational-basis measurement, while an $X$ correction flips its bit. Consequently the deterministic classical postprocessing isThis reproduces the output-bit distribution of the original quantum circuit, including its known byproduct corrections.

There is an additional simplification for these particular zero inputs. Since $J(\alpha )|0⟩=|+⟩$, $E(|+⟩|0⟩)=|+⟩|0⟩$, and $J(\beta )|0⟩=|+⟩$, the exact final state is $|+⟩|+⟩$, independently of the angles. The requested bit is therefore fair. A single isolated graph-state vertex measured in $Z$ already simulates that bit distribution; the six-vertex pattern also explicitly realizes the circuit and its corrections.

Use the operator norm induced by the usual vector norm, and assume the input quantum state is normalized. Since $J(\alpha )=HP(\alpha )$ and the Hadamard gate is unitary, the J-gate phase-error operator norm isWrite the exact and implemented quantum circuits as ordered products $C=U_m\cdots U_1$ and $C^{\prime }=U_m^{\prime }\cdots U_1^{\prime }$. The quantum circuit gate-error telescoping bound follows fromEvery surrounding factor is unitary, including gates tensored with identities on other qubits, so the triangle inequality and the submultiplicativity of the operator norm giveThe exact Controlled-Z gates contribute zero to that sum. ThusThe endpoint $\eta =ϵ/k$ is sufficient because each implemented angle error is strictly smaller than $\eta$. If $k=0$, the circuits are identical and any positive $\eta$ works. The bound controls the stated vector distance with actual gate phases retained, so no adjustment of the global phase of one output is needed.