Physicists Finally Find a Problem That Only Quantum Computers Can Do

Quantum computers are poised to become computational superpowers, but researchers have long sought a viable problem that confers a quantum advantage — something only a quantum computer can solve. Only then, they argue, will the technology finally be seen as essential.

They’ve been looking for decades. “Part of the reason it’s challenging is because classical computers are pretty good at a lot of the things they do,” said John Preskill, a theoretical physicist at the California Institute of Technology.

In 1994, Peter Shor discovered one possibility: a quantum algorithm for factoring large numbers. Shor’s algorithm is powerful and widely believed to beat all classical algorithms; when run on a quantum computer, it has the potential to break much of the internet’s security systems, which rely on the hardness of factoring large numbers. But as impressive as it is, the algorithm is relevant only to a narrow slice of research areas, and it’s possible that tomorrow someone will find an efficient way to factor large numbers on a classical machine, making Shor’s algorithm moot. Shor’s narrow applicability has led the research community to search for other use cases for quantum machines that might actually help make new scientific discoveries.

“We don’t want to build a computer just for a single task,” said Soonwon Choi, a physicist at the Massachusetts Institute of Technology. “Other than Shor’s algorithm, what else can we do with a quantum computer?”

As Preskill puts it, “We have to find those problems that are classically hard, but then we have to [show] that the quantum methods will really be efficient.”

A few times, researchers thought they’d done it, discovering quantum algorithms that could solve problems faster than anything a classical computer could do. But then someone — often the young researcher Ewin Tang — came up with clever new classical algorithms that could outperform the quantum ones.

Now, a team of physicists including Preskill may have found the best candidate yet for quantum advantage. By studying the energy of certain quantum systems, they discovered a specific and useful question that is easy for a quantum machine to answer, but still difficult for a classical one. “This is major progress on quantum algorithms theory,” said Sergey Bravyi, a theoretical physicist and computer scientist at IBM. “Their result is a quantum advantage for a problem with relevance to chemistry and material sciences.”

Researchers are also excited that the new work explores unexpected new areas of the physical sciences. “This new capability is qualitatively different [than Shor’s] and potentially opens up many new opportunities in the world of quantum algorithms,” said Choi.

John Preskill had long sought an example of quantum advantage, something quantum computers could do that regular, classical computers couldn’t.

The problem has to do with the properties of quantum systems (typically atoms) in various energy states. When the atoms jump between states, their properties change. They might emit a particular color of light, for example, or become magnetic. If we want to better predict the system’s properties at various energy states, it helps to understand the system when it’s in its least excited state, which scientists refer to as the ground state.

“A lot of chemists, material scientists and quantum physicists are working on finding ground states,” said Robert Huang, one of the new paper authors and a research scientist at Google Quantum AI. “It is known to be extremely hard.”

It’s so hard that after more than a century of work, researchers still haven’t found an effective computational approach to determining a system’s ground state from first principles. Nor does there appear to be any way for a quantum computer to do it. Scientists have concluded that finding a system’s ground state is hard for both classical and quantum computers.

But some physical systems exhibit a more complex energy landscape. When cooled, these complex systems are content to settle not in their ground state, but rather at a nearby low energy level, known as a local minimum energy level. (Part of the 2021 Nobel Prize in Physics was awarded for work in one such set of systems, known as spin glasses.) Researchers began to wonder if the question of determining a system’s local minimum energy level was also universally hard.

The answers started to emerge last year, when Chi-Fang (Anthony) Chen, another author of the recent paper, helped develop a new quantum algorithm that could simulate quantum thermodynamics (which studies the impact of heat, energy and work on a quantum system). “I think many people have [researched] the question about what the energy landscape looks like in quantum systems, but previously there was no tool to analyze it,” Huang said. Chen’s algorithm helped open a window into how these systems operate.

Upon seeing how powerful the new tool was, Huang and Leo Zhou, the fourth and final author of the new paper, used it to design a way for quantum computers to determine a system’s local minimum energy state, rather than chasing the ideal ground state — an approach that focused on just the kind of question quantum computing researchers were looking for. “Now we have a problem: finding a local amount of the energy, which is still hard classically, but which we can say is quantumly easy,” Preskill said. “So that puts us in the arena where we want to be for quantum advantage.”

Led by Preskill, the authors not only proved the power of their new approach for determining a system’s local minimum energy state — major progress in the field of quantum physics — but also proved that this was finally a problem where quantum computers could show their worth. “The problem of finding local minimum has quantum advantage,” Huang said.

And unlike previous candidates, this one probably won’t be dethroned by any new classical algorithms. “[It’s] unlikely to be dequantized,” said Choi. Preskill’s team made very plausible assumptions and took few logical leaps; if a classical algorithm can achieve the same results, it means physicists must be wrong about many other things. “That will be a shocking result,” Choi said. “I’ll be excited to see it, but it will be too shocking to believe.” The new work presents a tractable and promising candidate to demonstrate quantum advantage.

To be clear, the new result is still theoretical in nature. Demonstrating this new approach on an actual quantum computer is currently impossible. It will take time to build a machine that can thoroughly test the problem’s quantum advantage. So for Bravyi, the work is just beginning. “If you look what happened five years ago, we had only a few qubit quantum computers, and now we already have hundreds or even 1,000-qubit machines,” he said. “It’s very hard to predict what would happen in five or 10 years. It’s a very dynamic field.”