Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1005.3730 · Journal of Computational and Applied Mathematics

Obtaining the Quantum Fourier Transform from the classical FFT with QR decomposition

Franklin de Lima Marquezino, Renato Portugal, F. D. Sasse

Published May 22, 2010• 16 citations
arXivHTMLPDF
DOI
10.1016/j.cam.2010.05.012

Related papers

Quantum Fourier transform revisited

Daan Camps, Roel Van Beeumen, Chao Yang

Summary The fast Fourier transform (FFT) is one of the most successful numerical algorithms of the 20th century and has found numerous applications in many branches of computational science and engineering. The FFT algorithm can be derived from a particular matrix decomposition of the discrete Fourier transform (DFT) matrix. In this paper, we show that the quantum Fourier transform (QFT) can be derived by further decomposing the diagonal factors of the FFT matrix decomposition into products of matrices with Kronecker product structure. We analyze the implication of this Kronecker product structure on the discrete Fourier transform of rank‐1 tensors on a classical computer. We also explain why such a structure can take advantage of an important quantum computer feature that enables the QFT algorithm to attain an exponential speedup on a quantum computer over the FFT algorithm on a classical computer. Further, the connection between the matrix decomposition of the DFT matrix and a quantum circuit is made. We also discuss a natural extension of a radix‐2 QFT decomposition to a radix‐d QFT decomposition. No prior knowledge of quantum computing is required to understand what is presented in this paper. Yet, we believe this paper may help readers to gain some rudimentary understanding of the nature of quantum computing from a matrix computation point of view.

arXiv:2003.03011•Numerical Linear Algebra with Applications•Sep 15, 2020•57 citations

The Quantum Fourier Transform and Its Applications

WORLD SCIENTIFIC eBooks•Aug 27, 2026•0 citations

Coherent optical implementations of the fast Fourier transform and their comparison to the optical implementation of the quantum Fourier transform

Rupert C. D. Young, Philip M. Birch, Chris R. Chatwin

Optical structures to implement the discrete Fourier transform (DFT) and fast Fourier transform (FFT) algorithms for discretely sampled data sets are considered. In particular, the decomposition of the FFT algorithm into the basic Butterfly operations is described, as this allows the algorithm to be fully implemented by the successive coherent addition and subtraction of two wavefronts (the subtraction being performed after one has been appropriately phase shifted), so facilitating a simple and robust hardware implementation based on waveguided hybrid devices as employed in coherent optical detection modules. Further, a comparison is made to the optical structures proposed for the optical implementation of the quantum Fourier transform and they are shown to be very similar.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Apr 29, 2013•8 citations

Quantum Fourier transform in computational basis

S. S. Zhou, T. Loke, Josh Izaac +1 more

arXiv:1511.04818•Quantum Information Processing•Feb 10, 2017•72 citations

A Continuous-Variable Quantum Fourier Layer: Applications to Filtering and PDE Solving

Paolo Marcandelli, Stefano Mariani, Martina Siena +1 more

Fourier representations play a central role in operator learning methods for partial differential equations and are increasingly being explored in quantum machine learning architectures. The classical fast Fourier transform (FFT), particularly in its Cooley--Tukey decomposition, exhibits a structure that naturally matches continuous-variable quantum circuits. This correspondence establishes a direct structural isomorphism between the Cooley-Tukey butterfly network and Gaussian photonic gates, enabling the FFT to be realized as a native optical computation in continuous-variable quantum computing. Building on this observation, we introduce a continuous-variable Quantum Fourier Layer (CV--QFL) based on a bipartite Gaussian encoding and a Cooley-Tukey quantum Fourier transform, enabling exact two-dimensional spectral processing within a Gaussian photonic circuit. We test the CV--QFL on two representative tasks: spectral low-pass filtering and Fourier-domain integration of the heat equation. In both cases, the results match the classical reference to machine precision. Beyond these examples, our method naturally extends to optical-input settings in which the signal is already available as a Gaussian optical field. In such scenarios, coherent light coupled into single-mode waveguides can be processed directly by the CV--QFL, bypassing the need for an explicit classical-to-quantum encoding stage. This enables native spectral processing of light and lays the groundwork for new approaches to quantum scientific machine learning, in particular for future neural operator architectures within the CV framework.

quant-pharXiv:2603.17847•Algorithms•Mar 19, 2026•2 citations

The Quantum Fourier Transform

Marco O. Lanzagorta, Jeffrey K. Uhlmann

Synthesis lectures on quantum computing•Jan 1, 2008•3 citations
Summary The fast Fourier transform (FFT) is one of the most successful numerical algorithms of the 20th century and has found numerous applications in many branches of computational science and engineering. The FFT algorithm can be derived from a particular matrix decomposition of the discrete Fourier transform (DFT) matrix. In this paper, we show that the quantum Fourier transform (QFT) can be derived by further decomposing the diagonal factors of the FFT matrix decomposition into products of matrices with Kronecker product structure. We analyze the implication of this Kronecker product structure on the discrete Fourier transform of rank‐1 tensors on a classical computer. We also explain why such a structure can take advantage of an important quantum computer feature that enables the QFT algorithm to attain an exponential speedup on a quantum computer over the FFT algorithm on a classical computer. Further, the connection between the matrix decomposition of the DFT matrix and a quantum circuit is made. We also discuss a natural extension of a radix‐2 QFT decomposition to a radix‐d QFT decomposition. No prior knowledge of quantum computing is required to understand what is presented in this paper. Yet, we believe this paper may help readers to gain some rudimentary understanding of the nature of quantum computing from a matrix computation point of view.
Optical structures to implement the discrete Fourier transform (DFT) and fast Fourier transform (FFT) algorithms for discretely sampled data sets are considered. In particular, the decomposition of the FFT algorithm into the basic Butterfly operations is described, as this allows the algorithm to be fully implemented by the successive coherent addition and subtraction of two wavefronts (the subtraction being performed after one has been appropriately phase shifted), so facilitating a simple and robust hardware implementation based on waveguided hybrid devices as employed in coherent optical detection modules. Further, a comparison is made to the optical structures proposed for the optical implementation of the quantum Fourier transform and they are shown to be very similar.
Fourier representations play a central role in operator learning methods for partial differential equations and are increasingly being explored in quantum machine learning architectures. The classical fast Fourier transform (FFT), particularly in its Cooley--Tukey decomposition, exhibits a structure that naturally matches continuous-variable quantum circuits. This correspondence establishes a direct structural isomorphism between the Cooley-Tukey butterfly network and Gaussian photonic gates, enabling the FFT to be realized as a native optical computation in continuous-variable quantum computing. Building on this observation, we introduce a continuous-variable Quantum Fourier Layer (CV--QFL) based on a bipartite Gaussian encoding and a Cooley-Tukey quantum Fourier transform, enabling exact two-dimensional spectral processing within a Gaussian photonic circuit. We test the CV--QFL on two representative tasks: spectral low-pass filtering and Fourier-domain integration of the heat equation. In both cases, the results match the classical reference to machine precision. Beyond these examples, our method naturally extends to optical-input settings in which the signal is already available as a Gaussian optical field. In such scenarios, coherent light coupled into single-mode waveguides can be processed directly by the CV--QFL, bypassing the need for an explicit classical-to-quantum encoding stage. This enables native spectral processing of light and lays the groundwork for new approaches to quantum scientific machine learning, in particular for future neural operator architectures within the CV framework.