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

作者：Pang Chao Yang^*; Hu Ben Qiong

来源：Chinese Physics B, 2008, 17(9): 3220-3226.

• Grover's algorithm
• entangled state
• DFT
• QDFT

The discrete Fourier transform (DFT) is the base of modern signal processing. 1-dimensional fast Fourier transform (1D 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 cofficients contain nearly all energy. One-dimensional quantum DFT (1D 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, 1D and 2D QDFT have time complexity O(root N) and O(N) respectively. QDFT and quantum convolution demonstrate that quantum computation to process classical signal is possible.

• 出版日期2008-9
• 单位四川师范大学; 成都理工大学