= Solution
Put $N=2^n$ and label the binary digits of $x$ by $x_{n-1},\ldots,x_0$, with $x=\sum_{j=0}^{n-1}2^jx_j$. The <Walsh-Hadamard transform> prepares the <uniform quantum superposition> $N^{-1/2}\sum_x|x\rangle$. Applying the <phase gate> $R_a^{2^j}$ to the qubit for digit $x_j$ multiplies its basis amplitude by $\exp(2\pi ia2^jx_j/N)$. Taking their product gives
$$
\prod_{j=0}^{n-1}e^{2\pi ia2^jx_j/N}=e^{2\pi iax/N}.
$$
With the most significant qubit written first, this proves
$$
\boxed{\left(R_a^{2^{n-1}}\otimes R_a^{2^{n-2}}\otimes\cdots\otimes R_a\right)H^{\otimes n}|0^n\rangle
=\frac1{\sqrt N}\sum_{x=0}^{N-1}e^{2\pi iax/N}|x\rangle.}
$$
Each 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$.
Back to article page
