Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 58 (Quantum Computation)

The PDF's small superscript is essential: $f(x)=a^x\mathrm{mod}N$. Interpret $r$ as the least positive period, the multiplicative order of $a$ modulo $N$. If one permitted an unspecified nonminimal period, the answer would not be identifiable; for example, $a=1,N=8$ gives the same constant function with period one or period eight. Under the promised periodic modular-exponential interpretation, $a^r\equiv 1(\mathrm{mod}N)$, so $a$ is a unit. ThusIn particular, different residue classes modulo $r$ have different function values, which is necessary for the usual quantum period finding coset argument.

Prepare $N^{-1/2}{\sum }_x|x⟩|1⟩$ by applying the quantum Fourier transform to the first register. Use repeated squaring to precompute $a^{2^j}\mathrm{mod}N$, then multiply the value register by that known number controlled on bit $j$ of $x$. These controlled modular multiplications are reversible because $a$ is a unit; their inverses use the modular inverses of the same constants. This produces $N^{-1/2}{\sum }_x|x⟩|a^x\mathrm{mod}N⟩$ with a polynomial number of the assumed arithmetic operations. Known work registers can be uncomputed.

Measure the value register. Since $r\mid N$, its fiber is exactly one coset, and the first register becomesThe quantum Fourier transform of a periodic coset state is supported uniformly on the $r$ outcomes $c=jN/r$, $0\le j<r$. Indeed the inner geometric series ${\sum }_{\ell =0}^{N/r-1}{e}^{2\pi i\ell rc/N}$ is zero unless $(N/r)\mid c$, and each allowed amplitude has modulus $1/\sqrt{r}$.

Take two independent Fourier samples $c_1,c_2$ and returnThis is two-sample exact period recovery. The Chinese remainder theorem makes divisibility of independent uniform residues independent across the different prime divisors of $r$. For each such prime $\ell$, both $j_1$ and $j_2$ are divisible by $\ell$ with probability ${\ell }^{-2}$. ThereforeThe number-theoretic facts used here are the Chinese remainder theorem, the Euler product for the Riemann zeta function at two, and $\zeta (2)={\pi }^2/6$. The candidate can also be certified by $a^{\hat{r}}\equiv 1(\mathrm{mod}N)$: it divides the least period, so this equality holds exactly when it is the full period. Each preparation, reversible evaluation, QFT, measurement and greatest common divisor calculation has the assumed or standard polynomial time cost in $\log N$. Two runs suffice for the desired constant success probability. Quantum period finding recovers the least period with probability at least $6/{\pi }^2$ in polynomial time.

Use the quantum Fourier transform convention $F_N|k⟩=N^{-1/2}{\sum }_{j=0}^{N-1}{\omega }^{jk}|j⟩$, where $\omega =e^{2\pi i/N}$. Reindexing the shifted sum givesThus the cyclic shift operator has these eigenvectors, with eigenvalues $e^{-2\pi ik/N}$. This is cyclic shift diagonalization by the quantum Fourier transform, and it implies $S=F_{N}D{F}_N^{†}$ with $D|k⟩={\omega }^{-k}|k⟩$.

For $N=4$, the binary encoding is $k=2x+y$, with $x$ the more significant qubit. The required diagonal phase isso $D=P_{-1}\otimes P_{-i}$. The allowed-gate circuit is thereforeIn execution order, apply the inverse QFT, then the two phase gates, then the forward QFT. There is no extra global phase. Reversing the Fourier sign convention would conjugate both phase gate parameters.

A good item must exist, so assume $1\le k<N$; if $k=0$, the requested search is impossible, while $k=N$ makes every output good. Put $p=k/N$ and $\theta =\arcsin \sqrt{p}$. Normalize the good and bad components of the uniform superposition state asThe Boolean phase oracle negates $|g⟩$ and fixes $|b⟩$. The Grover diffusion operator is $-I_{{\psi }_0}=2|{\psi }_0⟩⟨{\psi }_0|-I$. Its implementation is independent of $f$: conjugate the reflection about $|0^n⟩$ by Hadamard gates. One Grover search algorithm iteration isHence, by the Grover rotation angle formula,Choose the nonnegative integer $j$ nearest to $\pi /(4\theta )-1/2$. Its final angle differs from $\pi /2$ by at most $\theta$, so a computational-basis measurement succeeds with probability at least ${\cos }^2\theta =1-p$. The allowed small-density regime includes $p\le 1/3$, giving the requested $2/3$ bound. Each iteration uses one Boolean phase oracle query, and $j=O(1/\sqrt{p})=O(\sqrt{N/k})$.

