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

It’s been difficult to find important questions that quantum computers can answer faster than classical machines, but a new algorithm appears to do so for some critical optimization tasks.

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.

But all that came later. When the researchers behind DQI started working on their algorithm, they didn’t even have this problem in mind.

A Problem Decoded

“It would have been entirely plausible for a goal-oriented researcher to start by stating the problem and then investigating whether quantum algorithms could solve it faster than classical algorithms,” said Stephen Jordan, a physicist at Google Quantum AI and one of the main architects of DQI. “Of course, for us, that’s not how it happened. We came upon it by a backward and circuitous route.”

Stephen Jordan helped come up with a quantum approach to certain problems that 

works better than any classical approach—so far.

 

Jordan embarked on that route in 2023, when he joined Google and found out he’d be working with Eddie Farhi, a physicist at Google whose work has long focused on quantum algorithms that outperform classical ones. (Farhi was once Jordan’s doctoral adviser at the Massachusetts Institute of Technology.) Jordan knew that in 2014, Farhi had made a quantum attack on an optimization problem by thinking of energy, with lower energies corresponding to better solutions. For Farhi, energy connected optimization to quantum physics.

But Jordan wanted to do something different. He turned to another concept built into quantum physics—recognizing everything as waves. Using a mathematical tool called a quantum Fourier transform, Jordan found a way to translate all the potential answers to a well-known class of optimization problems into quantum waves. In doing so, he could manipulate the quantum system so that bigger waves (in the form of higher quantum amplitudes) corresponded to better solutions.

But there was still a huge challenge that had to be overcome. In a quantum system, asking “What’s the biggest amplitude?” is not as simple as recognizing the biggest wave at the beach. The quantum landscape is incredibly complex, and it was unclear how to identify the quantum amplitudes that would correspond to the best solutions.

After many false starts, Jordan made a breakthrough: The process of selecting the best solutions turned out to be similar to the process of weeding out errors in coded messages, which is known as decoding. This is a well-studied area of computer science, full of techniques that Jordan could explore. By translating an optimization problem into a quantum one, and then applying the decoding lens to it, he had stumbled into a new way to develop quantum algorithms.

Together with Noah Shutty, also at Google, Jordan began testing decoding schemes, seeing how they fared against classical algorithms on various optimization problems. They needed both the right approach and a problem where it worked. “It turns out classical algorithms are hard to beat,” Jordan said. “After a few months of trying, we still had not notched up any wins for quantum.”

But eventually, the pair landed on a decoding algorithm first introduced in the 1960s to find and fix individual errors in an encoded message. Finding that problem was the key. “When we investigated, we seemed to hit success almost immediately,” Jordan said. Finally, they had found a problem and an approach that, together, looked like a quantum speedup.

Of course, that didn’t mean it was bulletproof. “Maybe there is some classical method that can efficiently replicate your entire approach,” Jordan said. “Such dequantizations are not always obvious.”

Gaining Confidence

To assuage those fears, they consulted with Mary Wootters, a coding theory expert (and Shutty’s former doctoral adviser at Stanford University). She carefully searched for any known classical algorithm that might match their quantum speedup. The advantage held. The team’s checks likewise suggest that it will continue to hold. “They did due diligence,” Tang said.

Bolstered by this analysis, they looked more carefully at the optimization problem they were solving. Jordan had worried that it might be too niche, with no wider applications, but Shutty recognized that this decoding problem was a variation of well-known and useful problems in encryption and other fields.

Jordan acknowledges that without a large enough quantum machine, DQI will remain a theoretical breakthrough. “DQI cannot run on present-day quantum computers,” he said. But they’re still moving forward. Since the group posted their work last August, they have extended the application of DQI beyond the original problem to a broader class of optimization problems, which includes more cases of these “best path” problems.

So far, Jordan said, he expects that DQI can beat classical algorithms in those problems, too.

For the moment, the quantum community remains elated. “Finding quantum algorithms that show an advantage over classical algorithms is a very exciting endeavor of the last three decades, and the number of definite algorithms that show such an advantage is not large,” Kalai said. “Therefore, every new algorithm is a reason for celebration.”

Original story reprinted with permission from Quanta Magazine, an editorially independent publication of the Simons Foundation whose mission is to enhance public understanding of science by covering research developments and trends in mathematics and the physical and life sciences.

Source

Hope you enjoyed this news post.

Thank you for appreciating my time and effort posting news every day for many years.

News posts... 2023: 5,800+ | 2024: 5,700+ | 2025 (till end of March): 1,357

RIP Matrix | Farewell my friend