The quantum Fourier transform on n qubits (N = 2^n basis states) sends each basis state |j\rangle to
Like every gate it has a matrix F_N (a list of rows, m[row][col], acting as new = F @ state). Column j of F_N is the image of |j\rangle, so the entry in row k, column j is
Note the plus sign in the exponent and the factor 1/\sqrt N. For N = 2, \omega = -1 and F_2 is the Hadamard gate H=\tfrac{1}{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}.
Write qft_matrix(n) that returns F_{2^n} as a list of 2^n rows (a numpy array is fine too). Any global phase is accepted (the matrix times a single e^{i\phi}). The larger tests use the helper peek_matrix(m), which returns 8 entries, [m[(j * 40503) % len(m)][(j * 977 + 3) % len(m)] for j in range(1, 9)].
F_N is unitary: F_N^\dagger F_N = I, so it is a legal gate. Press Run with m = np.array(qft_matrix(3)); print(np.allclose(m.conj().T @ m, np.eye(8))) to see it.
Examples
Input: n = 1
Output: [[0.7071067811865475, 0.7071067811865475], [0.7071067811865475, -0.7071067811865475]]
Explanation: the Hadamard gate.
Input: n = 2
Output: [[0.5, 0.5, 0.5, 0.5], [0.5, 0.5j, -0.5, -0.5j], [0.5, -0.5, 0.5, -0.5], [0.5, -0.5j, -0.5, 0.5j]]
Explanation: omega = i, and row k, column j holds i^(jk) / 2. Row 1 is 1, i, i^2, i^3 over 2.
Constraints
- entries are compared with a tolerance of
1e-6
Goals
- Build the matrix of the quantum Fourier transform on n qubits
- See that the QFT on one qubit is the Hadamard gate
- Check that the QFT matrix is unitary