Original source (on modern site)
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."