A quantum search algorithm of two entangled registers to realize quantum discrete Fouriertransform
of signal processing |
| |
Authors: | Pang Chao-Yang and Hu Ben-Qiong |
| |
Institution: | College of Information Management, Chengdu University of
Technology, Chengdu 610059, China; Key Software Laboratory, Sichuan Normal University, Chengdu 610066, China;College of Mathematics and Software Science, Sichuan
Normal
University, Chengdu 610066, 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. |
| |
Keywords: | Grover's algorithm entangled
state DFT QDFT |
本文献已被 维普 等数据库收录! |
| 点击此处可从《中国物理 B》浏览原始摘要信息 |
| 点击此处可从《中国物理 B》下载免费的PDF全文 |
|