**(Phys.org)** Scientists from Tokyo University of Science developed a new quantum circuit that executes the quantum fast Fourier transform (QFFT) and fully benefits from the peculiarities of the quantum world.

The Fourier transform is an important mathematical tool that decomposes a function or dataset into a its constituent frequencies, much like one could decompose a musical chord into a combination of its notes. It is used across all fields of engineering in some form or another and, accordingly, algorithms to compute it efficiently have been developed—that is, at least for conventional computers. But what about quantum computers?

The idea for the study came to Mr. Ryo Asaka, first-year Master’s student and one of the scientists on the study, when he first learned about the QFT and its limitations. He thought it would be useful to create a better alternative 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.

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. 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.

With quantum computers (hopefully) right around the corner, the outcomes of this study will make it easier to adopt quantum algorithms to solve the many engineering problems that rely on the FFT.