The quantum Fourier transform on n qubits (N = 2^n) sends each basis state |j\rangle to \frac{1}{\sqrt N}\sum_{k} e^{2\pi i\,jk/N}|k\rangle. Because a gate is linear, a state with amplitudes a_0, \dots, a_{N-1} goes to the state whose amplitude k is
Signal processing has a famous fast routine for sums like this, np.fft.fft, but it uses a different convention: np.fft.fft(a)[k] is \sum_j a_j\, e^{-2\pi i\,jk/N}, with a minus sign and no factor 1/\sqrt N. So neither np.fft.fft(a) nor np.fft.fft(a) / sqrt(N) is the QFT (the first and third examples show both failing). numpy also has other routines in np.fft, and plain Python works as well.
Write qft_state(state) that returns the QFT of state (a list of 2^n complex amplitudes) as a list or numpy array. Any global phase is accepted: [1j, 0] is the same state as [1, 0]. The larger tests use the helper peek(state), which returns 8 amplitudes, [state[(j * 40503) % len(state)] for j in range(1, 9)].
Examples
Input: state = [0, 1, 0, 0]
Output: [0.5, 0.5j, -0.5, -0.5j]
Explanation: the QFT of |1> with N = 4. np.fft.fft gives [1, -1j, -1, 1j]: no factor 1/2 and
the opposite turn.
Input: state = [0.6, 0.8]
Output: [0.9899494936611665, -0.1414213562373095]
Explanation: (0.6 + 0.8) / sqrt 2 and (0.6 - 0.8) / sqrt 2.
Input: state = [0.5, 0.5j, 0.5, -0.5j]
Output: [0.5, -0.5, 0.5, 0.5]
Explanation: np.fft.fft(state) / 2 is [0.5, 0.5, 0.5, -0.5], a different state.
Constraints
1 <= n <= 8; the state is normalised- amplitudes are compared with a tolerance of
1e-6
Goals
- Apply the quantum Fourier transform to any state
- Relate the QFT to numpy's FFT: opposite sign in the exponent, different scale