Skip to main content
Glossary

Quantum glossary

Quantum Fourier transform

Also: qft

The quantum version of the discrete Fourier transform, acting on amplitudes with only O(n²) gates for n qubits.

You cannot read out all the Fourier coefficients — measuring gives one sample — so the QFT is useful only inside algorithms that arrange for the answer to be concentrated, such as period finding and phase estimation.

See it for yourself

Related terms

  • Quantum phase estimation — An algorithm that reads out the eigenvalue phase of a unitary into a register of qubits.
  • Shor's algorithm — A quantum algorithm that factors integers and computes discrete logarithms in polynomial time.