Obtaining the quantum Fourier transform from the classical FFT with QR decomposition

DOI10.1016/J.CAM.2010.05.012MaRDI QIDQ711225zbMATH OpenOpenAlexFDO

Authors F. L. Marquezino, F. D. Sasse, R. Portugal

Publication date 25 October 2010

Published in Journal of Computational and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1005.3730

zbMATH Keywords

quantum Fourier transformquantum computingquantum circuit design

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computational methods for problems pertaining to quantum theory (81-08) Numerical methods for discrete and fast Fourier transforms (65T50)

Abstract: We present the detailed process of converting the classical Fourier Transform algorithm into the quantum one by using QR decomposition. This provides an example of a technique for building quantum algorithms using classical ones. The Quantum Fourier Transform is one of the most important quantum subroutines known at present, used in most algorithms that have exponential speed up compared to the classical ones. We briefly review Fast Fourier Transform and then make explicit all the steps that led to the quantum formulation of the algorithm, generalizing Coppersmith's work.

Recommendations

• scientific article; zbMATH DE number 1406111
• Quantum fourier transform over symmetric groups
• EFFICIENT IMPLEMENTATIONS OF THE QUANTUM FOURIER TRANSFORM: AN EXPERIMENTAL PERSPECTIVE
• Quantum Fourier transform revisited.
• A decomposition of quantum Fourier transformation

Cites work

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 3750146 (Why is no real title available?)
• scientific article; zbMATH DE number 236854 (Why is no real title available?)
• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Note on the Calculation of Fourier Series
• Some improvements in practical Fourier analysis and their application to X-ray scattering from liquids

Cited in

(6)

• Paired quantum Fourier transform with \(\log_2N\) Hadamard gates
• scientific article; zbMATH DE number 5669860 (Why is no real title available?)
• A hybrid universal blind quantum computation
• Storing the Quantum Fourier Operator in the QuIDD Data Structure
• Quantum QR decomposition in the computational basis
• Quantum windowed Fourier transform and its application to quantum signal processing

This page was built for publication: Obtaining the quantum Fourier transform from the classical FFT with QR decomposition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q711225)