= Dyadic phase-gate identification
{title2=$F_N^\dagger N^{-1/2}\sum_xe^{2\pi iax/N}|x\rangle=|a\rangle,\quad N=2^n$}
For the <phase gate> $R_a=\operatorname{diag}(1,e^{2\pi ia/2^n})$, apply powers $R_a^{2^{n-1}},\ldots,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\rangle$. The inverse <quantum Fourier transform> returns $|a\rangle$ 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$.
Back to article page
