Past exam of the mathematics course of the University of Cambridge / 2012 / iii / Paper 67 (Quantum Computation)

Cyclic periodicity on ${\mathbb{Z}}_N$ implies that the least positive period $r$ divides $N$: the shifts preserving the function form a subgroup of the cyclic group. Injectivity within one period says that distinct residue classes modulo $r$ have distinct function values. Write $L=N/r$.

Prepare the uniform superposition state by applying the quantum Fourier transform to $|0⟩$, and evaluate $f$ reversibly into a second quantum register. This is efficient because the given classical Boolean circuit can be converted into a reversible circuit, with its workspace cleaned by uncomputation. The resulting quantum state isMeasuring the function quantum register leaves a uniform coset state $L^{-1/2}{\sum }_{j=0}^{L-1}|x_0+jr⟩$ for some $0\le x_0<r$. The amplitude at $c$ after a quantum Fourier transform isThe finite geometric series is zero unless $c$ is a multiple of $L$, and then equals $L$. Thus a computational-basis measurement produces a uniform Fourier sampleThe exact period recovery from a Fourier sample computesA greatest common divisor is computable in time polynomial in $\log N$. The candidate is always a divisor of the true period, and equals it precisely when $s$ is coprime to $r$.

For the success flag, compute $f(\hat{r}\mathrm{mod}N)$ and compare with $f(0)$. If $\hat{r}<r$, injectivity within the first period makes these unequal. If $\hat{r}=r$, periodicity makes them equal, including $r=N$. Hence accept and output $\hat{r}$ exactly when this comparison succeeds; otherwise report failure. This is heralded exact quantum period finding when the period divides the register size, with no false acceptance. The case $r=1$ succeeds even on the sample $c=0$.

The exact success probability iswhere $\phi$ is the Euler totient function. For $r\mid N$, the prime-product formula gives $\phi (r)/r\ge \phi (N)/N$. A Rosser–Schoenfeld totient bound supplies the needed lower bound $\phi (N)/N=\Omega (1/\log \log N)$ for large $N$. Every single attempt, including verification, has the assumed polynomial-in-$\log N$ gate cost. Repeating $O(\log \log N)$ times gives constant success probability with a certified result whenever one is found.

The printed $O$ in the totient hint should be a lower-bound statement, $\Omega$. Literally, $\phi (N)=O(N/\log \log N)$ is false: at primes $N$, $\phi (N)=N-1$. Likewise the exact single-sample success probability need not be $O(1/\log \log N)$; for prime period it tends to one. The useful intended guarantee is the displayed inverse-log-log lower bound, not a universal upper bound. If an algorithm satisfying the literal success upper bound is desired, one can additionally accept an otherwise certified run only when $k=\lceil \log \log N\rceil$ independent fair bits are all zero. This retains a detectable failure flag and polynomial runtime, and has success at most $2^{-k}=O(1/\log \log N)$, but deliberately weakens the useful guarantee. The standard unsuppressed algorithm above gives the stronger intended performance. Small $N$ can be handled directly. Primary evidence for the totient lower bound is Theorem 15, equations (3.41)–(3.42), in denisevellachemla.eu/Rosser-Schoenfeld-1962.pdf .

Let $\omega =e^{2\pi i/3}$. The positive-exponent quantum Fourier transform gives $|\xi ⟩=3^{-1/2}{\sum }_{y=0}^2{\omega }^{2y}|y⟩$. Reindexing the cyclic shift operator givesThus $|\xi ⟩$ is an eigenstate with eigenvalue $\omega$, with this sign fixed by the printed quantum Fourier transform convention.

Prepare the first two qutrits in $({\mathrm{QFT}}_3|0⟩{)}^{\otimes 2}$ and the answer qutrit in $|\xi ⟩$. The modular-addition quantum oracle applies $S^{f(x_1,x_2)}$ to the answer. Its eigenvalue produces quantum phase kickback, leavingApply ${\mathrm{QFT}}_3^{-1}$ to each input qutrit, then measure them in the computational basis. The result isThe preparation, inverse transforms and measurements are independent of $f$, and there is exactly one use of $U_f$. This is qutrit linear-function identification, the ternary version of Bernstein-Vazirani phase kickback.

Use the bit-query Boolean quantum oracle $O_x|i,b,z⟩=|i,b\oplus x_i,z⟩$, where $z$ denotes workspace. Initially every probability amplitude is independent of $x$, hence is a constant polynomial. An input-independent unitary gate only forms linear combinations of probability amplitudes, so it does not increase their polynomial degree.

If $a_{i,b,z}(x)$ is an amplitude before a query, its new value isOne query increases polynomial degree by at most one. Inductively, after $T$ queries each amplitude has polynomial degree at most $T$. The acceptance probability is a sum of squared absolute values of the accepting amplitudes, so it is a real polynomial of degree at most $2T$. Intermediate quantum measurements and classical adaptation can be retained coherently, or handled by summing unnormalized branch probabilities; either approach yields the same degree bound.

