QFT Defined

You spent the last chapter with the classical DFT. You know its formula, you know the roots-of-unity orthogonality that makes it unitary, and you know the FFT does it in O(N\log N).

Now the pivot. Take an n-qubit quantum state. Its amplitude vector has N = 2^n complex entries — an exponentially long list compared to n. Think of those amplitudes as a signal. Run the DFT on that signal. That one sentence defines the Quantum Fourier Transform. It is the same linear map you already know, but now applied to the amplitude vector of a quantum state instead of to a list on a desktop computer.

Why is this interesting? Because the amplitude vector of an n-qubit state lives in a 2^n-dimensional Hilbert space for free — you need only n physical qubits to hold it. A classical FFT on a 2^n-entry vector requires O(n \cdot 2^n) operations, exponential in the qubit count. A quantum circuit can implement the exact same linear map on the amplitudes using only O(n^2) gates. That is the speedup the next chapter makes concrete. This chapter's job is narrower: state the definition cleanly, prove it is a valid quantum operation (unitary), write out the small cases so you can compute with it, and say where it will be used.

The definition, in one line

Write N = 2^n. Encode integers j = 0, 1, \ldots, N-1 as n-bit binary strings, and use those as computational-basis labels. So |j\rangle is the n-qubit state |j_{n-1} j_{n-2} \cdots j_0\rangle whose bit-pattern is the binary expansion of j.

Reading the definition, symbol by symbol.

• |j\rangle is a computational-basis state — a specific configuration of n classical bits. For n = 3, |5\rangle = |101\rangle: a product state with qubit 2 in |1\rangle, qubit 1 in |0\rangle, qubit 0 in |1\rangle.
• The sum \sum_k runs over all N = 2^n computational-basis states. The output is always a superposition spread across every basis state.
• The amplitude attached to |k\rangle is \frac{1}{\sqrt N} e^{2\pi i\, jk/N} — a unit-modulus complex number (a phase) divided by \sqrt N. So the output of QFT on a basis state is a uniform-magnitude superposition (every coefficient has the same absolute value 1/\sqrt N) with phases that depend on both j and k.
• For any n-qubit input state, the QFT outputs a state whose amplitudes are the DFT of the input amplitudes.

Why this is a clean definition: it gives the QFT's action on every basis vector, and because QFT is linear, that is enough to determine the action on every state. Linearity is built into the fact that the QFT is a unitary matrix — the action on basis states specifies the matrix columns, and matrix-times-vector handles everything else.

QFT is unitary — the orthogonality argument

Before using the QFT in a quantum algorithm, confirm it is a valid quantum operation. Every operation a quantum computer performs (apart from measurement) is unitary, so the QFT must satisfy \text{QFT}^\dagger\, \text{QFT} = I.

Read off the matrix. Using \omega = e^{2\pi i/N},

The adjoint has entries (\text{QFT}^\dagger)_{jk} = \overline{\text{QFT}_{kj}} = \frac{1}{\sqrt N}\,\omega^{-jk} (complex conjugation flips the sign of the exponent because \overline{\omega^{jk}} = \omega^{-jk}).

Compute \text{QFT}^\dagger\, \text{QFT} entry by entry:

