Quantum Discrete Fourier Transform with Classical Output for Signal Processing

2007/06/17 by Chao-Yang Pang, Pang, Chao-Yang, Ben-Qiong Hu +1 · 1 citation
Computer Science · Physics and Astronomy · #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #quant-ph

paper · pdf · doi:10.48550/arxiv.0706.2451

11 pages, 1 figure

arxiv created 2007/06/17 · arxiv updated 2009/12/01

Abstract

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²logN) 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.

Citations

• Loading N-Dimensional Vector into Quantum Registers from Classical Memory with O(logN) Steps

Cited by

• Quantum Pattern Recognition of Classical Signal

Related

• Quantum Inverse Fast Fourier Transform
• Exact quantum Fourier transforms and discrete logarithm algorithms
• 3-Qubit Circular Quantum Convolution Computation using Fourier Transform with Illustrative Examples
• Generalized Quantum Signal Processing and Non-Linear Fourier Transform are equivalent
• Quantum spectral analysis: frequency in time, with applications to signal and image processing