Quantum computers promise to outperform today's traditional computers in many areas of science, including chemistry, physics, and cryptography, but proving they will be superior has been challenging. The most well-known problem in which quantum computers are expected to have the edge, a trait physicists call "quantum advantage," involves factoring large numbers, a hard math problem that lies at the root of securing digital information.
In 1994, Caltech alumnus Peter Shor (BS '81), then at Bell Labs, developed a quantum algorithm that will easily factor a large number in just seconds, whereas this type of problem could take a classical computer millions of years. Ultimately, when quantum computers are ready and working-a goal that researchers say may still be a decade or more away-these machines will be able to quickly factor large numbers behind cryptography schemes.
But, besides Shor's algorithm, researchers have had a hard time coming up with problems where quantum computers will have a proven advantage. Now, reporting in a recent Nature Physics study , a Caltech-led team of researchers has identified a common physics problem that these futuristic machines would excel at solving. The problem has to do with simulating how materials cool down to their lowest-energy states.
"In nature, we can put a material in a refrigerator to cool it down to its lowest-energy state," says John Preskill , the Richard P. Feynman Professor of Theoretical Physics, the Allen V. C. Davis and Lenabelle Davis Leadership Chair of Caltech's Institute for Quantum Information and Matter (IQIM), and an Amazon Scholar at the AWS Center for Quantum Computing based at Caltech. "But modeling how this occurs is challenging for a quantum computer and even harder for a classical computer."
In the new study, the team formulated a quantum algorithm (a set of computer instructions) that can be used in theory to find low-energy states-what physicists call local minima-of any material. Their study theoretically proves that the algorithm will perform much better than its classical counterparts.
"This is a new way to test quantum advantage," says co-author Hsin-Yuan (Robert) Huang (PhD '24), a senior research scientist at Google Quantum AI who joined the Caltech faculty in early April as an assistant professor of theoretical physics. "There are a couple of other ways to test for quantum advantage besides Shor's algorithm, but it's not clear how practical they are. Here we have a test tailored to a broad family of physics fields that includes materials science, condensed matter physics, high-energy physics, and chemistry."
Researchers want to find the lowest-energy, or most stable, states of materials to make predictions about how the materials will behave. Chemists, for example, would use computers to calculate a molecule's local-minimum energy states when evaluating it for pharmaceutical applications. Computer models would be used to predict how the molecule will bind to its biological target, accelerating the drug-discovery process.
The very lowest-energy state of a material is called its ground state. When you cool down a material in a refrigerator, it will reach low-energy plateaus along the way, before it hits the ground state. "It's like hiking downhill and trying to find the lowest spot. You might stop at a flat plateau on the way down, a local minimum," Preskill says. "For classical computers, finding these local minima can be a really hard problem."
The classical computers "get stuck in what they think is a local minimum, but it's not," Huang explains. "It's as if the classical computer thinks it's as low as it can go and cannot go any further to find a true local minimum."
Quantum computers-which are based on bizarre properties of the subatomic world such as entanglement and superposition-are better at problems like this. As is the case with factoring prime numbers, they have the ability to test out options inaccessible to classical computers. "Quantum computers won't get stuck on these fictitious low-energy plateaus imagined by classical computers and can find ways to go further," Huang says. "They are better at navigating the energy landscape."
Zoom In to Image This illustration depicts a quantum computer (lower left) beating out a classical computer in solving a physics problem that involves finding a material's low-energy states, called local minima. Researchers want to find these lowest-energy, or stable, states of materials to make predictions about how the materials will behave. The problem is a difficult one for classical computers, but researchers at Caltech have developed a new quantum algorithm that could in theory readily solve the problem, giving it a proven advantage over classical counterparts. Credit: Chi-Yun (Claudia) Cheng
Co-author Chi-Fang (Anthony) Chen, a former graduate student working with Fernando Brandão , Bren Professor of Theoretical Physics at Caltech and director of applied science at AWS Center for Quantum Computing, had previously been developing quantum algorithms to speed up local minima queries for materials. In this new study, the team went a step further to tailor an algorithm in such a way to prove definitively that it works better than classical algorithms.
"This paper is about constructing a well-motivated class of physics problems where there is a quantum advantage," Preskill says. "Quantum computers aren't ready to use today, but this is an area where they will make better predictions."
The study titled " Local minima in quantum systems " was funded by the National Science Foundation, the Department of Energy's Office of Science, the Walter Burke Institute for Theoretical Physics, the AWS Center for Quantum Computing, and a Google PhD Fellowship. Other authors include Leo Zhou, a former Caltech postdoctoral scholar who is now an assistant professor of electrical and computer engineering at UCLA.
