Scientists Find a Fast Way to Describe Quantum Systems
After years of false starts, a team of computer scientists has found a way to efficiently deduce the Hamiltonian of a physical system at any constant temperature.
Introduction
Physicists have done a remarkable job explaining the chaos of the universe with well-behaved equations, but certain situations remain mysterious. Among these are collections of many tiny particles — they can be atoms, electrons, anything sufficiently small — that interact in surprising and complicated ways. These interactions give rise to exotic quantum phenomena including superconductivity (in which materials conduct electricity without losing energy), superfluidity (the frictionless flow of a fluid) and topological order (where particles interact according to a strict choreography).
Theoretically, there is a way to understand these various behaviors, a kind of super equation unique to each quantum system that can fully describe the system’s physical properties. Unfortunately, real-life systems are so complicated that it’s often impossible to write down this equation, called a Hamiltonian, ahead of time.
Instead, researchers have become experts at the inverse problem: If we can measure the properties of a given system, can we deduce its Hamiltonian?
This problem is known to be computationally difficult. Any algorithm that can take measurements of a system and return the specific Hamiltonian has always required too many measurements to be efficient. Or it takes too long to be practical.
But late last year, four co-authors from the Massachusetts Institute of Technology and the University of California, Berkeley shared a new algorithm that can spit out the Hamiltonian of any quantum system at any constant temperature. It’s efficient in both sample size and runtime, so it doesn’t require too many measurements, nor does it take too long to calculate. It’s the first time researchers have been able to quickly and accurately discern a given system’s Hamiltonian. This work was named best student paper by the Quantum Information Processing conference for its only student author, Allen Liu.
“This is a very exciting result,” said Anurag Anshu, a computer scientist at Harvard University who was not involved with the research. “They gave the first very important step in computational learning” of the Hamiltonian.
The new result is the fruit of several years’ worth of scientific labor. Prior research by Anshu and others got part of the way there. Those researchers developed an algorithm that could deduce a system’s Hamiltonian using a reasonable amount of sample data: The amount needed increased only as a polynomial function of the number of particles.
However, the approach was not computationally efficient — even though it didn’t require too much data, it still took too long to calculate to be practical. The next question was clear: “Is there any setting in which you could get something fast?” said Ewin Tang, a theoretical computer scientist at Berkeley and one of the new paper’s co-authors.
It turned out the answer was yes — Tang and others soon found an optimal algorithm for learning a system’s Hamiltonian that was polynomial in runtime. But again, there was a catch. The algorithm only worked for high-temperature settings, so it only partially resolved the open question.
“The caveat is that most of the exotic [quantum phenomena] operate at very low temperatures,” said Ainesh Bakshi, a computer scientist at MIT and a co-author of the new paper. “This is precisely where we did not have algorithms.”
All the existing techniques had failed to work for low temperatures, presenting a conceptual bottleneck. Researchers weren’t very hopeful they could get past it. A survey paper last year, co-authored by Anshu, conjectured that finding an efficient Hamiltonian-learning algorithm that worked even at low temperatures could be computationally hard — meaning it was about as hard as problems could get.
“You truly needed to do something new in order to solve the problem,” Bakshi said.
So that’s what the team behind the new paper ended up doing: They ported an optimization tool from mathematics into their field of quantum learning. First they reformulated the problem of calculating a system’s Hamiltonian into a family of polynomial equations. Now the goal was to prove that they could solve these equations reasonably quickly — which seemed like an equally hard goal. “In general, if I have an arbitrary polynomial system, I cannot hope to solve it efficiently,” Bakshi said. Even simple polynomial systems are just too hard.
But theoretical computer scientists are good at finding workarounds in such situations, by using what’s called a relaxation technique. This approach converts problems that are hard to optimize — they have too many solutions that appear right but aren’t valid everywhere — into simpler ones with a unique global solution. By approximating difficult problems via simpler ones, the relaxation technique helps find solutions closer to the true solution.
The relaxation technique is well known in the field of approximation algorithms, but it had never been tried in quantum learning. The co-authors spent most of their time proving that the approach would work, and that the relaxation technique could solve the Hamiltonian-learning problem in polynomial time.
Once they showed it was possible, the team quickly published their findings along with the new algorithm, thrilling the research community. “The paper is very interesting because the result is surprising,” said Alvaro Alhambra, a theoretical physicist at the Institute for Theoretical Physics in Spain. “It’s almost better than you would imagine.”
While we now have a quick and efficient way to calculate a system’s Hamiltonian at any constant temperature, there’s still room for improvement. For one thing, as temperatures drop, the new algorithm becomes slower and requires a larger sample size to effectively compute the Hamiltonian. Before they can apply this algorithm for potential experiments, physicists need it to be as lean as possible.
But that doesn’t make the new result any less exciting. “It’s still something that was very much out of the realm of what people could do previously,” said Sitan Chen, a computer scientist at Harvard.
And Ankur Moitra, a theoretical computer scientist at MIT and one of the authors of the new work, appreciates the symbolism of this result, since it’s part of a growing trend of interdisciplinary collaborations between physicists and computer scientists. “My dream is that there’s a dictionary between a lot of the results that we know in theoretical machine learning and versions of that for quantum learning,” he said. “That’s not to say that translating from one side of the dictionary to the other is easy, but it gives us a sense for what to expect and what to explore.”