Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Academician O.B. Lupanov International Scientific Seminar "Discrete Mathematics and Its Applications"

Compexity bound for discrete modelling of quantum Fourier transform

S.V. Shalagin

Published Jan 1, 2022• 0 citations
Publisher

Abstract

A discrete model of a quantum mechanical system with N basis states defined using 2(N-1) parameters. It is shown that the estimate of the complexity of discrete modeling quantum Fourier transform based on the presented model has O(N) order of operations on the specified parameters.
DOI
10.20948/dms-2022-29

Related papers

Quantum Fourier transform

Alexander M. Dalzell, Sam McArdle, Mario Berta +10 more

This chapter covers the quantum Fourier transform, which is an essential quantum algorithmic primitive that efficiently applies a discrete Fourier transform to the amplitudes of a quantum state. It features prominently in quantum phase estimation and Shor’s algorithm for factoring and computing discrete logarithms.

Cambridge University Press eBooks•Apr 24, 2025•1 citation

A discrete quantum model of the harmonic oscillator

Natig M. Atakishiyev, Anatoliy U Klimyk, Kurt Bernardo Wolf

We construct a new model of the quantum oscillator, whose energy spectrum is equally-spaced and lower-bound, whereas the spectra of position and of momentum are a denumerable non-degenerate set of points in [− 1, 1] that depends on the deformation parameter q ∊ (0, 1). We provide its explicit wavefunctions, both in position and momentum representations, in terms of the discrete q -Hermite polynomials. We build a Hilbert space with a unique measure, where an analogue of the fractional Fourier transform is defined in order to govern the time evolution of this discrete oscillator. In the limit when q → 1 − , one recovers the ordinary quantum harmonic oscillator.

arXiv:0711.3089•Journal of Physics A Mathematical and Theoretical•Feb 12, 2008•20 citations

THEORETICAL FRAMEWORK AND ALGORITHMIC IMPLEMENTATION OF THE QUANTUM FOURIER TRANSFORM AND PHASE ESTIMATION

Medak Srinivas

The Quantum Fourier Transform (QFT)andQuantumPhaseEstimation (QPE)are twofundamental algorithmic frameworks in quantum computation, and they provide the mathematical basis of many exponential-speedup quan tum algorithms, such as Shor’s factoring algorithm and quantum simulation techniques. In this work we present a detailed theoretical and computational study of the Quantum Fourier Transform and its integration in the Quan tum Phase Estimation. The discussion begins with the linear algebraic structure of the Hilbert spaces, the unitary transformations, and the complex vector representations that enable quantum interference and superposition. The QFT is studied as the unitary transform of computational basis states in the amplitudes in the frequency domain by phase rotations and tensor-product decompositions. The efficient circuit implementation in terms of Hadamard and controlled phase gates of this transform is discussed. The advantage of the transform in terms of polynomial time complexity over the classical discrete Fourier transform in some quantum scenarios is discussed.The QFT is implemented and the Quantum Phase Estimation algorithm is proposed to obtain the eigenphase information of the unitary operators. In the report the mathematical representation of QPE is derived by using the controlled unitary evolution, the inverse Fourier transforms and the measurement theory in finite dimensional Hilbert spaces. We discuss the probabilistic interpretation of phase extraction in detail and the convergence properties of the bi nary phase approximation. We also discuss the relation of QPE to eigenvalue problems in quantum mechanics and its applications to Hamiltonian simulation, quantum chemistry, cryptography, and hidden subgroup prob lems.Implementation aspects of these algorithms are studied using quantum circuit representations and oracle based computation models. We also discuss error sensitivity, qubit precision requirements, decoherence limita tions and practical constraints of Noisy Intermediate-Scale Quantum (NISQ) hardware. The work synthesizes the mathematical foundations, computational complexity analysis and physical realizations of the QFT and the QPE, demonstrating how the Fourier-based quantum transformations provide the essential mechanism underlying modern quantum algorithmic speedups and scalable quantum information processing.

Iterative International Publishers eBooks•May 1, 2026•0 citations

A quantum search algorithm of two entangled registers to realize quantum discrete Fourier transform of signal processing

Chao-Yang Pang, Ben-Qiong Hu

The discrete Fourier transform (DFT) is the base of modern signal processing. 1-dimensional fast Fourier transform (ID FFT) and 2D FFT have time complexity O ( N log N ) and O ( N 2 log N ) respectively. Since 1965, there has been no more essential breakthrough for the design of fast DFT algorithm. DFT has two properties. One property is that DFT is energy conservation transform. The other property is that many DFT coefficients are close to zero. The basic idea of this paper is that the generalized Grover's iteration can perform the computation of DFT which acts on the entangled states to search the big DFT coefficients until these big coefficients contain nearly all energy. One-dimensional quantum DFT (ID QDFT) and two-dimensional quantum DFT (2D QDFT) are presented in this paper. The quantum algorithm for convolution estimation is also presented in this paper. Compared with FFT, ID and 2D QDFT have time complexity O(√ N ) and O ( N ) respectively. QDFT and quantum convolution demonstrate that quantum computation to process classical signal is possible.

Chinese Physics B•Sep 1, 2008•7 citations

Quantum Discrete Fourier Transform with Classical Output for Signal Processing

Chao-Yang Pang, Ben-Qiong Hu

