= Solution
Let $L=2^n$ and use an $n$-qubit phase register. Begin with $|0^n\rangle|v\rangle$ and apply $H^{\otimes n}$ to the phase register, creating $L^{-1/2}\sum_{m=0}^{L-1}|m\rangle|v\rangle$. Controlled powers implement
$$
|m\rangle|v\rangle\longmapsto|m\rangle U^m|v\rangle
=e^{2\pi im\phi}|m\rangle|v\rangle.
$$
For 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 is
$$
\frac1{\sqrt L}\sum_m e^{2\pi imy/L}|m\rangle=F_L|y\rangle.
$$
Apply the inverse <quantum Fourier transform> to obtain the <exact quantum phase estimation> mapping
$$
\boxed{V:\ |0^n\rangle|v\rangle\longmapsto|y\rangle|v\rangle}.
$$
A <computational basis> measurement of the first register determines $y$ with certainty, hence $\phi=y/L$ and the <eigenvalue> $e^{2\pi i\phi}$. 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.
Back to article page
