A New Quantum Algorithm Speeds Up Solving a Huge Class of Problems

The original version of this story appeared in Quanta Magazine.

For computer scientists, solving problems is a bit like mountaineering. First they must choose a problem to solve—akin to identifying a peak to climb—and then they must develop a strategy to solve it. Classical and quantum researchers compete using different strategies, with a healthy rivalry between the two. Quantum researchers report a fast way to solve a problem—often by scaling a peak that no one thought worth climbing—then classical teams race to see if they can find a better way.

This contest almost always ends as a virtual tie: When researchers think they’ve devised a quantum algorithm that works faster or better than anything else, classical researchers usually come up with one that equals it. Just last week, a purported quantum speedup, published in the journal Science, was met with immediate skepticism from two separate groups who showed how to perform similar calculations on classical machines.

But in a paper posted on the scientific preprint site arxiv.org last year, researchers described what looks like a quantum speedup that is both convincing and useful. The researchers described a new quantum algorithm that works faster than all known classical ones at finding good solutions to a wide class of optimization problems (which look for the best possible solution among an enormous number of choices).

So far, no classical algorithm has dethroned the new algorithm, known as decoded quantum interferometry (DQI). It’s “a breakthrough in quantum algorithms,” said Gil Kalai, a mathematician at Reichman University and a prominent skeptic of quantum computing. Reports of quantum algorithms get researchers excited, partly because they can illuminate new ideas about difficult problems, and partly because, for all the buzz around quantum machines, it’s not clear which problems will actually benefit from them. A quantum algorithm that outperforms all known classical ones on optimization tasks would represent a major step forward in harnessing the potential of quantum computers.

“I’m enthusiastic about it,” said Ronald de Wolf, a theoretical computer scientist at CWI, the national research institute for mathematics and computer science in the Netherlands, who was not involved with the new algorithm. But at the same time, he cautioned that it’s still quite possible researchers will eventually find a classical algorithm that does just as well. And due to the lack of quantum hardware, it’ll still be a while before they can test the new algorithm empirically.

The algorithm might inspire new work on the classical side, according to Ewin Tang, a computer scientist at the University of California, Berkeley, who came to prominence as a teenager by creating classical algorithms that match quantum ones. The new claims “are interesting enough that I would tell classical-algorithms people, ‘Hey, you should look at this paper and work on this problem,’” she said.

The Best Way Forward?

When classical and quantum algorithms compete, they often do so on the battlefield of optimization, a field focused on finding the best options for solving a thorny problem. Researchers typically focus on problems in which the number of possible solutions explodes as the problem gets bigger. What’s the best way for a delivery truck to visit 10 cities in three days? How should you pack the parcels in the back? Classical methods of solving these problems, which often involve churning through possible solutions in clever ways, quickly become untenable.

The specific optimization problem that DQI tackles is roughly this: You’re given a collection of points on a sheet of paper. You need to come up with a mathematical function that passes through these points. Specifically, your function has to be a polynomial—a combination of variables raised to whole-number exponents and multiplied by coefficients. But it can’t be too complicated, meaning the powers can’t get too high. This gives you a curved line that wiggles up and down as it moves across the page. Your job is to find the wiggly line that touches the most points.

Variations of this problem show up in various forms across computer science, especially in error coding and cryptography—fields focused on securely and accurately encoding data as it’s transmitted. The DQI researchers recognized, basically, that plotting a better line is akin to shifting a noisy encoded message closer to its accurate meaning.