2015/11/30 by S. S. Zhou, T. Loke, J. A. Izaac +1 · 1 citation
Computer Science · Physics and Astronomy · #Circulant matrix #Complexity and Algorithms in Graphs #Discrete Fourier transform (general) #Discrete-time Fourier transform #Fourier transform #Quantum #Quantum Computing Algorithms and Architecture #Quantum Fourier transform #Quantum Information and Cryptography #Quantum algorithm #Quantum computer #Quantum error correction #Quantum phase estimation algorithm #quant-ph
paper · pdf · doi:10.1007/s11128-017-1515-0
published as Quantum Inf Process 16. (2017) 82 · revised discussion and reference mainly in section 4, minor changes in the result section, as well as corrected typos
arxiv created 2016/02/05 · openalex created_date 2016/06/24 · openalex publication_date 2017/02/10 · arxiv updated 2017/04/03 · openalex updated_date 2026/08/05
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-δ and desired precision ε. Its time complexity %O((log N)2log(N/δ)/ε)) depends polynomially on log(N), where N is the problem size, and linearly on log(1/δ) and 1/ε. We also discuss an application of potential practical importance, namely the simulation of circulant Hamiltonians.