Discrete Fourier transform (DFT) is the base of modern signal or information processing. 1-Dimensional fast Fourier transform (1D FFT) and 2D FFT have time complexity O(NlogN) and O(N^2logN) respectively. Quantum 1D and 2D DFT algorithms with classical output (1D QDFT and 2D QDFT) are presented in this paper. And quantum algorithm for convolution estimation is also presented in this paper. Compared with FFT, QDFT has two advantages at least. One of advantages is that 1D and 2D QDFT has time complexity O(sqrt(N)) and O(N) respectively. The other advantage is that QDFT can process very long signal sequence at a time. QDFT and quantum convolution demonstrate that quantum signal processing with classical output is possible.

arXiv:0706.2451•Jun 17, 2007•3 citations

Continuum quantum systems as limits of discrete quantum systems. IV. Affine canonical transforms

Laurence Barker

Affine canonical transforms, complex-order Fourier transforms, and their associated coherent states appear in two scenarios: finite-discrete and continuum. We examine the relationship between the two scenarios, making systematic use of inductive limits, which were developed in the preceding articles in this series.

Journal of Mathematical Physics•Mar 20, 2003•5 citations
We construct a new model of the quantum oscillator, whose energy spectrum is equally-spaced and lower-bound, whereas the spectra of position and of momentum are a denumerable non-degenerate set of points in [− 1, 1] that depends on the deformation parameter q ∊ (0, 1). We provide its explicit wavefunctions, both in position and momentum representations, in terms of the discrete q -Hermite polynomials. We build a Hilbert space with a unique measure, where an analogue of the fractional Fourier transform is defined in order to govern the time evolution of this discrete oscillator. In the limit when q → 1 − , one recovers the ordinary quantum harmonic oscillator.
The Quantum Fourier Transform (QFT)andQuantumPhaseEstimation (QPE)are twofundamental algorithmic frameworks in quantum computation, and they provide the mathematical basis of many exponential-speedup quan tum algorithms, such as Shor’s factoring algorithm and quantum simulation techniques. In this work we present a detailed theoretical and computational study of the Quantum Fourier Transform and its integration in the Quan tum Phase Estimation. The discussion begins with the linear algebraic structure of the Hilbert spaces, the unitary transformations, and the complex vector representations that enable quantum interference and superposition. The QFT is studied as the unitary transform of computational basis states in the amplitudes in the frequency domain by phase rotations and tensor-product decompositions. The efficient circuit implementation in terms of Hadamard and controlled phase gates of this transform is discussed. The advantage of the transform in terms of polynomial time complexity over the classical discrete Fourier transform in some quantum scenarios is discussed.The QFT is implemented and the Quantum Phase Estimation algorithm is proposed to obtain the eigenphase information of the unitary operators. In the report the mathematical representation of QPE is derived by using the controlled unitary evolution, the inverse Fourier transforms and the measurement theory in finite dimensional Hilbert spaces. We discuss the probabilistic interpretation of phase extraction in detail and the convergence properties of the bi nary phase approximation. We also discuss the relation of QPE to eigenvalue problems in quantum mechanics and its applications to Hamiltonian simulation, quantum chemistry, cryptography, and hidden subgroup prob lems.Implementation aspects of these algorithms are studied using quantum circuit representations and oracle based computation models. We also discuss error sensitivity, qubit precision requirements, decoherence limita tions and practical constraints of Noisy Intermediate-Scale Quantum (NISQ) hardware. The work synthesizes the mathematical foundations, computational complexity analysis and physical realizations of the QFT and the QPE, demonstrating how the Fourier-based quantum transformations provide the essential mechanism underlying modern quantum algorithmic speedups and scalable quantum information processing.
The discrete Fourier transform (DFT) is the base of modern signal processing. 1-dimensional fast Fourier transform (ID FFT) and 2D FFT have time complexity O ( N log N ) and O ( N 2 log N ) respectively. Since 1965, there has been no more essential breakthrough for the design of fast DFT algorithm. DFT has two properties. One property is that DFT is energy conservation transform. The other property is that many DFT coefficients are close to zero. The basic idea of this paper is that the generalized Grover's iteration can perform the computation of DFT which acts on the entangled states to search the big DFT coefficients until these big coefficients contain nearly all energy. One-dimensional quantum DFT (ID QDFT) and two-dimensional quantum DFT (2D QDFT) are presented in this paper. The quantum algorithm for convolution estimation is also presented in this paper. Compared with FFT, ID and 2D QDFT have time complexity O(√ N ) and O ( N ) respectively. QDFT and quantum convolution demonstrate that quantum computation to process classical signal is possible.
Discrete Fourier transform (DFT) is the base of modern signal or information processing. 1-Dimensional fast Fourier transform (1D FFT) and 2D FFT have time complexity O(NlogN) and O(N^2logN) respectively. Quantum 1D and 2D DFT algorithms with classical output (1D QDFT and 2D QDFT) are presented in this paper. And quantum algorithm for convolution estimation is also presented in this paper. Compared with FFT, QDFT has two advantages at least. One of advantages is that 1D and 2D QDFT has time complexity O(sqrt(N)) and O(N) respectively. The other advantage is that QDFT can process very long signal sequence at a time. QDFT and quantum convolution demonstrate that quantum signal processing with classical output is possible.