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

DOI10.1016/J.CAM.2010.05.012zbMATH Open1200.65117arXiv1005.3730OpenAlexW2054447881MaRDI QIDQ711225FDOQ711225

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)

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Title not available (Why is that?)
• Title not available (Why is that?)
• Some improvements in practical Fourier analysis and their application to X-ray scattering from liquids
• Note on the Calculation of Fourier Series

Cited In (6)

• Paired quantum Fourier transform with \(\log_2N\) Hadamard gates
• Title not available (Why is that?)
• 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)