The quantum Fourier transform on n qubits (N = 2^n) is the gate with
\mathrm{QFT}\,|j\rangle = \frac{1}{\sqrt N}\sum_{k=0}^{N-1} e^{2\pi i\,jk/N}\,|k\rangle ,
so its matrix has the entry e^{2\pi i\,jk/N}/\sqrt N in row k, column j. It is unitary, and the inverse of a unitary matrix is its conjugate transpose (swap rows and columns, conjugate every entry). The inverse QFT undoes the QFT: for every state, applying the QFT and then the inverse QFT gives the state back.
Write inverse_qft(state) that returns the inverse 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.5, 0.5j, -0.5, -0.5j]
Output: [0, 1, 0, 0]
Explanation: this is the QFT of |1> (N = 4), so the inverse gives |1> back.
Input: state = [0, 1, 0, 0]
Output: [0.5, -0.5j, -0.5, 0.5j]
Explanation: the inverse QFT of |1> turns the other way: amplitude 1 is -0.5j, not 0.5j.
Input: state = [0.9899494936611665, -0.1414213562373095]
Output: [0.6, 0.8]
Constraints
1 <= n <= 8; the state is normalised- amplitudes are compared with a tolerance of
1e-6
Goals
- Apply the inverse quantum Fourier transform to a state
- Use that the inverse of a unitary gate is its conjugate transpose