For $k=N/4$, $\theta =\pi /6$ and one iteration reaches $3\theta =\pi /2$ exactly. Thus one query gives a good outcome with certainty:This is exact Grover search on four entries applied to a marked fraction of one quarter, not only to a four-element register.

The amplitude amplification theorem concerns a known preparation quantum circuit $A$ and a good-subspace projector $\Pi$. Write $A|0⟩=\sin \theta |g⟩+\cos \theta |b⟩$, with ${\sin }^2\theta =p=\Vert \Pi A|0⟩{\Vert }^2$. Let $S_0=I-2|0⟩⟨0|$ and $S_{\chi }=I-2\Pi$. ThenThe reflection operators preserve the two-dimensional good-bad plane and rotate it by $2\theta$, so $O(1/\sqrt{p})$ iterations amplify a small known success probability to a constant close to one. Each iteration uses one good-subspace phase test and one use each of $A,A^{†}$, together with a known reflection. Amplitude amplification provides a quadratic improvement in the number of repetitions of a successful preparation. The query cost of the preparation and its inverse must be included when they themselves use the input oracle. Exact amplitude amplification uses additional known-overlap preparation or phase matching to avoid integer-iteration overshoot.

Under the usual reversible-circuit interpretation, there is a genuine obstruction to uniform probability lowering by a unitary in the printed premise. The universal assertion cannot hold for arbitrary $p$: it fails already at the search density $p=k/N$.

An explicit counterexample uses $N=4$, one good basis state $|0⟩$, $p=1/4$ and $p^{\prime }=1/8$. The six pure statesall have good probability $1/4$. Their equally weighted density operator is $I_4/4$, a maximally mixed state. Every unitary operator $C$ leaves this mixture unchanged, so its average output good probability remains $1/4$. The printed assertion would instead make all six output probabilities $1/8$, a contradiction. More generally, averaging states $\sqrt{k/N}|g⟩+e^{i\alpha }\sqrt{1-k/N}|b⟩$ uniformly over good and bad basis vectors and two opposite phases gives $I_N/N$, proving the same obstruction at the actual search density $p=k/N$.

The intended conditional construction needs only a supplied reversible preparation that lowers the success probability of the particular starting state, not of every state. Here is the complete argument under that weaker resource assumption. Count $C$ and $C^{†}$ as supplied, query-free operations, as required for the claimed input-oracle bound. Let $\theta =\arcsin \sqrt{k/N}$ and chooseIf equality holds, use the original preparation. Otherwise use the stipulated preparation on $|{\psi }_0⟩$ to obtain $|{\psi }_{\ast }⟩=C|{\psi }_0⟩$ with good probability $p_{\ast }$. Its reflection operator is implementable byThe good and bad components may be nonuniform, but amplitude amplification applies to this same two-dimensional decomposition. After $j$ iterations of $-I_{{\psi }_{\ast }}{I}_f$, its good probability isThus the stated exact-query conclusion follows from accessible preparation of one known-overlap state and its inverse. If the supplied preparation uses oracle queries, those costs cannot be omitted.

A physically realizable known-state success dilution for exact amplitude amplification is available in the standard enlarged marking-oracle model. Append a flag in $\sqrt{1-q}|0⟩+\sqrt{q}|1⟩$, where $q=p_{\ast }/p$, and call a joint state good only when $f(x)=1$ and the flag is one. This prepared state's success probability is exactly $pq=p_{\ast }$. Reflect about this known product preparation and mark the joint good subspace; $j$ ordinary iterations then succeed with certainty. A supplied controlled phase oracle gives one marking query per iteration, or a Boolean bit oracle computes $f$, applies the joint phase and uncomputes $f$ in two queries. Measuring the data therefore returns a good $x$ with certainty in $O(\sqrt{N/k})$ queries. This changes the state space and marking test, and does not assert the impossible universal $n$-qubit circuit. Controlled access is an additional resource in a bare phase-oracle model, so it is made explicit rather than silently assumed.

