Quantum Fourier transform in computational basis

DOI10.1007/S11128-017-1515-0MaRDI QIDQ2412616zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 23 October 2017

Published in Quantum Information Processing (Search for Journal in Brave)

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

zbMATH Keywords

computational basis statecontrolled quantum gatesquantum algorithmquantum Fourier transform

Mathematics Subject Classification ID

Numerical methods for discrete and fast Fourier transforms (65T50) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

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 $1-delta$ and desired precision $epsilon$. Its time complexity %$$ depends polynomially on $log(N)$, where $N$ is the problem size, and linearly on $log(1/delta)$ and $1/epsilon$. We also discuss an application of potential practical importance, namely the simulation of circulant Hamiltonians.

Recommendations

• EFFICIENT IMPLEMENTATIONS OF THE QUANTUM FOURIER TRANSFORM: AN EXPERIMENTAL PERSPECTIVE
• Design of quantum Fourier transforms and quantum algorithms by using circulant Hamiltonians
• scientific article; zbMATH DE number 5320404
• Quantum Fourier transform revisited.

Cites work

• A logarithmic-depth quantum carry-lookahead adder
• A quantum multiply-accumulator
• scientific article; zbMATH DE number 2103524 (Why is no real title available?)
• scientific article; zbMATH DE number 3892457 (Why is no real title available?)
• Limitations on the simulation of non-sparse Hamiltonians
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum Algorithms for Some Hidden Shift Problems
• Quantum arithmetic with the quantum Fourier transform
• Quantum computation and quantum information. 10th anniversary edition
• Quantum random access memory
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Roundoff Error Analysis of the Fast Fourier Transform
• Worst and average case roundoff error analysis for FFT

Cited in

(31)

• Quantum arithmetic with the quantum Fourier transform
• Quantum windowed Fourier transform and its application to quantum signal processing
• Quantum mean centering for block-encoding-based quantum algorithm
• Quantum algorithms for anomaly detection using amplitude estimation
• Quantum-based feature selection for multiclassification problem in complex systems with edge computing
• Structural stability of the quantum Fourier transform
• Visualization of the quantum Fourier transform using a quantum computer simulator
• Quantum algorithms for typical hard problems: a perspective of cryptanalysis
• Quantum QR decomposition in the computational basis
• Quantum circuit for the fast Fourier transform
• Quantum kernel logistic regression based Newton method
• Quantum dimensionality reduction by linear discriminant analysis
• Simple scheme for realizing the general conditional phase shift gate and a simulation of quantum Fourier transform in circuit QED
• Storing the Quantum Fourier Operator in the QuIDD Data Structure
• scientific article; zbMATH DE number 5669860 (Why is no real title available?)
• scientific article; zbMATH DE number 5320404 (Why is no real title available?)
• EXACT QUANTUM FOURIER TRANSFORMS AND DISCRETE LOGARITHM ALGORITHMS
• Quantum fast Fourier transform using multilevel atoms
• Design of quantum Fourier transforms and quantum algorithms by using circulant Hamiltonians
• Quantum Fourier analysis
• EFFICIENT IMPLEMENTATIONS OF THE QUANTUM FOURIER TRANSFORM: AN EXPERIMENTAL PERSPECTIVE
• STABILITY OF THE QUANTUM FOURIER TRANSFORMATION ON THE ISING QUANTUM COMPUTER
• Implementing quantum Fourier transform using three qubits
• Quantum discriminative canonical correlation analysis
• Quantum algorithm for unsupervised anomaly detection
• Coping with decoherence: parallelizing the quantum Fourier transform
• Quantum generalized least squares method in system identification
• Integer numeric multiplication using quantum Fourier transform
• A quantum convolution and neighborhood pixel extraction scheme based on NEQR
• Exploiting OFDM method for quantum communication
• Entanglement in cyclic sign invariant quantum states

This page was built for publication: Quantum Fourier transform in computational basis

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