An exact algorithm has acceptance probability precisely $f(x)$ at every Boolean input. The multilinear reduction on the Boolean cube replaces positive powers of each $x_i$ by $x_i$, preserving these values without increasing polynomial degree. Therefore the polynomial method for quantum query lower bounds givesHere $\mathrm{deg}(f)$ is the degree of the unique multilinear polynomial representing the Boolean function, and $Q_E$ is its exact quantum query complexity. Uniqueness follows, for example, by evaluating successively on the indicator vectors of subsets: the value on a subset determines its coefficient once all smaller-subset coefficients are known.

For the three-bit majority function, the pair products count how many pairs of input bits are both one. Their sum is zero at Hamming weights zero and one, one at weight two, and three at weight three. Subtracting twice the triple product corrects the last value. HenceThis is a multilinear polynomial of degree three, and its top coefficient is nonzero. Uniqueness of the Boolean multilinear polynomial excludes a degree-two alternative. The polynomial method for quantum query lower bounds therefore yields $T\ge 3/2$, and the integer number of queries gives

First use the allowed one-query algorithm to learn $p=x_1\oplus x_2$ exactly. This restricted two-index Boolean quantum oracle is realized by relabelling indices $1,2$ in a single query to the original input. Measure its output and choose the second query classically.

If $p=0$, the first two bits agree and their common value is the majority, irrespective of $x_3$. Query $x_1$ and output it. If $p=1$, the first two bits cancel in the vote, so query $x_3$ and output it. ThusThe exact two-query majority algorithm uses one parity query and one ordinary bit query on every branch, and is correct on all eight inputs. Together with the lower bound this proves $Q_E(\mathrm{MAJ})=2$.

Boolean conjunction is multiplication on zero-one inputs. The block conjunction of three-bit majorities therefore has the multilinear polynomialThe factors use disjoint variables, so their product remains a multilinear polynomial. Its monomial containing all $3n$ variables has coefficient $(-2{)}^n\ne 0$; no term has higher degree. By uniqueness, the representing multilinear polynomial has degree exactly $3n$. Applying the polynomial method for quantum query lower bounds givesThis argument concerns exact quantum query complexity; the analogous claim for bounded error does not follow from exact polynomial degree.

For a Boolean function $f$, its block sensitivity at $x$ is the maximum number of pairwise disjoint nonempty index sets $B_j$ such that flipping all bits in each $B_j$ individually changes $f(x)$. Maximize over $x$ to obtain $\mathrm{bs}(f)$.

Choose $x=(110)(110)\cdots (110)$, so every three-bit block has majority one and the conjunction is one. In each block, flipping either of its two one bits alone changes that block's majority to zero and therefore changes the conjunction to zero. These $2n$ singleton index sets are all disjoint, soThe supplied bounded-error quantum query complexity lower bound now givesHere $Q_2$ denotes a fixed two-sided error bound below $1/2$, such as $1/3$.

In fact the block sensitivity is exactly $2n$. At a one-input, selecting two one bits from each triple gives a size-$2n$ certificate: any block flip changing the output must touch it, so disjoint sensitive sets number at most $2n$. At a zero-input, one failing triple contains at least two zero bits; fixing those two zeros certifies zero, so at most two disjoint sensitive sets can change the output. The lower-bound witness above attains $2n$. The certificate complexity of a Boolean function supplies these upper bounds, though only the witness is needed for the requested result.

Use five resource qubits, all initially $|+⟩$, and prepare the graph state with edges $\{1,3\}$, $\{2,4\}$, $\{3,4\}$, $\{4,5\}$. The labels here identify resource vertices; logical wire 1 travels from vertex 1 to 3, and logical wire 2 travels from 2 to 4 to 5. Each edge is a Controlled-Z gate, and these entangling gates commute, so all can be applied when preparing the resource.

Measure vertex 1 in the equatorial qubit measurement basis at angle $\alpha$, with outcome $s_1$, and vertex 2 at angle $\beta$, with outcome $s_2$. These measurements can be simultaneous. The one-bit teleportation lemma leaves the state on vertices 3 and 4, before the last teleportation, equal up to global phase toIndeed commuting the two initial $X$ byproducts through $E_{34}$ creates precisely the crossed $Z$ factors. The unused edge from 4 to the fresh vertex 5 is the last one-bit teleportation link.

Measure vertex 4 at angle $\theta =(-1{)}^{s_2}\gamma$, with outcome $s_4$. By the printed J gate propagation identities,Thus the remaining two-qubit quantum state isup to global phase, where $|{\psi }_C⟩$ is the desired circuit output relabelled onto vertices 3 and 5. The sign choice cancels the unwanted angle reversal caused by the $X$ frame on vertex 4.

