The Exercise

The quantum Fourier transform $F$ on two qubits is the operator on $\mathbb{C}^4$ whose matrix in the computational basis $|0\rangle, |1\rangle, |2\rangle, |3\rangle$ is $$F = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{pmatrix},$$(1)^✦ so that its entry in row $j$ and column $k$, both counted from $0$, is $i^{jk}/2$. The exercise asks for $F$ as a product of two-level unitaries. The library answers with five factors.

Two-level Unitaries

A two-level unitary on $\mathbb{C}^d$ is a unitary matrix $U$ for which there are two basis indices $p$ and $q$, not necessarily distinct, such that $$U_{ij} = \delta_{ij} \quad \text{whenever } i \notin \{p, q\} \text{ or } j \notin \{p, q\}.$$(2)^✦

The Five Factors

Write $H_{pq}$ for the matrix on $\mathbb{C}^4$ that acts on $|p\rangle$ and $|q\rangle$ by the Hadamard matrix and fixes the other two basis states. Three of the factors are of this kind: $$H_{01} = \begin{pmatrix} \tfrac{1}{\sqrt{2}} & \tfrac{1}{\sqrt{2}} & 0 & 0 \\ \tfrac{1}{\sqrt{2}} & -\tfrac{1}{\sqrt{2}} & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix},$$(3) $$H_{23} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & \tfrac{1}{\sqrt{2}} & \tfrac{1}{\sqrt{2}} \\ 0 & 0 & \tfrac{1}{\sqrt{2}} & -\tfrac{1}{\sqrt{2}} \end{pmatrix},$$(4) and $$H_{02} = \begin{pmatrix} \tfrac{1}{\sqrt{2}} & 0 & \tfrac{1}{\sqrt{2}} & 0 \\ 0 & 1 & 0 & 0 \\ \tfrac{1}{\sqrt{2}} & 0 & -\tfrac{1}{\sqrt{2}} & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}.$$(5)

The factor $G_{13}$ is the matrix on $\mathbb{C}^4$ that acts on $|1\rangle$ and $|3\rangle$ by the Hadamard matrix with its second column multiplied by $i$, and fixes $|0\rangle$ and $|2\rangle$: $$G_{13} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & \tfrac{1}{\sqrt{2}} & 0 & \tfrac{i}{\sqrt{2}} \\ 0 & 0 & 1 & 0 \\ 0 & \tfrac{1}{\sqrt{2}} & 0 & -\tfrac{i}{\sqrt{2}} \end{pmatrix}.$$(6)^✦

The last factor, $P_{12}$, is the permutation matrix that exchanges $|1\rangle$ and $|2\rangle$: $$P_{12} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}.$$(7)^✦

The Claim

What Is Checked

The claim is stated over the Fourier matrix (1) and the five factors (3) to (7), all $4\times4$ complex matrices given entry by entry, and over the two-level unitaries of (2). The library shows that each of the five factors is a two-level unitary, acting nontrivially only on its own pair of basis states, and that the product of the five factors in the order of (8) is the Fourier matrix.