 |
ML Newsnew | past | best | rss | submit | about |
| Learning quantum Hamiltonians at any temperature in polynomial time (arxiv.org) | |
| 1 point by westurner on May 18, 2024 | hide | past | pdf | 1 comment on HN | |
|
In plain words: Given copies of a quantum system's thermal state at a known temperature, this recovers the energy rules behind it by turning the task into solving polynomial equations. It runs in polynomial time at any fixed temperature, where the earlier general approach needed exponential time. AbstractWe study the problem of learning a local quantum Hamiltonian $H$ given copies of its Gibbs state $ρ= e^{-βH}/\textrm{tr}(e^{-βH})$ at a known inverse temperature $β>0$. Anshu, Arunachalam, Kuwahara, and Soleimanifar (arXiv:2004.07266) gave an algorithm to learn a Hamiltonian on $n$ qubits to precision $ε$ with only polynomially many copies of the Gibbs state, but which takes exponential time. Obtaining a computationally efficient algorithm has been a major open problem [Alhambra'22 (arXiv:2204.08349)], [Anshu, Arunachalam'22 (arXiv:2204.08349)], with prior work only resolving this in the limited cases of high temperature [Haah, Kothari, Tang'21 (arXiv:2108.04842)] or commuting terms [Anshu, Arunachalam, Kuwahara, Soleimanifar'21]. We fully resolve this problem, giving a polynomial time algorithm for learning $H$ to precision $ε$ from polynomially many copies of the Gibbs state at any constant $β> 0$. Our main technical contribution is a new flat polynomial approximation to the exponential function, and a translation between multi-variate scalar polynomials and nested commutators. This enables us to formulate Hamiltonian learning as a polynomial system. We then show that solving a low-degree sum-of-squares relaxation of this polynomial system suffices to accurately learn the Hamiltonian. | |
| add comment on HN |
> 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.