Why that last sum collapses: if j = j', every term is \omega^0 = 1 and the sum is N, giving diagonal entry N/N = 1. If j \neq j', the exponent j' - j is a non-zero integer between -(N-1) and N-1, so \omega^{j'-j} \neq 1. The sum \sum_{k=0}^{N-1} (\omega^{j'-j})^k is a geometric series with ratio r = \omega^{j'-j}, which equals (r^N - 1)/(r - 1) = (1 - 1)/(r-1) = 0 because \omega^N = 1. The off-diagonal entries vanish.

So (\text{QFT}^\dagger\,\text{QFT})_{j,j'} = \delta_{j,j'}, meaning \text{QFT}^\dagger\,\text{QFT} = I. The QFT is unitary, and its inverse is obtained by flipping the sign of every phase: \text{QFT}^\dagger|k\rangle = \frac{1}{\sqrt N}\sum_j e^{-2\pi i\, jk/N}|j\rangle — the "inverse QFT" (sometimes written \text{QFT}^{-1} or \text{QFT}^\dagger).

This is the same orthogonality calculation you did for the classical DFT in the previous chapter. It is worth repeating in the quantum-mechanical setting because it underwrites why the QFT is a valid gate at all: unitarity is the rule that says a quantum operation preserves probability, and without that, the QFT could not be implemented by a quantum circuit.

The single-qubit case — QFT is the Hadamard

Start with the smallest case: n = 1 qubit, so N = 2, and \omega = e^{2\pi i/2} = e^{i\pi} = -1.

Plug into the definition:

So \text{QFT}|0\rangle = |+\rangle and \text{QFT}|1\rangle = |-\rangle. Compare with the Hadamard gate: H|0\rangle = |+\rangle and H|1\rangle = |-\rangle. For one qubit, the QFT is exactly the Hadamard. No qualification, no up-to-a-phase; the two matrices are equal:

Why this is not a coincidence: the Hadamard is the Fourier transform on the group \mathbb{Z}_2 (two elements, addition mod 2). The QFT on n qubits is the Fourier transform on the group \mathbb{Z}_{2^n}. At n = 1 these match up exactly. In the next chapter you will see that the n-qubit QFT is built by applying Hadamards on each wire in combination with controlled phase gates — the Hadamard is literally one of the building blocks of the larger QFT.

The two-qubit case — a 4×4 matrix

Step up to n = 2 qubits, N = 4, \omega = e^{2\pi i/4} = i. The matrix entries \text{QFT}_{kj} = \frac{1}{2}\,i^{jk} give

This matrix is identical to the classical F_4 you wrote out in the previous chapter — because the QFT on n qubits is the classical DFT on N = 2^n points, written as a matrix on the computational basis of the quantum register.

Reading the columns: column j is the QFT image of the basis state |j\rangle. Column 0 is all 1/2's — the state \text{QFT}|0\rangle = \tfrac{1}{2}(|0\rangle + |1\rangle + |2\rangle + |3\rangle), a uniform superposition. Column 1 is the QFT image of |1\rangle: the amplitudes \tfrac{1}{2}, \tfrac{i}{2}, -\tfrac{1}{2}, -\tfrac{i}{2}, which rotate around the unit circle once as k runs from 0 to 3. Column 2 spins twice; column 3 spins three times (or equivalently, once backward).

The pattern generalises. For any n, \text{QFT}|j\rangle is a uniform-magnitude superposition whose phase on |k\rangle is \omega^{jk} — that is, the k-th phase winds j times around the unit circle as k varies.

Worked examples

Where the QFT appears

The QFT is not a stand-alone application. It is a subroutine that sits inside bigger quantum algorithms, turning one kind of structure into another. Four places where it is the heart of the machine:

Shor's factoring algorithm (1994). Shor's protocol reduces integer factoring to period-finding: given a function f(x) = a^x \bmod N with period r, find r. You prepare a superposition over many inputs x, compute f(x) into a second register, and then — crucially — apply the QFT to the first register. The phases from f's periodicity interfere constructively at multiples of 1/r and destructively elsewhere. Measuring the post-QFT register gives, with high probability, a sample from which you can classically extract r. The QFT is what converts the period into a peak that a measurement can read.

Quantum phase estimation. Given a unitary U and an eigenstate |u\rangle with U|u\rangle = e^{2\pi i \varphi}|u\rangle, phase estimation extracts \varphi to n bits of precision. The protocol applies a chain of controlled-U^{2^j} operations to build up a state whose phases encode \varphi in binary — then applies the inverse QFT to convert that phase pattern into the measurable bit-string \varphi_1 \varphi_2 \ldots \varphi_n. Every use of QPE in the wild (quantum chemistry, HHL's linear-systems solver, Shor's algorithm) runs an inverse QFT as its final step.

Hidden Subgroup Problem for finite abelian groups. Given a function f : G \to S that is constant on cosets of an unknown subgroup H \le G and distinct across cosets, the HSP is to find H. For G a finite abelian group — \mathbb{Z}_{N_1} \times \cdots \times \mathbb{Z}_{N_k} — the quantum algorithm is: superpose inputs, apply f, and QFT. The QFT in question is the group Fourier transform for G (which specialises to the \mathbb{Z}_{2^n} QFT when the group is n bits). Simon's algorithm, discrete logarithm, and Shor's factoring all fit this template.

Quantum signal processing. Recent algorithms (quantum SVT, block encoding, signal-processing-based eigenvalue amplification) use the QFT as a building block for controlled amplitude manipulation. The modern quantum algorithmic toolkit treats the QFT as one of three primitive subroutines — alongside amplitude amplification (Grover-type) and quantum walks — that generically produce speedups.

The speedup — one careful sentence

Here is the subtle part that separates pop-science from the real story.

The QFT on n qubits can be implemented by a quantum circuit using O(n^2) gates — you will see the construction in the next chapter. Classical FFT on a length-N = 2^n vector requires O(n \cdot 2^n) operations. The ratio is exponential in n — an enormous speedup.

But: the QFT does not let you compute the classical DFT of a desktop signal exponentially faster. To benefit from the QFT, the input signal must already exist as a quantum state on n qubits — that is, its amplitudes must be loaded into the amplitudes of a quantum register. Loading N = 2^n classical numbers into an n-qubit state takes O(N) work in general, wiping out the QFT's gain. Worse, the output of the QFT is a quantum state; reading it destroys the superposition and gives you only one n-bit basis label. You cannot read out the transformed amplitude vector wholesale.

So the QFT's speedup is real but conditional. It pays off when:

1. The input state can be prepared cheaply (either by a small circuit that generates superposition, such as H^{\otimes n}|0^n\rangle for the uniform superposition, or as the output of a previous quantum subroutine).
2. The downstream step only needs a single sample from the transformed distribution — or only needs interference patterns among the amplitudes, which measurement can resolve.

Shor's algorithm satisfies both: the state before QFT is a cheap superposition tagged by modular exponentiation, and the post-QFT measurement just samples from a peaked distribution to reveal the period. Phase estimation satisfies both: the pre-QFT state is built by controlled-U's, and the post-QFT measurement directly reads the binary expansion of \varphi.

Hype check. "The QFT lets a quantum computer compute the DFT exponentially faster" is a common headline. The linear map is computed with exponentially fewer gates, yes — but the quantum DFT is not a drop-in replacement for a classical FFT in a signal-processing pipeline, because loading the input and extracting the output are each themselves exponentially expensive in general. The QFT's power is in how it composes with the rest of a quantum algorithm, not in how fast it transforms arbitrary classical data.

Common confusions

• "The QFT is a fast classical FFT." It is not. The QFT and FFT compute the same linear map, but they act on different kinds of data. The FFT's input is a classical list of N numbers in memory; the QFT's input is a superposition whose N amplitudes are physically encoded in n qubits. The QFT's O(n^2) gate count versus the FFT's O(n \cdot 2^n) operation count reflects an exponential gap in the representation of the amplitude vector — not an exponential speedup for the original classical DFT task.

• "For n = 1, the QFT is not quite the Hadamard — there's a phase." No — for n = 1, \text{QFT}_1 = H exactly, with no residual phase. Calculations like e^{2\pi i \cdot 1 \cdot 1 / 2} = e^{i\pi} = -1 give the Hadamard's minus sign directly. The equality is on the nose.

• "QFT on computational-basis states gives random-looking superpositions." They look random only if you do not know the phase formula. Every output of \text{QFT}|j\rangle has exactly the same magnitudes (1/\sqrt N on every basis state) and phases e^{2\pi i\, jk/N} — a maximally simple and structured superposition called the "Fourier basis" vector |\widetilde{j}\rangle. It is the most tightly patterned kind of quantum state.

• "QFT needs large N to be useful." A common misconception. For n = 1 qubit the QFT reduces to the Hadamard — already useful. Any quantum algorithm that encodes information in the phase of a superposition is implicitly using QFT-style thinking, regardless of the register size.

• "You can read off the classical DFT from the QFT's output." You can read out one basis state per run (with the probability distribution determined by the QFT output amplitudes). To estimate all the amplitudes, you need exponentially many runs. This is why QFT is useful in algorithms (Shor, phase estimation) where the output is peaked — a small number of samples quickly pinpoint the answer.

Going deeper

The product-form identity — the key to the circuit

The QFT has a remarkable structural identity that makes its efficient circuit possible. Write j in binary as j = j_{n-1}j_{n-2}\ldots j_0, and introduce the notation 0.j_\ell j_{\ell-1}\ldots j_1 = j_\ell/2 + j_{\ell-1}/4 + \cdots + j_1/2^\ell for binary fractions. Then the QFT has the beautiful factored form

This says: the QFT's output is a product state across the n qubits (not an entangled state!), and each qubit's state is \tfrac{1}{\sqrt 2}(|0\rangle + e^{2\pi i \phi_\ell}|1\rangle) for a specific phase \phi_\ell built from the binary expansion of j.

The product form is why the QFT has an O(n^2) circuit. Each qubit's output can be built independently using a Hadamard and a small number of controlled phase gates driven by the other qubits. The next chapter — QFT circuit construction — derives this factoring in full and turns it into an explicit gate sequence.

QFT as a change of basis — the Fourier basis

Every unitary on n qubits is a change of basis. The QFT is the change from the computational basis \{|0\rangle, |1\rangle, \ldots, |N-1\rangle\} to the Fourier basis \{|\widetilde 0\rangle, |\widetilde 1\rangle, \ldots, |\widetilde{N-1}\rangle\}, where |\widetilde k\rangle = \text{QFT}|k\rangle.

Expressed differently: the computational-basis states are eigenstates of the "position" observable (the integer represented by the bits); the Fourier-basis states are eigenstates of the "momentum" observable (the conjugate observable, corresponding to the cyclic shift |j\rangle \to |j+1 \bmod N\rangle). The QFT is the rotation between these two bases — the analog, on finite qubits, of the Fourier transform that exchanges position and momentum in continuous quantum mechanics.

This duality generalises: on any finite abelian group G, there is a "position" basis (elements of G) and a "Fourier" basis (characters of G), and the group Fourier transform rotates between them. For G = \mathbb{Z}_{2^n}, that transform is the n-qubit QFT.

QFT on arbitrary abelian groups — the Hidden Subgroup Problem

Given a finite abelian group G and a function f : G \to S with the property that f(g) = f(g') iff g - g' \in H for some unknown subgroup H \le G, the Hidden Subgroup Problem asks you to find H.

The standard quantum algorithm is:

1. Prepare \frac{1}{\sqrt{|G|}}\sum_{g \in G} |g\rangle|0\rangle using the QFT over G on the first register starting from |0\rangle.
2. Compute f into the second register: \frac{1}{\sqrt{|G|}}\sum_g |g\rangle|f(g)\rangle.
3. Measure the second register. The first register collapses to a uniform superposition over a coset of H.
4. Apply \text{QFT}_G to the first register. By character theory, the resulting state is supported on H^\perp — the subgroup of characters that are trivial on H.
5. Measure. Accumulate samples and classically reconstruct H.

For G = \mathbb{Z}_{2^n}, \text{QFT}_G is exactly the QFT you have just defined. Shor's algorithm is the HSP over G = \mathbb{Z}_N for N the number being factored; Simon's algorithm is the HSP over G = \mathbb{Z}_2^n (where the group is a product of two-element groups and the Fourier transform is H^{\otimes n}).

The non-abelian HSP (for groups like the symmetric group S_n or the dihedral group) is a major open problem — an efficient quantum algorithm for it would solve graph isomorphism and the shortest vector problem, which still resist quantum attack after twenty years.

Approximate QFT — dropping the small phases

The QFT circuit (next chapter) uses controlled phase gates with phases of the form 2\pi/2^k. For large k, these phases are vanishingly small — a rotation by 2\pi/2^{20} is barely distinguishable from the identity. Coppersmith (1994) showed that dropping gates with k larger than a threshold m produces an approximate QFT with error bounded by O(n 2^{-m}). Choosing m = O(\log n) suffices for polynomial precision — and reduces the circuit depth from O(n^2) to O(n\log n), a practical win when compiling for real hardware where every gate is noisy.

A note on practical circuit cost

Current quantum hardware (2025) is firmly in the NISQ era. A 100-qubit QFT implemented with O(n^2) = 10^4 gates is already a non-trivial circuit, especially because many of the controlled phase rotations need to be compiled into hardware-native gates (CZ plus single-qubit rotations), multiplying the gate count several-fold. Depth — the length of the longest gate sequence — scales as O(n) in naive constructions and can be further parallelised.

For Shor-scale factoring of a 2048-bit RSA modulus, the QFT subroutine sits on a register of about 4000 qubits and requires billions of gates end-to-end — which is why fault-tolerant error correction (not just QFT-specific tricks) is the bottleneck for cryptographically relevant quantum attacks. Today's largest machines have around 1000 physical qubits; the gap to cryptographic attack is still six orders of magnitude in qubits and many more in gate fidelity.

The Indian context — quantum algorithms at TIFR and IISc

Research groups at the Tata Institute of Fundamental Research, Mumbai, and the Indian Institute of Science, Bangalore, have active programmes in quantum algorithms and their theoretical analysis, including work on QFT-based algorithms and the HSP framework. India's National Quantum Mission (launched 2023, ₹6000 crore over 8 years) funds a portion of this research, with dedicated hubs at IIT Madras, IIT Bombay, and C-DAC. The QFT is one of the very first algorithms any new student of quantum computing implements in a lab — typically in Qiskit, on an IBM Quantum machine accessed over the cloud.

Where this leads next

• QFT circuit construction — how to build an n-qubit QFT circuit using O(n^2) Hadamards and controlled phase gates, via the product-form identity. The next chapter.
• Why QFT is efficient — the head-to-head comparison of classical FFT versus QFT, and what the speedup means in practice.
• Quantum phase estimation — the flagship QFT application: extracting an eigenphase of a unitary.
• Shor's algorithm — factoring by period-finding, with the QFT as its heart.
• Hidden Subgroup Problem — the unifying framework for QFT-based speedups.

References

1. Wikipedia, Quantum Fourier transform — definition, circuit, and references.
2. Nielsen and Chuang, Quantum Computation and Quantum Information (2010), §5.1 — QFT definition and circuit derivation — Cambridge University Press.
3. John Preskill, Lecture Notes on Quantum Computation, Chapter 6 — QFT and its algorithmic applications — theory.caltech.edu/~preskill/ph229.
4. Don Coppersmith, An Approximate Fourier Transform Useful in Quantum Factoring (1994) — arXiv:quant-ph/0201067. The approximate-QFT trick that makes practical Shor feasible.
5. Richard Jozsa, Quantum Factoring, Discrete Logarithms, and the Hidden Subgroup Problem (2000) — arXiv:quant-ph/0012084. The unifying HSP view, with QFT at its centre.
6. Qiskit Textbook, Quantum Fourier Transform — hands-on implementation with Qiskit.