= Solution
Put $M=2^m$ and prepare $m$ control <qubits> in $|0\rangle^{\otimes m}$ and the target in the supplied <eigenstate> $|\psi\rangle$. Apply a <Hadamard gate> to every control <qubit>. Let $k=\sum_{j=0}^{m-1}2^jk_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> yields
$$
\frac1{\sqrt M}\sum_{k=0}^{M-1}|k\rangle U^k|\psi\rangle=\frac1{\sqrt M}\sum_{k=0}^{M-1}e^{2\pi ikx/M}|k\rangle\otimes|\psi\rangle=\operatorname{QFT}_M|x\rangle\otimes|\psi\rangle.
$$
Applying $\operatorname{QFT}_M^{-1}$ to the controls therefore produces $|x\rangle$ exactly. A <computational-basis measurement> returns $x$ with certainty, and the algorithm outputs
$$
\boxed{\phi=x/2^m.}
$$
This 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>.
Back to article page
