The Fast Fourier Transform or FFT algorithm is an algorithm commonly used since the 1970s in signal processing and telecommunications.
Efficient in digital signal processing, from compression to transmission, the FFT algorithm also provided the basis for the development of transform compression techniques, like the JPEG format for images.
Basically, every type of digital data, like images, videos, sound, and radio signals, pass through the FFT algorithm, which makes the backbone of information technology.
However, the FFT method just can’t keep up with the explosive development of Big Data, too slow for applications demanding faster processing of digital data.
Quantum FFT Algorithm
Physicists at the University of Warsaw in Poland have collaborated with researchers from the University of Oxford and the U.S. NIST to show that quantum interference can enable constant-time processing of quantum information.
Scientists have been working for years on the development of alternatives to the standard methods, and they have come up with Quantum Fourier Transforms, the quantum counterpart of the conventional FFT.
As researchers explain, one of the many mathematically-possible transforms is the Kravchuk transform. Like the FFT, the Kravchuk transform “allows processing of discrete (e.g. digital) data, but uses Kravchuk functions to decompose the input sequence into the spectrum.”
Decades ago, scientists found that the Kravchuk transform is perfect for the processing of noisy data, which makes it ideal for application in autonomous vehicles and computer vision for robots.
However, there’s no computational algorithm to handle this transform fast enough, and this is what the team at the University of Warsaw’s Faculty of Physics have accomplished. They demonstrated that quantum mechanics, via quantum interference, could bridge this gap.
According to the researchers, “the simplest quantum gate, which interferes between two quantum states, essentially computes the Kravchuk transform. Such a gate could be a well-known optical device—a beam splitter, which divides photons between two outputs.”
It was real teamwork that led to the creation and validation of this concept for quantum FFT algorithm.
The University of Warsaw physicists devised the experiment, which they then performed and took place in a quantum optical laboratory at the University of Oxford. They used NIST’s Transmission Edge Sensors, which can count photons and can function at near-absolute zero temperatures.
The detailed results of the study are published in Science Advances journal.
Comments (0)
Most Recent