A register of n qubits has N = 2^n basis states, and a state is a list of N complex amplitudes (amplitude k belongs to basis state |k\rangle). The quantum Fourier transform (QFT) is the gate that sends each basis state |j\rangle to an even spread over all basis states, each with its own turn:
So amplitude k of the result is \omega^{jk}/\sqrt N, where \omega = e^{2\pi i/N} is the N-th root of unity: an arrow of length 1/\sqrt N turned by j\cdot k steps of 1/N of a full turn. Note the plus sign in the exponent and the factor 1/\sqrt N; this path always uses this convention.
Write qft_basis(n, j) that returns \mathrm{QFT}\,|j\rangle as a list (or numpy array) of 2^n amplitudes. 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: n = 1, j = 1
Output: [0.7071067811865475, -0.7071067811865475]
Explanation: N = 2 and omega = e^{i pi} = -1, so the amplitudes are 1/sqrt 2 and -1/sqrt 2.
Input: n = 2, j = 1
Output: [0.5, 0.5j, -0.5, -0.5j]
Explanation: omega = e^{i pi/2} = i; the arrows turn a quarter turn each step: 1, i, -1, -i, divided by 2.
Input: n = 2, j = 0
Output: [0.5, 0.5, 0.5, 0.5]
Constraints
- amplitudes are compared with a tolerance of
1e-6
Goals
- Write the quantum Fourier transform of one basis state as a list of amplitudes
- Use the N-th root of unity e^(2 pi i/N) and its powers