Quantum circuit for the fast Fourier transform
- PDF / 1,106,547 Bytes
- 20 Pages / 439.37 x 666.142 pts Page_size
- 61 Downloads / 282 Views
Quantum circuit for the fast Fourier transform Ryo Asaka1 · Kazumitsu Sakai1
· Ryoko Yahagi1
Received: 7 November 2019 / Accepted: 17 July 2020 / Published online: 7 August 2020 © The Author(s) 2020
Abstract We propose an implementation of the algorithm for the fast Fourier transform (FFT) as a quantum circuit consisting of a combination of some quantum gates. In our implementation, a data sequence is expressed by a tensor product of vector spaces. Namely, our FFT is defined as a transformation of the tensor product of quantum states. It is essentially different from the so-called quantum Fourier transform (QFT) defined to be a linear transformation of the amplitudes for the superposition of quantum states. The quantum circuit for the FFT consists of several circuits for elementary arithmetic operations such as a quantum adder, subtractor and shift operations, which are implemented as effectively as possible. Namely, our circuit does not generate any garbage bits. The advantages of our method compared to the QFT are its high versatility, and data storage efficiency in terms, for instance, of the quantum image processing.
1 Introduction Quantum computing, which utilizes quantum entanglement and quantum superpositions inherent to quantum mechanics, is rapidly gaining ground to overcome the limitations of classical computing. Shor’s algorithm [1] solving the integer factorization problem in a polynomial time and Grover’s algorithm [2] making it possible to substantially speed up the search in unstructured databases1 are one of the best-known
1 In fact, an effective encoding method to convert classical data to quantum states [e.g., a quantum version
of random access memory (qRAM)] [3–5] is necessary to take advantage of quantum computing.
B
Kazumitsu Sakai [email protected] Ryo Asaka [email protected] Ryoko Yahagi [email protected]
1
Department of Physics, Tokyo University of Science, Kagurazaka 1-3, Shinjuku-ku, Tokyo 162-8601, Japan
123
277
Page 2 of 20
R. Asaka et al.
examples of the astounding properties of quantum computing (see [6], for example, for various applications of quantum computing). An implementation of the Fourier transform as a quantum circuit sometimes plays a crucial role on quantum computing. Indeed, the quantum Fourier transform (QFT) [7] is a key ingredient of many important quantum algorithms, including Shor’s factoring algorithm and the quantum phase estimation algorithm to estimate the eigenvalues of a unitary operator. Here, the QFT is the Fourier transform for the amplitudes of a quantum state: N −1 N −1 x j | j −→ X k |k , (1.1) j=0
k=0
where we set N = 2n , and the amplitudes {X k } are the classical discrete Fourier transform of the amplitudes {x j } Xk =
N −1
jk
WN x j ,
xj =
j=0
N −1 1 − jk WN X k , N
(1.2)
k=0
where W N := exp(−2πi/N ). Due to the superposition of the state (1.1) and quantum parallelism, the QFT can be implemented in a quantum circuit consisting of O(n 2 ) quantum gates, which is much more efficient than the fast Fourier tr
Data Loading...