Finally measure vertices 3 and 5 in the computational basis, obtaining raw results $t_3,t_5$. The Pauli Z gate affects only phases, while the Pauli X gate flips a computational result. The five-vertex graph-state circuit simulation therefore outputsThis deterministic classical correction reproduces the ideal joint probability distribution for every preceding measurement branch. The final fixed-basis measurements may share the second layer with the adaptive measurement of vertex 4, because their projectors act on different vertices; measuring them afterwards is also valid.

Replace every CNOT gate by $H_j{E}_{ij}{H}_j$. The resulting quantum circuit contains only Hadamard gates and Controlled-Z gates. Realize each Hadamard gate by a fresh one-bit teleportation link measured at angle zero, so every internal measurement is in the fixed $X$ basis. Insert a graph edge between the current wire vertices for each Controlled-Z gate. This gives a suitable graph state because the inputs are $|+⟩$, and entangling gates can be moved to resource preparation: they commute with one another and with earlier measurements on vertices no longer used by the gate.

Track a Pauli frame ${⨂}_i{X}_i^{p_i}{Z}_i^{q_i}$. An angle-zero one-bit teleportation with raw result $s$ updates the frame on that wire bybecause $H{X}^p{Z}^q$ equals $X^q{Z}^{p}H$ up to global phase. A Controlled-Z gate updates $q_i\leftarrow q_i\oplus p_j$ and $q_j\leftarrow q_j\oplus p_i$, leaving the $p$ bits unchanged. These are classical binary updates; no measurement angle depends on them.

All the internal quantum measurements consequently have predetermined bases. Their projectors act on distinct resource vertices and commute, so all internal measurements can be performed simultaneously: the logical measurement depth is at most one. If the output is to be read in the computational basis, those fixed-basis measurements can occur in the same layer; a raw output $t_i$ is relabelled $t_i\oplus p_i$. If quantum outputs are retained, the same calculation gives the desired output in a known Pauli frame. This nonadaptive Hadamard–CNOT measurement pattern concerns measurement depth, not the depth of resource preparation or classical frame computation.

Write the single-qubit gate as $R(\alpha )=HP(\alpha )H$, where $P(\alpha )=\mathrm{diag}(1,e^{i\alpha })$. Thus it is, up to global phase, a rotation about the x-axis, and it commutes with $X$. Compile it as a Hadamard gate followed by the J gate $J(\alpha )$. Compile each CNOT gate as before into $H_j{E}_{ij}{H}_j$. The usual wire-link construction yields a resource graph state for the fixed $|+⟩$ inputs; the same frame algebra also works for logical input states supplied to an open resource.

The point is stronger than counting two gates per rotation: a long circuit must not acquire a new adaptive layer for every rotation. We show that every nonzero-angle basis depends only on outcomes of the angle-zero measurements.

For an $R(\alpha )$ gadget, let the incoming Pauli frame be $X^p{Z}^q$. Denote the angle-zero outcome by $s$, and the subsequent angle-$\theta$ outcome by $t$. The two one-bit teleportations givewhere $\simeq$ omits a global phase. Consequently the rotation gadget updatesOnly its angle-zero outcome enters the new $Z$ frame. Its arbitrary-angle outcome enters only the $X$ frame, which commutes through all later $R$ gates.

For a CNOT gate from $i$ to $j$, call the outcomes of its two angle-zero target-wire measurements $r,u$, in that order. The Pauli frame update isThese follow by applying the preceding Hadamard gate and Controlled-Z gate frame updates twice. In particular, the new $Z$ frames depend on old $Z$ frames and angle-zero outcomes only; they never depend on old $X$ frames or arbitrary-angle outcomes. This is the measurement-level version of the given fact that a CNOT gate propagates $X$ operators into products of $X$ operators.

Starting with no frame, induction in the original circuit order now computes every $q$ solely from angle-zero results. Therefore every sign $(-1{)}^{s\oplus q}$ is known after one simultaneous layer containing all angle-zero measurements, including those appearing late in the circuit. Compute those signs classically, and perform all remaining equatorial measurements in a second simultaneous layer. An angle zero that occurs accidentally among these remaining choices may stay in that layer. Reordering is valid because, once a branch's bases have been fixed, the projectors on different vertices commute; no second-layer result is needed to choose another second-layer basis.

The two-layer measurement pattern for CNOT and x-axis rotations thus hasindependently of the number or order of gates. Fixed computational-basis measurements of classical outputs can be included in layer two, followed by relabelling $t_i\mapsto t_i\oplus p_i$. For quantum outputs the final Pauli frame gives the required correction. The depth statement excludes graph preparation and classical processing, as in the definition in the paper.

