Proving Quantum Computers Have the Edge
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."
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.
In related work, David Hsieh, Caltech's Donald A. Glaser Professor of Physics, along with Gil Refael, the Taylor W. Lawrence Professor of Theoretical Physics, and their colleagues show how local minima can be experimentally accessed starting from the ground state. As a demonstration platform, they used a crystal of Ca2RuO4, whose ground state features electron spins that are aligned antiparallel from one lattice site to the next. By stimulating the crystal with an ultrashort burst of light lasting less than one picosecond, researchers were able to excite the material into a local-energy minimum in which the spins are aligned in a parallel fashion between sites. This parallel-aligned state persists well beyond microseconds, indicating that the system is stably trapped in the local minimum.
According to Preskill, "having a way to compute and experimentally access local minima by driving systems far from thermal equilibrium could be a way to transform quantum materials properties on demand."
The study titled "Time-hidden magnetic order in a multi-orbital Mott insulator" was published in Nature Physics and was funded by IQIM, an National Science Foundation Physics Frontiers Center; the Gordon and Betty Moore Foundation; the Simons Foundation; the Army Research Office; and a Caltech Postdoctoral Prize Fellowship. Other authors include Xinwei Li and Iliya Esin, former Caltech postdoctoral scholars who are now assistant professors of physics at the National University of Singapore, and Bar Ilan University, respectively; current graduate students Youngjoon Han and Yincheng Liu; former graduate students Honglie Ning (PhD '23), now a postdoc at MIT, and Jun-Yi Shan (PhD '22), now a postdoc at UC Berkeley); former postdoc Kyle Seyler, now an assistant professor at the University of Arizona); and former Caltech WAVE student Cora Barrett, now a graduate student at MIT.