Past exam of the mathematics course of the University of Cambridge / 2014 / iii / Paper 61 / 3

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.