{ "id": "ept5za50zp", "slug": "quantum-fourier-transform", "title": "Quantum Fourier transform", "updated": "2026-10-21", "topic_path": [ { "id": "technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/topics/technology" }, { "id": "technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing" }, { "id": "technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai" }, { "id": "technology.computing.ai.algorithms", "label": "Algorithms and computational methods", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.algorithms" }, { "id": "technology.computing.ai.numerical_string_geometry", "label": "Numerical, string, and geometric algorithms", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.numerical_string_geometry" }, { "id": "technology.computing.ai.numerical_string_geometry.fourier_signal_transforms", "label": "Fourier and signal transforms", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.numerical_string_geometry.fourier_signal_transforms" } ], "geo": [ { "id": "geo.nongeo.t1946.technology.computing.ai.numerical_string_geometry.fourier_signal_transforms", "label": "Non-geographic · 1946 to 2000: Fourier and signal transforms", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.numerical_string_geometry.fourier_signal_transforms", "path": [ { "id": "geo.nongeo", "label": "Non-geographic", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo" }, { "id": "geo.nongeo.t1946", "label": "Non-geographic · 1946 to 2000", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946" }, { "id": "geo.nongeo.t1946.technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology" }, { "id": "geo.nongeo.t1946.technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing" }, { "id": "geo.nongeo.t1946.technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai" }, { "id": "geo.nongeo.t1946.technology.computing.ai.algorithms", "label": "Algorithms and computational methods", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.algorithms" }, { "id": "geo.nongeo.t1946.technology.computing.ai.numerical_string_geometry", "label": "Numerical, string, and geometric algorithms", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.numerical_string_geometry" }, { "id": "geo.nongeo.t1946.technology.computing.ai.numerical_string_geometry.fourier_signal_transforms", "label": "Fourier and signal transforms", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.numerical_string_geometry.fourier_signal_transforms" } ] } ], "excerpt": "The quantum Fourier transform (QFT) is a quantum algorithm applying the discrete Fourier transform to a quantum state's amplitudes, used in Shor's algorithm and phase estimation.", "snippet": "The quantum Fourier transform (QFT) is a quantum algorithm applying the discrete Fourier transform to a quantum state's amplitudes, used in Shor's algorithm and phase estimation.", "node": "technology.computing.ai.numerical_string_geometry.fourier_signal_transforms", "markdown": "# Quantum Fourier transform\n\nThe quantum [Fourier transform](https://www.edgepedia.org/fourier-transform) (QFT) is a quantum algorithm that applies the discrete Fourier transform to the amplitude vector of a quantum state, and it serves as the central subroutine in quantum phase estimation, Shor's factoring algorithm, and related periodicity-finding methods.[1](https://ar5iv.labs.arxiv.org/html/quant-ph/0006004) • [2](https://www.cambridge.org/core/books/quantum-algorithms/quantum-fourier-transform/4F2B669EE1363DF9BBB83D66F05C6041) On an input state \\( \\sum_{x} \\alpha_{x} |x\\rangle \\) it produces \\( \\sum_{x} \\beta_{x} |x\\rangle \\), where \\( \\beta_{x} = \\tfrac{1}{\\sqrt{m}} \\sum_{y} (e^{2\\pi i/m})^{x \\cdot y} \\alpha_{y} \\).[1](https://ar5iv.labs.arxiv.org/html/quant-ph/0006004) The circuit needs only \\( O(n^{2}) \\) gates for \\( n \\) qubits, while the classical FFT takes \\( O(N \\log N) \\) arithmetic operations for \\( N = 2^{n} \\); however, the QFT prepares a transformed quantum state whose amplitudes cannot all be read out from one run, whereas the FFT returns a list of all Fourier coefficients.[3](https://link.springer.com/article/10.1007/s11128-026-05067-7) • [4](https://prod-edxapp.edx-cdn.org/assets/courseware/v1/8f101da9d14cfeec83df9e42a70562bf/c4x/BerkeleyX/CS-191x/asset/chap5.pdf) Its value lies in phase estimation and periodicity extraction, not in computing Fourier coefficients.[5](https://export.arxiv.org/pdf/quant-ph/0211030v1.pdf)\n\n| Key fact | Value |\n|---|---|\n| Transform performed | \\( \\beta_{x} = \\tfrac{1}{\\sqrt{m}} \\sum_{y} (e^{2\\pi i/m})^{x \\cdot y} \\alpha_{y} \\), the DFT on amplitudes[1](https://ar5iv.labs.arxiv.org/html/quant-ph/0006004) |\n| Exact circuit, \\( n \\) qubits | \\( n \\) Hadamard gates, \\( n(n-1)/2 \\) controlled rotations, \\( n/2 \\) SWAPs: \\( O(n^{2}) \\) gates[6](https://www.cl.cam.ac.uk/teaching/2324/QuantComp/Quantum_Computing_Lecture_9_2024.pdf) |\n| Classical comparison | O(n·2ⁿ) bit-level gates classically vs O(n²) quantum[3](https://link.springer.com/article/10.1007/s11128-026-05067-7) |\n| Semiclassical variant | \\( O(n) \\) gates, no two-qubit gates, but requires sequential measurement[7](https://www.science.org/doi/10.1126/science.1110335) |\n| Approximate QFT depth | \\( O(\\log n + \\log \\log(1/\\varepsilon)) \\) with an \\( \\Omega(\\log n) \\) lower bound[1](https://ar5iv.labs.arxiv.org/html/quant-ph/0006004) |\n| Fault-tolerant cost | \\( O(n \\log n) \\) T gates (Nam, Su, and Maslov, 2020)[8](https://doi.org/10.1038/s41534-020-0257-5) |\n| Main applications | Shor's algorithm, quantum phase estimation, HHL, quantum PCA[3](https://link.springer.com/article/10.1007/s11128-026-05067-7) |\n\n## How it works\n\nFor \\( N = 2^{n} \\), the QFT is the unitary \\( U_{\\mathrm{FT}} = \\tfrac{1}{\\sqrt{N}} \\sum_{x,y=0}^{N-1} e^{2\\pi i x y / N} |y\\rangle \\langle x| \\); its matrix has \\( j \\cdot k \\)-th entry \\( \\omega^{jk} \\) with \\( \\omega = e^{2\\pi i / N} \\).[9](https://qubit.guide/10.9-quantum-fourier-transform) • [4](https://prod-edxapp.edx-cdn.org/assets/courseware/v1/8f101da9d14cfeec83df9e42a70562bf/c4x/BerkeleyX/CS-191x/asset/chap5.pdf) It maps a basis state \\( |j\\rangle \\) to \\( \\tfrac{1}{\\sqrt{N}} \\sum_{k} e^{2\\pi i j k / N} |k\\rangle \\).[6](https://www.cl.cam.ac.uk/teaching/2324/QuantComp/Quantum_Computing_Lecture_9_2024.pdf)\n\nThe efficient circuit exists because the output is a product state: \\( F_{N}|k\\rangle = \\bigotimes_{\\ell=1}^{n} \\tfrac{1}{\\sqrt{2}} (|0\\rangle + e^{2\\pi i\\, 0.k_{n-\\ell+1}\\ldots k_{n}} |1\\rangle) \\), where \\( 0.j_{1} \\ldots j_{n} \\) denotes a binary fraction.[10](https://gilyen.hu/teaching/PCMI_2023_QFT_prez_day_1.pdf) • [11](https://dojo.qulacs.org/en/qp_main/notebooks/2.3_quantum_Fourier_transform.html) Each output qubit depends on a binary fraction of the input bits, so the transform factorizes into single-qubit operations and controlled phase rotations. The \\( n = 1 \\) case is exactly the [Hadamard gate](https://www.edgepedia.org/hadamard-gate); more generally, the QFT is the Fourier transform on the cyclic group \\( \\mathbb{Z}/2^{n}\\mathbb{Z} \\), while the [Hadamard transform](https://www.edgepedia.org/hadamard-transform) is the Fourier transform on \\( (\\mathbb{Z}/2\\mathbb{Z})^{n} \\).[9](https://qubit.guide/10.9-quantum-fourier-transform)\n\n## How it is done\n\nThe standard circuit for \\( n \\) qubits applies, for each qubit, a Hadamard followed by controlled rotations \\( R_{k} = \\mathrm{diag}(1, e^{2\\pi i / 2^{k}}) \\) from the later qubits, then reverses the qubit order with a SWAP stage.[6](https://www.cl.cam.ac.uk/teaching/2324/QuantComp/Quantum_Computing_Lecture_9_2024.pdf) • [11](https://dojo.qulacs.org/en/qp_main/notebooks/2.3_quantum_Fourier_transform.html) One source counts \\( n \\) Hadamards, \\( n(n-1)/2 \\) controlled rotations, and \\( n/2 \\) SWAPs, for a scaling of \\( \\Theta(n^{2}) \\).[6](https://www.cl.cam.ac.uk/teaching/2324/QuantComp/Quantum_Computing_Lecture_9_2024.pdf) • [12](https://quantumnanophotonics.org/wp-content/uploads/2023/07/module4lecture1.pdf) The inverse QFT reverses the circuit with each gate inverted: Hadamard and SWAP are self-inverse, and \\( R_{k}^{\\dagger} = \\mathrm{diag}(1, e^{-2\\pi i / 2^{k}}) \\).[6](https://www.cl.cam.ac.uk/teaching/2324/QuantComp/Quantum_Computing_Lecture_9_2024.pdf)\n\n## Origin\n\nThe observation that quantum circuit size for the Fourier transform can be polynomial in \\( \\log m \\) was first made by Shor in 1994, at the Foundations of Computer Science conference, in his algorithms for discrete logarithm and factoring.[1](https://ar5iv.labs.arxiv.org/html/quant-ph/0006004) • [13](https://epubs.siam.org/doi/10.1137/S0036144598347011) Robert B. Griffiths and Chi-Sheng Niu, of Carnegie Mellon University, published the semiclassical Fourier transform in [Physical Review Letters](https://www.edgepedia.org/physical-review-letters) in 1996.[14](https://doi.org/10.1103/physrevlett.76.3228)\n\n## Variants\n\n**Semiclassical QFT.** Griffiths and Niu showed that when the transform immediately precedes measurement, as in [Shor's algorithm](https://www.edgepedia.org/shors-algorithm), every two-bit gate can be replaced by one-bit gates controlled by classical signals: each bit is measured, and the outcome \\( c \\) updates a phase \\( \\varphi' = \\varphi/2 + c/4 \\) applied to the next bit before it is measured.[15](https://arxiv.org/pdf/quant-ph/9511007) This reduces the gate count from \\( O(n^{2}) \\) to \\( O(n) \\).[7](https://www.science.org/doi/10.1126/science.1110335) The cost is sequentiality: one bit must be measured before the next is processed, which is a disadvantage if qubits decohere rapidly on the measurement timescale, and the scheme destroys the superposition, so it is useful only when the QFT directly precedes measurement.[15](https://arxiv.org/pdf/quant-ph/9511007) • [16](http://arxiv.org/pdf/1006.3989) A coherent version replaces the measurement-controlled corrections with controlled qubits.[9](https://qubit.guide/10.9-quantum-fourier-transform)\n\n**Approximate QFT.** Omitting rotations \\( R_{k} \\) with \\( k = \\Omega(\\log n) \\) gives an \\( O(n \\log n) \\)-gate circuit implementing the QFT with precision \\( 1/\\mathrm{poly}(n) \\).[17](https://www.cs.umd.edu/~amchilds/teaching/w13/l02.pdf) Truncating each qubit's binary-fraction phase to \\( m = O(\\log(n/\\varepsilon)) \\) bits yields phase error at most \\( 2\\pi n / 2^{m} \\).[18](https://www.rintonpress.com/xqic7/qic-7-4/383-391.pdf) • [19](https://arxiv.org/html/2505.00701) In fault-tolerant (Clifford+T) form, the standard approximate QFT has a higher T-count; Yunseong Nam, Yuan Su, and Dmitri Maslov reduced this to \\( O(n \\log n) \\) for fixed error \\( \\varepsilon \\), reaching roughly \\( 8n(\\log n - 2) + 1.2 \\log^{2} n \\) T gates in npj Quantum Information in 2020.[8](https://doi.org/10.1038/s41534-020-0257-5) For depth, Cleve and Watrous gave parallel circuits of depth \\( O(\\log n + \\log \\log(1/\\varepsilon)) \\) for the QFT modulo \\( 2^{n} \\) in 2000, improving the previous \\( O(n) \\) depth, and proved an \\( \\Omega(\\log n) \\) lower bound.[1](https://ar5iv.labs.arxiv.org/html/quant-ph/0006004)\n\n## Applications\n\nIn quantum phase estimation, the inverse QFT applied to the first register yields a \\( t \\)-bit approximation \\( \\tilde{\\varphi} \\) of an eigenvalue phase \\( \\varphi \\); to obtain \\( n \\)-bit accuracy with success probability at least \\( 1 - \\varepsilon \\), the register needs \\( t = n + \\lceil \\log_{2}(2 + 1/(2\\varepsilon)) \\rceil \\) qubits.[6](https://www.cl.cam.ac.uk/teaching/2324/QuantComp/Quantum_Computing_Lecture_9_2024.pdf) • [12](https://quantumnanophotonics.org/wp-content/uploads/2023/07/module4lecture1.pdf) Shor's factoring and discrete-log algorithms run in random polynomial time and were the first examples of quantum cryptanalysis; the discrete-log version uses a QFT over \\( \\mathbb{Z}_{N} \\times \\mathbb{Z}_{N} \\), with each attempt succeeding with probability \\( \\varphi(N)/N = \\Omega(1/\\log \\log N) \\).[13](https://epubs.siam.org/doi/10.1137/S0036144598347011) • [17](https://www.cs.umd.edu/~amchilds/teaching/w13/l02.pdf) The QFT also underlies the [Abelian hidden subgroup problem](https://www.edgepedia.org/abelian-hidden-subgroup-problem), the HHL linear-systems algorithm, and quantum principal component analysis.[10](https://gilyen.hu/teaching/PCMI_2023_QFT_prez_day_1.pdf) • [3](https://link.springer.com/article/10.1007/s11128-026-05067-7)\n\n## Limitations and alternatives\n\nThe central limitation is readout: individual Fourier-transformed output amplitudes cannot be accessed by measurement, and reading an amplitude out directly would require exponentially many repetitions.[5](https://export.arxiv.org/pdf/quant-ph/0211030v1.pdf) • [11](https://dojo.qulacs.org/en/qp_main/notebooks/2.3_quantum_Fourier_transform.html) The \\( O(n^{2}) \\) versus \\( O(n \\cdot 2^{n}) \\) advantage rests on using phase information without measuring the state; any measurement extracts at most \\( n = \\log N \\) bits, so the QFT is not an exponential speedup of the classical FFT, which computes the transform in \\( O(N \\log N) \\) operations.[16](http://arxiv.org/pdf/1006.3989) • [20](https://people.eecs.berkeley.edu/~vazirani/f04quantum/notes/lec8.pdf) For basis-state input, a classical algorithm can generate a compact product-state description of the QFT output in \\( O(n) \\) time, though explicitly outputting all amplitudes takes at least \\( \\Omega(2^{n}) \\) time.[16](http://arxiv.org/pdf/1006.3989) In fault-tolerant settings, gate synthesis dominates cost; Goto found that ancilla-assisted gate synthesis outperforms state distillation for a fault-tolerant QFT.[21](https://journals.aps.org/pra/abstract/10.1103/PhysRevA.90.052318) Hardware demonstrations have grown rapidly: the semiclassical QFT was implemented on three beryllium ion qubits in a segmented multizone trap,[7](https://www.science.org/doi/10.1126/science.1110335) and Q-CTRL researchers later demonstrated a 100-qubit QFT on [IBM Quantum](https://www.edgepedia.org/ibm-quantum) computers. These results represent the largest experimental QFT on any quantum hardware to date by a factor of two.[22](https://q-ctrl.com/blog/breaking-the-100-qubit-barrier-executing-the-quantum-fourier-transform-at-scale-on-ibm-hardware)\n\nRecent work has targeted resource costs. A dynamic QFT using \\( O(n) \\) mid-circuit measurements replaces the \\( O(n^{2}) \\) two-qubit-gate circuit without connectivity constraints.[3](https://link.springer.com/article/10.1007/s11128-026-05067-7) A 2025 construction achieves depth \\( O(\\log(n/\\varepsilon)) \\) with no ancilla qubits, long-range gates, or measurements, where earlier log-depth circuits needed \\( O(n \\log n) \\) ancillas; applied to a QFT-based multiplier it yields a factoring algorithm with depth \\( O(n^{1+\\varepsilon}) \\) and \\( 2n + O(n/\\log n) \\) total qubits.[19](https://arxiv.org/html/2505.00701) Nam, Su, and Maslov estimated that about \\( 5.3 \\times 10^{4} \\) controlled rotation gates suffice to factor 2048-bit numbers with expected algorithmic accuracy of at least 99.992%.[8](https://doi.org/10.1038/s41534-020-0257-5)\n\n## References\n\n1. [Fast parallel circuits for the quantum Fourier transform (Cleve & Watrous)](https://ar5iv.labs.arxiv.org/html/quant-ph/0006004)\n2. [Quantum Fourier transform (Chapter 12), Quantum Algorithms: A Survey of Applications and End-to-end Complexities (Cambridge University Press, 2025)](https://www.cambridge.org/core/books/quantum-algorithms/quantum-fourier-transform/4F2B669EE1363DF9BBB83D66F05C6041)\n3. [A review on quantum Fourier transform (Quantum Information Processing, 2026)](https://link.springer.com/article/10.1007/s11128-026-05067-7)\n4. [Quantum Fourier Transform (BerkeleyX CS-191x, Chapter 5)](https://prod-edxapp.edx-cdn.org/assets/courseware/v1/8f101da9d14cfeec83df9e42a70562bf/c4x/BerkeleyX/CS-191x/asset/chap5.pdf)\n5. [Implementation of the quantum Fourier transform on NMR quantum computers](https://export.arxiv.org/pdf/quant-ph/0211030v1.pdf)\n6. [Quantum Computing (CST Part II), Lecture 9: Quantum Fourier Transform & Quantum Phase Estimation (University of Cambridge)](https://www.cl.cam.ac.uk/teaching/2324/QuantComp/Quantum_Computing_Lecture_9_2024.pdf)\n7. [Implementation of the Semiclassical Quantum Fourier Transform in a Scalable System](https://www.science.org/doi/10.1126/science.1110335)\n8. [Yunseong Nam, Yuan Su, Dmitri Maslov (2020). Approximate quantum Fourier transform with O(n log(n)) T gates. npj Quantum Information.](https://doi.org/10.1038/s41534-020-0257-5)\n9. [10.9 Quantum Fourier transform | Introduction to Quantum Information Science](https://qubit.guide/10.9-quantum-fourier-transform)\n10. [Quantum Fourier transform beyond Shor's algorithm (Gilyén, PCMI 2023, Day 1)](https://gilyen.hu/teaching/PCMI_2023_QFT_prez_day_1.pdf)\n11. [2-3. Quantum Fourier Transform (Qulacs Dojo)](https://dojo.qulacs.org/en/qp_main/notebooks/2.3_quantum_Fourier_transform.html)\n12. [AQI Lecture 1 (Module 4): Quantum Fourier Transform and Phase Estimation](https://quantumnanophotonics.org/wp-content/uploads/2023/07/module4lecture1.pdf)\n13. [Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (Shor)](https://epubs.siam.org/doi/10.1137/S0036144598347011)\n14. [Robert B. Griffiths, Chi-Sheng Niu (1996). Semiclassical Fourier Transform for Quantum Computation. Physical Review Letters.](https://doi.org/10.1103/physrevlett.76.3228)\n15. [Semiclassical Fourier Transform for Quantum Computation (Griffiths & Niu, preprint full text)](https://arxiv.org/pdf/quant-ph/9511007)\n16. [De-quantisation of the Quantum Fourier Transform](http://arxiv.org/pdf/1006.3989)\n17. [Quantum Fourier transform (lecture notes, UMD, Andrew Childs)](https://www.cs.umd.edu/~amchilds/teaching/w13/l02.pdf)\n18. [The quantum Fourier transform on a linear nearest neighbor architecture (Quantum Information & Computation)](https://www.rintonpress.com/xqic7/qic-7-4/383-391.pdf)\n19. [A log-depth in-place quantum Fourier transform that rarely needs ancillas (arXiv, 2025)](https://arxiv.org/html/2505.00701)\n20. [CS 294 Quantum Computing, Lecture 8: Quantum Fourier transform (Vazirani, Fall 2004)](https://people.eecs.berkeley.edu/~vazirani/f04quantum/notes/lec8.pdf)\n21. [Resource requirements for a fault-tolerant quantum Fourier transform (Goto, Phys. Rev. A 90, 052318, 2014)](https://journals.aps.org/pra/abstract/10.1103/PhysRevA.90.052318)\n22. [Breaking the 100-qubit barrier: Executing the Quantum Fourier Transform at scale on IBM hardware | Q-CTRL](https://q-ctrl.com/blog/breaking-the-100-qubit-barrier-executing-the-quantum-fourier-transform-at-scale-on-ibm-hardware)\n\n---\n*Topic: Encyclopedia › Technology and the built world › Computing and digital systems › Artificial intelligence and data › Algorithms and computational methods › Numerical, string, and geometric algorithms › Fourier and signal transforms*\n\n*Initially written Sep 29, 2026 · Edited: Oct 15, 2026; Oct 21, 2026*\n\n*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*\n\nLicense: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license\n", "same_as": [ "https://www.cs.umd.edu/~amchilds/teaching/w13/l02.pdf", "https://people.eecs.berkeley.edu/~vazirani/f04quantum/notes/lec8.pdf" ], "url": "https://www.edgepedia.org/quantum-fourier-transform", "markdown_url": "https://www.edgepedia.org/quantum-fourier-transform.md", "license": { "name": "Edgepedia Community License 1.0", "url": "https://www.edgepedia.org/edgepedia/license", "summary": "Free with credit, commercial use included. AI training is open to everyone. For other uses, organizations over USD 100M in revenue or 100M monthly users license separately.", "spdx": "LicenseRef-Edgepedia-Community-1.0" }, "credit": "\"Quantum Fourier transform\", Edgepedia (EdgeChat), https://www.edgepedia.org/quantum-fourier-transform. Edgepedia Community License 1.0.", "credit_md": "\"[Quantum Fourier transform](https://www.edgepedia.org/quantum-fourier-transform)\", Edgepedia (EdgeChat), [https://www.edgepedia.org/quantum-fourier-transform](https://www.edgepedia.org/quantum-fourier-transform). [Edgepedia Community License 1.0](https://www.edgepedia.org/edgepedia/license).", "credit_html": "\"Quantum Fourier transform\", Edgepedia (EdgeChat), https://www.edgepedia.org/quantum-fourier-transform. Edgepedia Community License 1.0.", "speakable": "The quantum Fourier transform is a quantum algorithm applying the discrete Fourier transform to a quantum state's amplitudes, used in Shor's algorithm and phase estimation." }