This note is part of [[quantum/Practical Quantum Information System]]. > [!info] Course code > Use the companion repository for this lecture's runnable lab, helper functions, and regression checks: > - [notebooks/by_concept/quantum_fourier_transform.ipynb](https://github.com/montekkundan/quantum-code/blob/main/notebooks/by_concept/quantum_fourier_transform.ipynb) > - [qcourse/algorithms.py](https://github.com/montekkundan/quantum-code/blob/main/qcourse/algorithms.py) > - [tests/test_protocols_algorithms_qec.py](https://github.com/montekkundan/quantum-code/blob/main/tests/test_protocols_algorithms_qec.py) [TODO: add video - Quantum Fourier Transform] ## What This Concept Is The [[quantum/Glossary#Quantum Fourier Transform|Quantum Fourier Transform]] is one of the major reusable subroutines in quantum computing. It is not just a fancy gate sequence. It is a basis change that turns hidden periodic or phase structure into something measurement can access efficiently. If Shor's algorithm is the headline, the QFT is one of the main engines under the hood. Learning it well also helps you see how phase, interference, and circuit decomposition work together in a serious algorithm. ## Foundation Terms You Need First The [[quantum/Glossary#Quantum Fourier Transform|QFT]] is a unitary transform on computational basis states. [[quantum/Glossary#Phase kickback|Phase kickback]] helps you understand how phase information gets encoded before the transform. [[quantum/Glossary#Period finding|Period finding]] is the structured problem the QFT is often used to expose. The main beginner mistake is to think of the QFT as "just another circuit." It is better understood as a coordinate change designed to make periodic structure visible. ## How The Idea Actually Works Classically, the Fourier transform reorganizes data by frequency content. Quantumly, the QFT reorganizes amplitudes so that hidden periodic structure concentrates into predictable output patterns. That is why the subroutine is so useful. If a state carries phase information related to a period or eigenvalue, the QFT converts that information into basis states you can sample. The quantum device is not symbolically solving the period problem in one line. It is transforming the representation so the important structure becomes measurable. Circuit-wise, the QFT is built from a clear pattern of Hadamards and controlled phase rotations. This makes it a good note for both theory and implementation. You can read the algebra, and then you can see exactly how that algebra becomes a circuit. It is also one of the best examples of why later simplification, approximation, and transpilation matter. The exact textbook QFT circuit is rarely the end of the story once real hardware costs enter. ## Why It Matters - It is central to phase estimation, order finding, and Shor's algorithm. - It shows how representation changes can create algorithmic advantage. - It is a strong example of a mathematically meaningful circuit pattern rather than a heuristic circuit trick. ## Related Questions > [!question] Why is the QFT useful even though measuring gives only one sample? >> [!answer] The QFT reshapes amplitudes so samples are concentrated around values that encode the hidden period or phase. Repeated samples plus classical post-processing can then recover the structured information. > [!question] Why is the inverse QFT important in algorithms? >> [!answer] Many algorithms first encode phase information into amplitudes. The inverse QFT converts that phase structure into computational-basis information that can be sampled directly. > [!question] Why does approximate QFT matter for implementation? >> [!answer] Small controlled rotations can be expensive and noise-sensitive. Approximate QFT drops rotations that contribute little at the target precision, trading exactness for shorter circuits. ## Study Checks Use these after the explanation, not before it. ### Quick Checks - What does the QFT help reveal? **Answer:** It makes periodic or phase structure visible in computational-basis samples. ### Oral Exam Anchors > [!question] Oral exam anchor > Explain the role of the Quantum Fourier Transform in Shor's algorithm. A good answer should say: Shor's algorithm reduces factoring to order finding. The quantum part prepares a superposition over exponents, computes modular exponentiation, and uses the Quantum Fourier Transform to convert periodic structure into peaks in the frequency domain. Measurement gives data from which the period can be recovered using classical continued fractions or related post-processing. The QFT is not just a faster classical Fourier transform. It is a unitary basis change applied to quantum amplitudes. Its role is to make periodicity visible in samples without reading out the whole exponentially large state. ## Practical Lab Use a small-register implementation so you can inspect every gate and every phase. - Implement the QFT and inverse QFT on a small number of qubits. - Track how basis states and simple superpositions transform. - Compare your hand-built circuit to a transpiled version and note the cost differences. ## Homework Connect the circuit pattern to the periodic-structure story. - State what the QFT does to computational basis states. - Explain why the QFT is useful for period finding. - Estimate the gate scaling of the exact small-register construction you used. ## References - Scott Aaronson, [Introduction to Quantum Information Science](https://www.scottaaronson.com/qclec.pdf), Lecture 20. - [[Resources]] - IBM Quantum Learning, [learning portal](https://quantum.cloud.ibm.com/learning/en). - Qiskit documentation, [main docs](https://qiskit.org/documentation/).