While the Fourier transform - a mathematical operation that decomposes a function (often a function of time, or a signal) into its constituent frequencies - already has a quantum version called the quantum Fourier transform (QFT), its applicability is quite limited because its results cannot be used in subsequent quantum arithmetic operations. To address this, say the researchers, they developed a new quantum circuit that executes the "quantum fast Fourier transform (QFFT)" and fully benefits from the peculiarities of the quantum world.
The approach is based on a variant of the standard Fourier transform called the " fast Fourier transform " (FFT) - an indispensable algorithm in conventional computing that greatly speeds things up if the input data meets some basic conditions. To design the quantum circuit for the 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, say the researchers, 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, say the researchers, is that their implementation exploits a unique property of the quantum world to greatly increase computational speed.
"In quantum computing, we can process a large amount of information at the same time by taking advantage of a phenomenon known as 'superposition of states,'" says Associate Professor Kazumitsu Sakai, who led the study. "This allows us to convert a lot of data, such as multiple images and sounds, into the frequency domain in one go."
Processing speed is regularly cited as the main advantage of quantum