Unknown-structure Hamiltonian learning from Gibbs states at all temperatures
- Fields
- Topics
Problem
Can every bounded-degree local Hamiltonian with unknown interaction support be learned efficiently from copies of its Gibbs state at any fixed inverse temperature?
Fix constants \(k\) and \(g\). Let \(\mathcal P_{n,k}\) be the nonidentity \(n\)-qubit Pauli strings of weight at most \(k\), and consider
The nonzero Pauli terms are unknown, while \(\beta>0\) is known and fixed independently of \(n\). Can independent copies of \(\rho_\beta\) in Eq. (1) be used to output coefficients satisfying \(\max_P|\widehat a_P-a_P|\leq\varepsilon\) with probability at least \(2/3\), using \(\operatorname{poly}(n,1/\varepsilon)\) copies and classical time for every fixed \(\beta\)?
Source
This precise formulation is editor wording based on the unresolved direction and limitations documented in the cited primary literature [Narayanan25][Lewis26]; it is not presented as a verbatim conjecture of those authors.
Progress
Reports do not certify correctness or automatically change the problem's status. Progress policy.
With a supplied bounded-degree list of \(r\) Pauli terms, learning at every fixed temperature is possible. Narayanan’s Theorem 1.6 gives
\begin{equation} N=O\!\left(r^6(1/\varepsilon)^{O(\beta^2)} +\frac{\log r}{\beta^2\varepsilon^2}\right) \tag{2} \end{equation}copies and polynomial computational time for fixed locality, interaction degree, and \(\beta\). The supplied list is essential to this theorem; it is parameter learning rather than unknown-structure learning. [Narayanan25]
The displayed definitions, constraints, and target bounds are recorded in Eqs. (2).
For geometrically local Hamiltonians with a known interaction dictionary, Chen, Anshu, and Nguyen obtain the sharper lattice sample bound
\begin{equation} N=\widetilde O\!\left(\frac{e^{\operatorname{poly}(\beta)}}{\beta^2\varepsilon^2}\right)\log(n/\delta), \tag{3} \end{equation}where \(\delta\) is the failure probability and the tilde suppresses logarithmic factors. Their all-temperature results do not remove the supplied-structure assumption. [Chen25]
The displayed definitions, constraints, and target bounds are recorded in Eqs. (3).
Unknown-structure learning is now solved at sufficiently high temperature. Lewis, Tang, and Wright’s Theorem 5.18 proves, under the normalization above,
\begin{equation} \beta\leq\frac{1}{1000e^6(2kg+1)^8} \quad\Longrightarrow\quad N=O\!\left(\frac{\log(n/\delta)}{\beta^2\varepsilon^2}\right), \tag{4} \end{equation}with classical runtime \(O(n^k\operatorname{poly}(g)\log(n/\delta)/(\beta^2\varepsilon^2))\). Thus neither high-temperature structure learning nor all-temperature known-structure learning should be listed as open. [Lewis26]
The displayed definitions, constraints, and target bounds are recorded in Eqs. (4).
Section 1.4 of the 29 June 2026 preprint explicitly leaves all-temperature structure learning open. Supplying all \(O(n^k)\) candidate Pauli terms to [Narayanan25] does not immediately solve the problem: their candidate interaction graph no longer has bounded degree. [Narayanan25][Lewis26]
Comment
The unresolved conjunction is unknown interaction support, arbitrary fixed positive temperature, and polynomial resources. Constants and polynomial exponents may depend on \(k\), \(g\), and \(\beta\); this question does not demand efficient scaling as the temperature approaches zero with system size. Lewis, Tang, and Wright explicitly leave all-temperature Gibbs-state structure learning open in Section 1.4; no impossibility result is asserted here.
References
- [Narayanan25]
- S. Narayanan, "Improved algorithms for learning quantum Hamiltonians, via flat polynomials," in Proceedings of the Thirty Eighth Conference on Learning Theory, Proceedings of Machine Learning Research 291, 4360–4385 (2025). Proceedings;linkarXiv