Put $M=2^m$ and prepare $m$ control qubits in $|0{⟩}^{\otimes m}$ and the target in the supplied eigenstate $|\psi ⟩$. Apply a Hadamard gate to every control qubit. Let $k={\sum }_{j=0}^{m-1}{2}^j{k}_j$ denote the integer encoded in that quantum register.

For every $j$, apply a controlled unitary gate $U^{2^j}$ with control $k_j$ and the same target. The quantum phase kickback yieldsApplying ${\mathrm{QFT}}_M^{-1}$ to the controls therefore produces $|x⟩$ exactly. A computational-basis measurement returns $x$ with certainty, and the algorithm outputsThis is exact quantum phase estimation; exactness uses the finite dyadic phase promise, not a rounding argument.

Only a controlled-U gate is supplied as a primitive. Its $2^j$ repetitions implement controlled-$U^{2^j}$, so the total number of black-box uses is ${\sum }_{j=0}^{m-1}{2}^j=2^m-1$. Access to powers as unit-cost primitives would be a different quantum query complexity model. This distinction is the cost of exact phase estimation on a dyadic spectrum.

The quantum circuit has one control wire per binary digit and one target quantum register. Every control starts in $|0⟩$, receives a Hadamard gate, controls the corresponding power $U^{2^j}$, and then enters the collective inverse quantum Fourier transform. Only the control register is measured; the target stays in $|\psi ⟩$.

The omitted intermediate wires continue the pattern $j=0,1,\dots ,m-1$. The inverse quantum Fourier transform black box is defined on the integer basis $|k⟩$ with $k={\sum }_j{2}^j{k}_j$, so the displayed ordering introduces no hidden bit reversal. The measured bits satisfyEach controlled power box represents $2^j$ sequential controlled-$U$ uses when only that primitive is available.

Let $\lambda =e^{2\pi i\varphi }$. In terms of the Pauli X gate, the given unitary operator is $U_{\varphi }=aI+bX$, with $a=(1+\lambda )/2$ and $b=(1-\lambda )/2$. Since $X|+⟩=|+⟩$ and $X|-⟩=-|-⟩$,Thus the normalized eigenvectors are $|\pm ⟩=(|0⟩\pm |1⟩)/\sqrt{2}$, with eigenvalues $1$ and $e^{2\pi i\varphi }$ respectively. At $\varphi =0$ they coincide as eigenvalues, and the whole two-dimensional Hilbert space is the eigenspace; the same chosen eigenbasis remains valid.

Prepare $|-⟩$ independently of $\varphi$ and use the exact quantum phase estimation circuit of the preceding parts on the controlled-$U_{\varphi }$ black box. It returns $\varphi$ exactly usingThe chosen eigenstate contains all the unknown phase information, unlike $|+⟩$, whose eigenvalue is independent of $\varphi$.

Again put $a=(1+\lambda )/2$, $b=(1-\lambda )/2$. If computational strings $z,y$ differ in $h$ places, the matrix element of $U_{\varphi }^{\otimes n}$ between them is $a^{n-h}{b}^h$: an unchanged bit contributes $a$, and a flipped bit contributes $b$. Hence the given operator isThe printed factored expression $a^n(b/a{)}^h$ is undefined at $a=0$, namely $\varphi =1/2$. Its polynomial form $a^{n-h}{b}^h$ gives the natural continuous extension there, $U_{1/2}^{(n)}=X^{\otimes n}$. For $n\ge 2$ the strict promise $\varphi <1/n$ avoids that singular value; for $n=1$ the extension is needed to include the allowed phase $1/2$. This is a removable defect of the formula, not a failure of unitarity of the tensor-product operator.

Prepare $|-{⟩}^{\otimes n}$. Its eigenvalue is ${\lambda }^n=e^{2\pi in\varphi }$, giving tensor-product eigenphase amplification. Write $n=2^s$. If $s<m$, thenwhere the upper bound is exactly the promise $\varphi <1/n$. Thus the amplified phase has only $m-s$ unknown binary digits and no modulo-one aliasing. Run exact quantum phase estimation with $m-s$ controls on the controlled-$U_{\varphi }^{(n)}$ black box. It returns $x$ exactly, after which division by the original $2^m$ recovers $\varphi$.

The number of joint black-box uses isIf $s\ge m$, the dyadic promise and $\varphi <1/n$ force $x=0$, so output $\varphi =0$ without querying the oracle. This covers the zero-control edge case without an invalid negative number of phase bits. The improvement counts one supplied controlled-$U_{\varphi }^{(n)}$ call as one query. Implementing such a joint call from $n$ individual controlled-$U_{\varphi }$ calls would remove the claimed factor-$n$ primitive-query saving, and preparing the $n$ target qubits is a separate gate cost.