Quantum Fourier Transform in Computational Basis
arXiv:1511.04818 · doi:10.1007/s11128-017-1515-0
Abstract
The conventional Quantum Fourier Transform, with exponential speedup compared to the classical Fast Fourier Transform, has played an important role in quantum computation as a vital part of many quantum algorithms (most prominently, the Shor's factoring algorithm). However, situations arise where it is not sufficient to encode the Fourier coefficients within the quantum amplitudes, for example in the implementation of control operations that depend on Fourier coefficients. In this paper, we detail a new quantum algorithm to encode the Fourier coefficients in the computational basis, with success probability and desired precision . Its time complexity % depends polynomially on , where is the problem size, and linearly on and . We also discuss an application of potential practical importance, namely the simulation of circulant Hamiltonians.
arXiv commentrevised discussion and reference mainly in section 4, minor changes in the result section, as well as corrected typos
References in corpus (15)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum algorithm for solving linear systems of equations
- Quantum support vector machine for big data classification
- Quantum Amplitude Amplification and Estimation
- Quantum fingerprinting
- Quantum Networks for Elementary Arithmetic Operations
- Polynomial-time quantum algorithm for the simulation of chemical dynamics
- Continuous-Time Quantum Walks: Models for Coherent Transport on Complex Networks
- Architectures for a quantum random access memory
- Fast quantum algorithm for numerical gradient estimation
- Efficient Quantum Walk on a Quantum Processor
- Pattern recognition on a quantum computer
- Quantum simulation of the single-particle Schrodinger equation
- Eigenvalue Estimation of Differential Operators
- Discretely-observable continuous time quantum walks on Möbius strips and other exotic structures in 3D integrated photonics
Cited by in corpus (11)
- Quantum Analog-Digital Conversion
- Asymptotic Quantum Algorithm for the Toeplitz Systems
- Quantum walk-based portfolio optimisation
- Combinatorial optimisation via highly efficient quantum walks
- Quantum algorithms for anomaly detection using amplitude estimation
- Quantum circuit for the fast Fourier transform
- Quantum Dimensionality Reduction by Linear Discriminant Analysis
- Quantum algorithm for Neighborhood Preserving Embedding
- Quantum mean centering for block-encoding-based quantum algorithm
- Quantum Algorithm for Unsupervised Anomaly Detection
- Everything You Always Wanted to Know About Quantum Circuits