Scientists at Tokyo University of Science have designed a novel quantum circuit that calculates the Fast Fourier Transform (FFT).
Although there already exists an algorithm that computes the Fourier Transform in Quantum Computers (the Quantum Fourier Transform – QFT), it is not versatile enough for many practical applications.
The new concept has been based on a variant of the standard Fourier transform called the Fast Fourier Transform, a classical algorithm in conventional computing that greatly speeds things up.
To design the quantum circuit for the Quantum Fast Fourier Transform (QFFT), the scientists had to first devise quantum arithmetic circuits to perform the basic operations of the FFT, such as addition, subtraction, and digit shifting. A notable advantage of their algorithm is that no “garbage bits” are generated; the calculation process does not waste any qubits, the basic unit of quantum information. Considering that increasing the number of qubits of quantum computers has been an uphill battle over the last few years, the fact that this novel quantum circuit for the QFFT can use qubits efficiently is very promising.
Another merit of their quantum circuit over the traditional QFT is that their implementation exploits a unique property of the quantum world to greatly increase computational speed.
One of the main advantages of the QFFT is that it is applicable to any problem that can be solved by the conventional FFT, such as the filtering of digital images in the medical field or analyzing sounds for engineering applications.
The study has been published in Quantum Information Processing.