= Dyadic quantum Fourier transform circuit
{title2=$\operatorname{QFT}_{2^n}$}
In most-significant-bit-first order, let $x=x_1\cdots x_n$ and $0.x_j\cdots x_n=\sum_{l=j}^n x_l2^{-(l-j+1)}$. On a <computational-basis state>, process wire $j$ with a <Hadamard gate>, then <controlled phase gates> $R_{l-j+1}$ controlled by unprocessed wire $l$ for each $l>j$. Wire $j$ becomes $(|0\rangle+e^{2\pi i0.x_j\cdots x_n}|1\rangle)/\sqrt2$. Reversing the final wire order yields the positive-exponent <quantum Fourier transform>. There are $n$ <Hadamard gates> and $n(n-1)/2$ <controlled phase gates>. Physical reversal costs $\lfloor n/2\rfloor$ <swap operators>, each expressible as three <controlled-NOT gates>, themselves implemented with <Hadamard gates> and a <Controlled-Z gate>. Thus the entire construction uses $O(n^2)$ gates from the specified family.
Back to article page
