The Fast Fourier Transform (FFT) is the neglected digital workhorse of modern life. This is a clever mathematical shortcut that makes many signals possible in our world of connected devices. For example, each minute of each video stream requires the calculation of several hundred FFTs. The importance of FFTs to virtually all data processing applications in the digital age is why some researchers have started to explore how quantum computing can trigger the FFT algorithm even more effectively.
“The rapid Fourier transform is an important algorithm that has found many applications in the classical world,” says Ian Walmsley, a physicist at Imperial College London. “It also has many uses in the quantum field. [Therefore] it is important to find effective ways to implement it. ”
The first proposed killer application for quantum computers – finding prime factors of a number – was discovered by mathematician Peter Shor of AT&T Bell Laboratories in 1994. Shor’s algorithm scales factorization of numbers over efficiently and faster than any conventional computer that could ever be designed. And at the heart of Shore’s phenomenal quantum engine is a subroutine called – you guessed it – the Fourier Quantum Transform (QFT).
This is where the terminology gets out of hand. At the center of Shor’s algorithm is QFFT, followed by QFFT, the quantum fast Fourier transform. These are different calculations that give different results, although both are based on the same basic mathematical concept known as the Discrete Fourier Transform.
QFFT is poised to be the first to find technology applications, although none are intended to be the new FFT. Instead, QFT and QFFT appear to be more likely to become the backbone of next-generation quantum applications.
The quantum circuit for QFFT is just one piece of a much larger puzzle that, when completed, will lay the groundwork for future quantum algorithms, according to researchers at Tokyo University of Science. The QFT algorithm will process a data stream at the same rate as the classic FFT. However, the power of QFFT is not in processing a single data stream separately, but in processing multiple data streams simultaneously. The quantum paradox that makes this possible, called superposition, allows a group of quantum bits (qubits) to encode multiple information states simultaneously. Thus, by presenting multiple data streams, QFFT seems to offer higher performance and energy savings in information processing.
The Tokyo researchers’ quantum circuit design efficiently uses qubits without producing so-called unwanted bits that can interfere with quantum computing. One of their next big steps in the development of quantum random access memory for preprocessing large amounts of data. They presented their QFFT plans in a recent issue of Quantum Information Processing magazine.
“QFFT and our arithmetic operations in the article only demonstrate their capabilities when used as subroutines in conjunction with other parts,” says Ryo Asaka, Ph.D. student in physics at Tokyo University of Science and author principal of the study.
Greg Kuperberg, a mathematician at the University of California at Davis, says the Japanese group’s work lays the foundation for future quantum algorithms. However, he adds, “It’s not meant to be a magic bullet to a problem. Take out the equipment for someone’s magic show.
It’s also unclear how well the proposed QFFT will perform when running on a quantum computer under real conditions, says Imperial’s Walmsley. But he suggested that it might be more profitable for him to work on one type of quantum computer rather than another (for example, a magneto-optical trap against nitrogen vacancies in a diamond) and that he could eventually become a specialized coprocessor in a classical-quantum hybrid computing system.
Magdalena Stobińska, a physicist at the University of Warsaw, chief coordinator of the European Commission’s AppQInfo project, which will train young researchers in quantum information processing from 2021, notes that one of the main topics is related to the development of new quantum algorithms such as QFFT.
“The real value of this work is to come up with a different data encoding for computation [FFT] on quantum hardware,” she says, “and to show that thinking outside the box can lead to new classes of quantum algorithms. “.