A Fourier basis is a frequency-shaped vector used to compare a discrete signal with sinusoidal patterns. Each component follows a geometric sequence, and the discrete Fourier transform uses inner products with these bases to obtain frequency magnitudes and phases. section 7.3.1
For a quantum state of dimension N, the basis state indexed by l has amplitudes 1/sqrt(N) times cis(2πkl/N). Equal magnitudes normalize the state; l determines its frequency. section 7.3.2
Listing 7.3 Computing the Fourier basis for a given N and l
def fourier_basis(N, l):
return [1/sqrt(N) * cis(k*l*2*pi/N) for k in range(N)]
Use the Python function to generate the normalized Fourier basis for any dimension N and frequency index l. section 7.3.2
The basis supports a reusable transform pattern:
- Generate each basis vector for the required frequency index. section 7.3.1
- Compute an inner product between the input amplitudes and each basis to obtain transform entries. section 7.3.1 section 7.3.2
- Use conjugate bases for the QFT and the corresponding positive-angle convention for the IQFT. section 7.3.2
Recovering frequency 13
Applying the IQFT to the four-qubit Fourier basis F13 reveals the binary digits of its frequency from right to left. Hadamard gates and controlled phase rotations recover 1101, then qubit swaps produce computational basis state 13. section 7.4.1
