1. Introduction

Quantum computing, quantum communication and quantum signal processing have been received great attention in recent years [1]–[3]. In 1994, Peter Shor at AT&T Labs-Research showed that integer factoring could be done in polynomial time on a quantum computer [4]. One of major applications of Shor's quantum factorization algorithm is to break RSA public key cryptosystems. Due to this success, it is very interesting to design quantum circuit to implement various computation algorithms of digital signal transforms. These transforms include discrete Fourier transform (DFT), discrete Hartley transform (DHT) and discrete cosine transform (DCT). So far, quantum DFT, DCT, fractional Walsh transform and wavelet transform circuits have been designed [4]–[7]. In this paper, we will also design a quantum circuit for DFT implementation. The main steps involved in the design are described as follows. First, the discrete Fourier transform matrix is decomposed into the product of several sparse unitary matrices using its fast computation flow graph. Second, each sparse matrix is implemented by elementary quantum gates and cascade them to obtain the final circuit. The details are described in the following sections.