Problem 586355 · medium · Quantum Computing · Level 05 Fourier and Phase

The Fourier Gate, Wire by Wire

quantum Fourier transform · quantum circuits · controlled phase gate · Hadamard gate · swap gate

The quantum Fourier transform on n qubits (N = 2^n) is the gate with \mathrm{QFT}\,|j\rangle = \frac{1}{\sqrt N}\sum_{k} e^{2\pi i\,jk/N}|k\rangle; its matrix has the entry e^{2\pi i\,jk/N}/\sqrt N in row k, column j. A chip cannot apply this N\times N matrix in one go, but it can run a short circuit of small gates that has exactly this matrix. A circuit is a list of gates applied from left to right, in this format:

  • ("h", q): the Hadamard gate H=\tfrac{1}{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix} on qubit q;
  • ("cp", a, b, lam): the controlled phase CP(\lambda), which multiplies the amplitude of every basis state where qubits a and b both read 1 by e^{i\lambda} (a and b play the same role);
  • ("swap", a, b): exchanges qubits a and b.

The standard circuit works through the qubits in order, q = 0, 1, \dots, n-1. For qubit q it applies H to q, then one cp between q and each later qubit m = q+1, \dots, n-1 (in that order) with angle \pi/2^{\,m-q}: \pi/2 with the next qubit, \pi/4 with the one after, and so on. This produces the QFT with the qubits in reversed order, so the circuit ends with the swaps (q, n-1-q) for every q < n-1-q.

Bit order: basis state |b_0 b_1 \dots b_{n-1}\rangle has index int("b0b1...", 2), so qubit 0 is the leftmost bit, the most significant. In 3 qubits, |011\rangle is index 3.

Write qft_circuit(n) that returns such a circuit. Each test builds your circuit's matrix and compares it with the QFT matrix (tolerance 1e-6, any global phase), so any correct circuit passes, not only the standard one. The setup gives circuit_matrix(n, gates) (the matrix as a list of rows) and run_circuit(n, gates, state) (the state after the circuit) for trying things with Run, e.g. print(run_circuit(2, qft_circuit(2), [0, 1, 0, 0])).

Examples

Input:  n = 1
Output: [("h", 0)]
Explanation: on one qubit the QFT is the Hadamard gate.

Input:  n = 2
Output: [("h", 0), ("cp", 1, 0, 1.5707963267948966), ("h", 1), ("swap", 0, 1)]
Explanation: run_circuit(2, this, [0, 1, 0, 0]) gives [0.5, 0.5j, -0.5, -0.5j], the QFT of |1>.

Input:  n = 3
Output: [("h", 0), ("cp", 1, 0, 1.5707963267948966), ("cp", 2, 0, 0.7853981633974483),
         ("h", 1), ("cp", 2, 1, 1.5707963267948966), ("h", 2), ("swap", 0, 2)]

Constraints

  • 1 <= n <= 8; at most 300 gates

Goals

  • Write the quantum Fourier transform as a list of Hadamard, controlled phase and swap gates
  • Get the angle of every controlled phase from the distance between its two qubits
  • Check a circuit by building its matrix and comparing it with the QFT matrix
Starting Python…