This is the Deutsch-Jozsa test with an arbitrary uniform-state unitary, and does not require $N$ to be a power of two. Choose a known unitary operator $F$ such that $F|0⟩=|s⟩=N^{-1/2}{\sum }_i|i⟩$. Prepare the target qubit in $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$. One Boolean-oracle call gives quantum phase kickback:Apply $F^{†}$ to the index register. The amplitude on $|0⟩$ isIt equals $+1$ or $-1$ for the two constant strings, and equals zero for a balanced string. Consequently a single query decides the promised problem exactly: measure the index register and report constant for outcome zero, balanced for any other outcome. This is the Deutsch-Jozsa algorithm with the available exact state-preparation operation.

Let $|u_i⟩$ denote the specified image of $|i⟩|0⟩$. Its components comprise $N-1$ distinct ordered-pair basis states, each with coefficient $\pm N^{-1/2}$, together with $|0,0⟩$ with coefficient $N^{-1/2}$. Hence $⟨u_i|u_i⟩=1$.

For distinct indices $i<j$, only two output basis states occur in both images. Their common $|0,0⟩$ contributions have product $1/N$, while the $|i,j⟩$ contributions have product $-1/N$. ThusThe specified map is therefore a linear isometry on the $N$-dimensional input subspace. Complete the input vectors $|i,0⟩$ to an orthonormal basis of the $N^2$-dimensional space, and independently complete their images $|u_i⟩$ to another orthonormal basis. Map the first full basis to the second. This is a unitary extension of a finite-dimensional isometry, giving the required $\tilde{U}$. The prescribed columns are orthonormal, so a full unitary extension exists. Its construction depends only on $N$, not on the unknown string, and is permitted by the question's exact-unitary assumption.

Let $w$ be the number of ones. The displayed output state assigns the outcome $(0,0)$ probabilityFor a constant string, $w=0$ or $N$, so this probability is one. For a balanced string, $w=N/2$, so it is zero. Under the promise, $(0,0)$ certifies a constant string, and any other possible outcome certifies a balanced string. A nonzero ordered-pair outcome must have $i<j$ and ${\hat{x}}_i-{\hat{x}}_j\ne 0$, which also certifies $x_i\ne x_j$ without separately reading either bit. This is the fact used by opposite-pair elimination for exact quantum balance testing.

Maintain a known list of the still-active indices, initially all $N=2K$ positions. On a list of even size $M$, perform the three-step construction with $M$ replacing $N$. A known reversible relabeling prepares and queries the corresponding original indices, so quantum phase kickback still needs only one call to $O_{\mathbf{x}}$. The full unitary extension for that current size is independent of the remaining unknown values. It is allowed even when $M$ is not a power of two.

If the measurement gives $(0,0)$, its amplitude is the imbalance divided by $M$. A balanced active string has zero such amplitude, so an observed zero pair certifies that the active string is unbalanced. Return unbalanced immediately. No probability-of-error estimate is needed: an impossible outcome never occurs in the balanced case.

Otherwise the measured pair corresponds to two opposite bits. Delete those two indices and repeat. Each deletion removes exactly one zero and one one, preserving the difference between their counts. Thus the active string is balanced if and only if the original one is balanced. If all indices are removed, return balanced. This is opposite-pair elimination for exact quantum balance testing; it never requires determining which member of a deleted pair is zero.

Each query either terminates with a valid imbalance certificate or reduces the active length by two. After at most $K$ opposite-pair outcomes the active list is empty. The result is certain on every input, with worst-case query countThe same argument includes the $M=2$ last step: equal bits give $(0,0)$ with certainty, while opposite bits give the sole nonzero pair with certainty. There is no additional final query. The measurement probabilities are normalized because $(M-2w{)}^2+4w(M-w)=M^2$.

For $n\ge 2$, the Pauli X gate and Pauli Z gate act on different qubits in $X_0{Z}_1$, so they commute. Their product is a Hermitian matrix and squares to the identity operator. Its eigenvalues have modulus one; equivalently it is a unitary operator. Therefore its spectral norm isThe $n\ge 2$ qualification is necessary because the qubit labelled one does not exist for $n=1$.

