Dyadic phase-gate identification ($F_N^{†}{N}^{-1/2}{\sum }_x{e}^{2\pi iax/N}|x⟩=|a⟩,N=2^n$)

For the phase gate $R_a=\mathrm{diag}(1,e^{2\pi ia/2^n})$, apply powers $R_a^{2^{n-1}},\dots ,R_a$ to a uniform quantum superposition on $n$ qubits. Binary positional weights multiply the phases into $e^{2\pi iax/2^n}$ on basis vector $|x⟩$. The inverse quantum Fourier transform returns $|a⟩$ exactly, by orthogonality of roots of unity. Preparing the powers by repeated applications uses $2^n-1$ copies of $R_a$; this does not claim a number of gate calls polynomial in $n$. If $a$ is odd, its powers generate the entire set of dyadic phase gates because $a$ has a modular inverse modulo $2^n$.