A new type of quantum circuit that calculates the Fourier transform much faster, more versatile and more efficiently.
Scientists design a novel quantum circuit that calculates the fast Fourier transform, an indispensable tool in all areas of technology.
The Fourier transform is a mathematical operation that is essential for practically all areas of physics and technology. Although there is already an algorithm that calculates the Fourier transform in quantum computers, it is not versatile enough for many practical applications. In a recent study, scientists at Tokyo University of Science solved this problem by designing a novel quantum circuit that computes the Fourier transform much faster, more versatile, and more efficiently.
The Fourier transform is an important mathematical tool that breaks a function or a data set into its constituent frequencies, much like breaking a musical chord into a combination of its notes. It is used in one form or another in all areas of engineering, and accordingly algorithms have been developed to compute it efficiently – at least for traditional computers. But what about quantum computers?
Even though Quantum computing remains an enormous technical and intellectual challenge, it has the potential to accelerate many programs and algorithms immensely, provided that suitable quantum circuits are designed. In particular, the Fourier Transform already has a quantum version called a Quantum Fourier Transform (QFT), but its applicability is quite limited as its results cannot be used in subsequent quantum arithmetic operations.
To address this problem, a recently published study in Quantum information processingScientists at Tokyo University of Science developed a new quantum circuit that carries out the “quantum-fast Fourier transformation (QFFT)” and takes full advantage of the peculiarities of the quantum world. The idea for the study came to Mr. Ryo Asaka, a freshman master’s student and one of the study’s scientists, when he first learned about QFT and its limitations. He thought it 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 speeds things up a lot, when the input data meet certain basic conditions.
To design the quantum circuit for the QFFT, the scientists first had to develop 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 qubits, the basic unit of quantum information. Given that the increase in the number of qubits of quantum computers has been an uphill battle in recent years, the fact that this novel quantum circuit for the QFFT can use qubits efficiently is very promising.
Another advantage of their quantum circuit over traditional QFT is that their implementation takes advantage of a unique property of the quantum world to significantly increase the computing speed. Associate Professor Kazumitsu Sakai, who led the study, explains: “In quantum computing, we can process a large amount of information at the same time by exploiting a phenomenon known as ‘superposition of states’. In this way, we can convert a lot of data such as multiple images and sounds to the frequency domain at once. “ Processing speed is regularly cited as the main advantage of the quantum computer, and this novel QFFT circuit represents a step in the right direction.
Additionally, the QFFT circuit is much more versatile than the QFT, as Assistant Professor Ryoko Yahagi, who also participated in the study, notes: “One of the main advantages of QFFT is that it is applicable to any problem that can be solved with traditional FFT, such as filtering digital images in the medical field or analyzing sounds for technical applications.” With quantum computers (hopefully) around the corner, the results of this study will facilitate the adoption of quantum algorithms to solve the many engineering problems that rely on the FFT.
Reference: “Quantum circuit for the fast Fourier transformation” by Ryo Asaka, Kazumitsu Sakai and Ryoko Yahagi, August 7, 2020, Quantum information processing.
DOI: 10.1007 / s11128-020-02776-5