The printed upper summation limit introduces $Z_n$ although only qubits $0,\dots ,n-1$ were defined. Literally the final term is undefined. Use the natural open-chain repairThis preserves the stated $n$-qubit system and agrees with the supplied sum-of-squares hint. If a cyclic convention $Z_n=Z_0$ was intended instead, it must be stated; the same argument works for its $n$ terms when $n\ge 2$. For $n=1$, the repaired open chain is empty and the target is the identity.

Here is a product-formula Hamiltonian simulation using exactly the two supplied lemmas. Let $L=n-1$ and choose an integer $r\ge L$. Every $h_i$ is a norm-one Hermitian matrix. One time slice is the product of two-qubit gatesTo compare a partial product with $e^{i(h_1+\cdots +h_j)/r}$, first propagate the previous error through the next unitary gate, which preserves the spectral norm, and then use Lemma A with $A=-(h_1+\cdots +h_{j-1})/r$, $B=-h_j/r$. Both norms are at most $j/r\le 1$. Its new error is at most $c(j/r{)}^2$ for a universal constant $c$. For an explicit choice, $c=4$ follows from the unitary Taylor bounds $\Vert e^{iA}-I-iA\Vert \le \Vert A{\Vert }^2/2$ and $\Vert e^{iA}-I\Vert \le \Vert A\Vert$. Induction and the triangle inequality therefore giveLemma B, the unitary product telescoping bound, now compares the $r$ repeated slices with $(e^{i{H}_{\mathrm{open}}/r}{)}^r=e^{i{H}_{\mathrm{open}}}$:Take, for example, $r=\max (1,L,\lceil 2c{\sum }_{j=2}^L{j}^2/ϵ\rceil )$. If the sum is zero the product is already exact; otherwise its error is at most $ϵ/2<ϵ$. There are $Lr$ two-qubit gates. This explicit lemma-based construction has fourth-degree dependence on $n$ for fixed precision:This is a sufficient polynomial, not an optimality claim. The polynomial-degree statement treats $ϵ$ as fixed; the inverse-precision dependence is displayed separately. No first-order term error is accumulated without the required repeated-slice factor.

For a unitary operator $W$, $W{W}^{†}=I$. Thus for every nonnegative integer $j$,Insert this into the convergent matrix exponential series in the finite-dimensional qubit setting:Consequently unitary conjugation commutes with the exponential:For an unbounded self-adjoint Hamiltonian, the same identity follows from the spectral theorem for normal operators, with the domain transported by $W$; no unbounded power-series manipulation is needed.

Use one target ancilla qubit initially in $|0⟩$. Apply a CNOT gate from each data qubit $x_j$ to that same target, for $j=1,\dots ,n$. Each CNOT gate adds its control bit modulo two without changing the control. After all $n$ gates the target contains the parity bit $f(x)=x_1\oplus \cdots \oplus x_n$. Thus the required circuit is the $n$-gate parity fan-in:This is parity computation by CNOT gates. The circuit also satisfies $W|x⟩|y⟩=|x⟩|y\oplus f(x)⟩$ for either target value, and $W^{-1}=W$ because all these shared-target CNOT gates commute and individually square to the identity. The action on general superpositions follows by linearity.

The product of the data Pauli Z gates has computational-basis eigenvalueUse the parity circuit $W$ from part (ii), apply the target unitary gate $R=e^{itZ}=\mathrm{diag}(e^{it},e^{-it})$, and then uncompute the parity with $W^{†}$. For every basis input,This equals $e^{it{Z}^{\otimes n}}$ on the data, with the ancilla qubit returned to zero. The compute-phase-uncompute construction therefore gives an exact linear-size circuit:This is a Pauli-string phase by parity computation, an instance of simulation of a computable diagonal Hamiltonian. Part (i) also explains it by $W^{†}(I\otimes Z)W=Z^{\otimes n}\otimes Z$, whose exponential restricts correctly to the target-$|0⟩$ subspace. If no extra line is desired, accumulate parity into the last data qubit, apply $e^{itZ}$ there, and undo the $n-1$ CNOT gates, for $2n-1$ gates. Both constructions implement the global phase as well as the relative phases exactly.