# 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?

## 1 Answer

You seem to have confused the CNOT gate with the controlled phase gate. There's no CNOT gate involved in the implementation of a C-phase-gate (let's denote it CPG for short), as all we do with it, is multiplying by a phase factor. For example on two qubits it is defined as:

$$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.

• Shouldn't all your gates be 4x4 matrices? -- Also, I wouldn't fully agree that "there is no CNOT gate involved in the implementation of a controlled phase gate", since usually CNOT (or CZ) is used as the entangling gate in a universal gate set, so it can be used to construct a controlled-phase gate with a general phase. Aug 24, 2015 at 22:31
• @NorbertSchuch No, the 2x2 matrices shown here are single qubit c-phase gates, or sometimes called the conditional phase shift gate (when it's for 1 qubit), and for a single qubit gate there's no need for an ancilla qubit, so it stays a 2x2 matrix, maybe I misunderstood your question. QFT can be implemented with only single qubit gates, without the need for entangling gates, and it's because of this property of QFT that I made the earlier comment about CNOT's. Although your point remains valid, because any gate can in principle be implemented using a CNOT+[one arbitrary universal gate]. Aug 24, 2015 at 23:03
• 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
• @NorbertSchuch Indeed, thank you for having pointed it out. Aug 24, 2015 at 23:18
• Say for 3 qubit case QFT we have the order on first qubit as $H$ then $S$ and then $T$ where S and T are different phase gate. Can we interchange this order to say SHT or TSH. I think yes, because it ultimately multiplying two diagonal matrices. Apr 11 at 20:07