What is the order of the gates making up the QFT on two qubits?

The Quantum Fourier Transform consists of 2 gates. Controlled Phase Gates, and Hadamard gates. I'm assuming the Controlled Phase Gate is a combination of a Control Gate, and a Phase Gate.

But what is the order of operations on the Controlled Phase Gate? CNOT then Phase Change? Or Phase Change then CNOT?

$$U_{CPG}(\phi) |xy\rangle = \exp(i(x\land y)\phi)|xy\rangle$$ Where $\land$ is the logical AND operation. Thus the multiplication by the phase factor $e^{i\phi}$ is only applied if the 2 input qubits are $|xy\rangle = |11\rangle.$ All 3 other possible inputs ($00$, $01$, $10$) remain unaffected. Its matrix form using $|00\rangle,$ $|01\rangle,$ $|10\rangle$ and $|11\rangle$ vectors as an orthonormal basis in $\mathbb{C}^4$ would be: \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & e^{i\phi} \end{pmatrix}
Now in the Quantum Fourier Transform (QFT) setup, single qubit controlled phase gates are used. For example for the first qubit, after the Hadamard, we start by applying the first CPG gate, usually named $R_2=U_{CPG}(2\pi/2^2)$: \begin{pmatrix} 1 & 0 \\ 0 & e^{i2\pi/2^2} \end{pmatrix} Then we continue applying the remaining CPG's, i.e. $R_3,...$ all the way up to $R_k$ (for $k$ qubit quantum computer). Note $R_k$ is given by: \begin{pmatrix} 1 & 0 \\ 0 & e^{i2\pi/2^k} \end{pmatrix} You proceed similarly for the remaining input qubits, until the last qubit for which there's only a Hadamard to apply.
• The QFT can only be implemented only with single-qubit gates if you measure the qubits in the computational basis directly after the QFT (as it is done in Shor's algorithm and other applications). If you want to realize the full QFT, you have to use Controlled-$R_k$ gates instead. See en.wikipedia.org/wiki/… Aug 24, 2015 at 23:13