Past exam of the mathematics course of the University of Cambridge / 2012 / iii / Paper 67 / 4

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.