Past exam of the mathematics course of the University of Cambridge / 2010 / iii / Paper 49 / 4 / a / Solution

Put $N=2^n$ and label the binary digits of $x$ by $x_{n-1},\dots ,x_0$, with $x={\sum }_{j=0}^{n-1}{2}^j{x}_j$. The Walsh-Hadamard transform prepares the uniform quantum superposition $N^{-1/2}{\sum }_x|x⟩$. Applying the phase gate $R_a^{2^j}$ to the qubit for digit $x_j$ multiplies its basis amplitude by $\exp (2\pi ia{2}^j{x}_j/N)$. Taking their product givesWith the most significant qubit written first, this provesEach power is implemented by repeated uses of the supplied gate. The total is ${\sum }_{j=0}^{n-1}{2}^j=N-1$ uses. This realizes dyadic phase-gate identification without needing an unknown controlled gate or asserting a gate-call cost polynomial in $n$.