Quantum Computers Will Speed Up the Fast Fourier Transform, the Internet’s Most Important Algorithm

(SpectrumIEEE) Some researchers have begun exploring how quantum computing can run the fast Fourier transform (FFT) algorithm more efficiently.
The fast Fourier transform (FFT) is the unsung digital workhorse of modern life. It’s a clever mathematical shortcut that makes possible the many signals in our device-connected world. Every minute of every video stream, for instance, entails computing some hundreds of FFTs.
“The fast Fourier transform is an important algorithm that’s had lots of applications in the classical world,” says Ian Walmsley, physicist at Imperial College London. “It also has many applications in the quantum domain.”
The first proposed killer app for quantum computers—finding a number’s prime factors—was discovered by mathematician Peter Shor at AT&T Bell Laboratories in 1994. At the heart of Shor’s phenomenal quantum engine is the quantum Fourier transform (QFT). There is the QFT at the center of Shor’s algorithm, and then there is the QFFT—the quantum fast Fourier transform.
The quantum circuit for QFFT is just one part of a much bigger puzzle that will lay the foundation for future quantum algorithms, according to researchers at the Tokyo University of Science. By representing multiple streams of data, the QFFT appears poised to deliver faster performance and to enable power-saving information processing.
The Tokyo researchers’ quantum-circuit design uses qubits efficiently without producing so-called garbage bits, which can interfere with quantum computations. One of their next big steps involves developing quantum random-access memory for preprocessing large amounts of data.
Greg Kuperberg, a mathematician at the University of California, Davis, says the Japanese group’s work provides a scaffolding for future quantum algorithms.
University of Warsaw physicist Magdalena Stobińska, is a main coordinator for the European Commission’s AppQInfo project. She said, “The real value of this work lies in proposing a different data encoding for computing the [FFT] on quantum hardware,” she says, “and showing that such out-of-box thinking can lead to new classes of quantum algorithms.”