Quantum Speedup Found for Huge Class of Hard Problems

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

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

Keep your files stored safely and securely with the SanDisk 2TB Extreme Portable SSD. With over 69,505 ratings and an impressive 4.6 out of 5 stars, this product has been purchased over 8K+ times in the past month. At only $129.99, this Amazon’s Choice product is a must-have for secure file storage.

Help keep private content private with the included password protection featuring 256-bit AES hardware encryption. Order now for just $129.99 on Amazon!

Help Power Techcratic’s Future – Scan To Support

If Techcratic’s content and insights have helped you, consider giving back by supporting the platform with crypto. Every contribution makes a difference, whether it’s for high-quality content, server maintenance, or future updates. Techcratic is constantly evolving, and your support helps drive that progress.

As a solo operator who wears all the hats, creating content, managing the tech, and running the site, your support allows me to stay focused on delivering valuable resources. Your support keeps everything running smoothly and enables me to continue creating the content you love. I’m deeply grateful for your support, it truly means the world to me! Thank you!