中国物理B ›› 2008, Vol. 17 ›› Issue (9): 3220-3226.doi: 10.1088/1674-1056/17/9/013

• • 上一篇    下一篇

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

胡本琼1, 庞朝阳2   

  1. (1)College of Information Management, Chengdu University of Technology, Chengdu 610059, China; (2)Key Software Laboratory, Sichuan Normal University, Chengdu 610066, China;College of Mathematics and Software Science, Sichuan Normal University, Chengdu 610066, China
  • 收稿日期:2007-06-27 修回日期:2008-02-27 出版日期:2008-09-08 发布日期:2008-09-08
  • 基金资助:
    Project supported by Sichuan Normal University, China (Grant No 06lk002).

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)   

  1. a Key Software Laboratory, Sichuan Normal University, Chengdu 610066, China; b College of Mathematics and Software Science, Sichuan Normal University, Chengdu 610066, China; b College of Information Management, Chengdu University of Technology, Chengdu 610059, China
  • Received:2007-06-27 Revised:2008-02-27 Online:2008-09-08 Published:2008-09-08
  • Supported by:
    Project supported by Sichuan Normal University, China (Grant No 06lk002).

PDF (PC)

656

赞

摘要： 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.

关键词: Grover's algorithm, entangled state, DFT, QDFT

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. 

Key words: Grover's algorithm, entangled state, DFT, QDFT

中图分类号:  (Entanglement and quantum nonlocality)

  • 03.65.Ud
02.30.Uu (Integral transforms) 03.67.Lx (Quantum computation architectures and implementations) 03.67.Mn (Entanglement measures, witnesses, and other characterizations) 84.40.Ua (Telecommunications: signal transmission and processing; communication satellites)