= Solution
Use <exact quantum phase estimation> with $n$ control <qubits> initially $|0^n\rangle$ and one target <quantum register> prepared in the given <eigenvector> $|\psi\rangle$. Apply <Hadamard gates> to the control <qubits>. If control bit $x_j$ has significance $2^j$, apply a <controlled unitary gate> $U^{2^j}$ from that <qubit> to the target. The target stays in $|\psi\rangle$, while <quantum phase kickback> produces
$$
\frac1{\sqrt{2^n}}\sum_{x=0}^{2^n-1}e^{2\pi ix\phi}|x\rangle|\psi\rangle.
$$
Since $\phi=c/2^n$, this is $F_{2^n}|c\rangle\otimes|\psi\rangle$. The inverse <quantum Fourier transform> on the control <quantum register> therefore gives $|c\rangle|\psi\rangle$. The <quantum measurement in the computational basis> returns $c$ with certainty, so
$$
\boxed{\phi=\frac c{2^n}\quad\text{with success probability }1.}
$$
The <quantum circuit> below reads left to right. The upper wires are control <qubits>, with $q_0$ least significant; the vertical ellipsis represents the intervening control wires and powers. The inverse <quantum Fourier transform> acts on the entire control <quantum register>, including any bit-order permutations.
\Image[/past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2017/iii/paper-324-phase-estimation.png]
{title=Quantum phase estimation and spectral filtering}
A supplied controlled-$U$ can implement controlled-$U^{2^j}$ by $2^j$ repetitions with the same control. Hence this exact <quantum circuit> uses $2^n-1$ calls to the supplied controlled-$U$, unless controlled powers are additionally available cheaply. The <cost of exact phase estimation on a dyadic spectrum> is not automatically polynomial in $n$; the question asks for an exact algorithm, not that stronger complexity guarantee. Exactness also uses the promised dyadic <eigenphase>, ideal gates, and the supplied inverse <quantum Fourier transform>.
Back to article page
