Quantum phase estimation and the quantum Fourier transform

Short answer: The quantum Fourier transform (QFT) is essentially the discrete Fourier transform viewed as a unitary operation on quantum states. Quantum phase estimation uses it to approximate the phase of an eigenvalue of a unitary operator. Both are standard textbook building blocks, and they underlie later algorithms such as quantum factoring. This is an explainer; nothing here describes a deployed system.

What the quantum Fourier transform is

The Fourier transform, which Joseph Fourier discovered in the early 1800s, extracts the frequency components of a signal and is still at the heart of modern signal processing. The discrete Fourier transform (DFT) takes an input vector and transforms it into an output vector. The IBM Quantum learning course describes the QFT as essentially the DFT viewed as a unitary operation, so it acts on the amplitudes of a quantum register. Cambridge lecture notes on the topic describe how its circuit is derived by rewriting the input state qubit by qubit, with the first qubit holding the most significant bit.

How the circuit is built

The same Cambridge notes say the QFT on n qubits needs n Hadamard gates, n(n-1)/2 two-qubit conditional rotation gates and n/2 SWAP gates. That is order n squared gates in total, which means it can be implemented efficiently in a time that grows polynomially with the number of qubits. The SWAP gates reorder the output qubits.

A polynomial gate count describes the circuit on paper. It does not say how well the circuit would run on today's noisy hardware, and it does not mean a general signal-processing task gets faster.

What phase estimation does

The IBM course describes the phase estimation procedure as a quantum algorithm for the phase estimation problem. You are given a unitary operator and one of its eigenvectors, and the goal is to approximate the phase of the corresponding eigenvalue. The procedure uses control qubits and the inverse of the QFT to read out that phase. The course notes that using more control qubits than one gives better precision, and then describes and analyses the general procedure.

MIT lecture notes by Peter Shor present phase estimation as an application of the QFT, and say it is later used to show how to factor and compute discrete logarithms on a quantum computer. Those algorithms were originally discovered using the QFT directly.

What this does not tell you

These are algorithms and circuit constructions. The sources used here are course notes and lectures, so they say nothing about hardware that runs them at a useful scale. Reading about the gate count is not evidence that any organisation uses them.

FAQ

What is the quantum Fourier transform?

It is essentially the discrete Fourier transform viewed as a unitary operation on quantum states.

What is quantum phase estimation?

A quantum algorithm that approximates the phase of an eigenvalue of a unitary operator, given one of its eigenvectors.

How does phase estimation use the QFT?

It uses control qubits and the inverse of the QFT to extract the phase information.

How many gates does the QFT need?

According to the Cambridge lecture notes, n Hadamard gates, n(n-1)/2 conditional rotation gates and n/2 SWAP gates on n qubits, which is order n squared in total.

Why does it matter for cryptography?

MIT lecture notes say phase estimation is later used to show how to factor and compute discrete logarithms on a quantum computer.