Quantum Computers Will Speed Up the Internet’s Most Important Algorithm

Illustration: Dan Page

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 FFT's importance to practically every data-processing application in the digital age explains why some researchers have begun exploring how quantum computing can run the FFT algorithm more efficiently still.

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. [So] it's important to figure out effective ways to be able to implement it."

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. Shor's algorithm scales up its factorization of numbers more efficiently and rapidly than any classical computer anyone could ever design. And at the heart of Shor's phenomenal quantum engine is a subroutine called-you guessed it-the quantum Fourier transform (QFT).

Here is where the terminology gets a little out of hand. There is the QFT at the center of Shor's algorithm, and then there is the QFFT-the quantum fast Fourier transform. They represent different computations that produce different results, although both are based on the same core mathematical concept, known as the discrete Fourier transform.

The QFT is poised to find technological applications first, though neither appears destined to become the new FFT. Instead, QFT and QFFT seem more likely to power a new generation of quantum applications.

The quantum circuit for QFFT is just one part of a much bigger puzzle that, once complete, will lay the foundation for future quantum algorithms, according to researchers at the Tokyo University of Science. The QFFT algorithm would process a single stream of data at the same speed as a classical FFT. However, the QFFT's strength comes not from processing a single stream of data on its own but rather multiple data streams at once. The quantum paradox that makes this possible, called superposition, allows a single group of quantum bits (qubits) to encode multiple states of information simultaneously. So, 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. They laid out their QFFT blueprints in a recent issue of the journal Quantum Information Processing.

QFFT and our arithmetic operations in the paper demonstrate their power only when used as subroutines in combination with other parts," says Ryo Asaka, a physics graduate student at Tokyo University of Science and lead author on the study.

Greg Kuperberg, a mathematician at the University of California, Davis, says the Japanese group's work provides a scaffolding for future quantum algorithms. However, he adds, it's not destined by itself to be a magical solution to anything. It's trundling out the equipment for somebody else's magic show."

It is also unclear how well the proposed QFFT would perform when running on a quantum computer under real-world constraints, says Imperial's Walmsley. But he suggested it might benefit from running on one kind of quantum computer versus another (for example, a magneto-optical trap versus nitrogen vacancies in diamond) and could eventually become a specialized coprocessor in a quantum-classical hybrid computing system.

University of Warsaw physicist Magdalena Stobiska, a main coordinator for the European Commission's AppQInfo project-which will train young researchers in quantum information processing starting in 2021-notes that one main topic involves developing new quantum algorithms such as the QFFT.

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

This article appears in the January 2021 print issue as A Quantum Speedup for the Fast Fourier Transform."