Academy K

Quantum Fourier Transform

InterviewDerivationQFTFourier transform

Related module: Fourier transform, phase estimation and factoring

Problem statement

The Quantum Fourier Transform (QFT) on nn qubits maps basis states as:

QFT∣j⟩=1N∑k=0N−1e2πijk/N∣k⟩\text{QFT}|j\rangle = \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}e^{2\pi ijk/N}|k\rangle

where N=2nN = 2^n.

  1. Show that the QFT is unitary.
  2. For n=2n=2 qubits, write out the full matrix.
  3. What does QFT do to the state ∣0⟩⊗n|0\rangle^{\otimes n}?

Hints

Practise this problem

Verify you understand it—not just that you read the answer.

Learn the foundations

The Quantum Computing track covers this topic and more in depth.