A quantum search algorithm of two entangled registers to realize quantum discrete Fouriertransform of signal processing
Pang Chao-Yang(庞朝阳)a)b)† and Hu Ben-Qiong(胡本琼)c)
aKey Software Laboratory, Sichuan Normal University, Chengdu 610066, China; bCollege of Mathematics and Software Science, Sichuan Normal University, Chengdu 610066, China; bCollege of Information Management, Chengdu University of Technology, Chengdu 610059, China
Abstract 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 coefficients 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(\sqrt{N})$ and $O(N)$ respectively. QDFT and quantum convolution demonstrate that quantum computation to process classical signal is possible.
Received: 27 June 2007
Revised: 27 February 2008
Accepted manuscript online:
(Telecommunications: signal transmission and processing; communication satellites)
Fund: Project supported
by Sichuan Normal University, China (Grant No
06lk002).
Cite this article:
Pang Chao-Yang(庞朝阳) and Hu Ben-Qiong(胡本琼) A quantum search algorithm of two entangled registers to realize quantum discrete Fouriertransform of signal processing 2008 Chin. Phys. B 17 3220
Altmetric calculates a score based on the online attention an article receives. Each coloured thread in the circle represents a different type of online attention. The number in the centre is the Altmetric score. Social media and mainstream news media are the main sources that calculate the score. Reference managers such as Mendeley are also tracked but do not contribute to the score. Older articles often score higher because they have had more time to get noticed. To account for this, Altmetric has included the context data for other articles of a similar age.
