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.
