Learning quantum Hamiltonians at any temperature in polynomial time

Ainesh Bakshi; Allen Liu; Ankur Moitra; Ewin Tang

arxiv: 2310.02243 · v2 · submitted 2023-10-03 · 🪐 quant-ph · cs.DS· cs.LG

Learning quantum Hamiltonians at any temperature in polynomial time

Ainesh Bakshi , Allen Liu , Ankur Moitra , Ewin Tang This is my paper

Pith reviewed 2026-05-24 06:03 UTC · model grok-4.3

classification 🪐 quant-ph cs.DScs.LG

keywords quantum Hamiltonian learningGibbs statespolynomial-time algorithmssum-of-squaresthermal stateslocal Hamiltoniansquantum many-body physics

0 comments

The pith

A polynomial-time algorithm learns any local quantum Hamiltonian from polynomially many copies of its Gibbs state at any constant temperature.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that local quantum Hamiltonians can be learned efficiently in polynomial time from their thermal Gibbs states at any fixed positive inverse temperature. Earlier results either required exponential runtime or were restricted to high temperatures or special commuting cases. The approach relies on a new flat polynomial approximation to the exponential function and a correspondence that converts multivariate polynomials into nested commutators. This reformulation allows the problem to be solved via a low-degree sum-of-squares relaxation. A sympathetic reader would care because this removes the computational barrier to characterizing quantum systems from thermal data.

Core claim

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.

What carries the argument

A new flat polynomial approximation to the exponential function together with a translation between multi-variate scalar polynomials and nested commutators that casts the learning task as a polynomial system solvable by low-degree sum-of-squares.

If this is right

The algorithm runs in polynomial time for any constant β > 0.
Only polynomially many copies of the Gibbs state are needed.
The method applies to general local Hamiltonians on n qubits.
It achieves precision ε in the output.
This closes the gap left by prior exponential-time or restricted algorithms.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

This technique might extend to learning other properties of quantum thermal states beyond the Hamiltonian.
Experimental implementations could use this for efficient Hamiltonian tomography in quantum devices.
The polynomial approximation method could be adapted to related problems in quantum information like state preparation or simulation.
Further work might reduce the degree of the sum-of-squares or improve sample complexity.

Load-bearing premise

The new flat polynomial approximation to the exponential function and the translation to nested commutators allow the learning task to be cast as a polynomial system that low-degree sum-of-squares can solve accurately.

What would settle it

A specific local Hamiltonian on a small number of qubits at a constant temperature where running the sum-of-squares procedure fails to recover the Hamiltonian parameters to within ε.

read the original abstract

We study the problem of learning a local quantum Hamiltonian $H$ given copies of its Gibbs state $\rho = e^{-\beta H}/\textrm{tr}(e^{-\beta H})$ at a known inverse temperature $\beta>0$. Anshu, Arunachalam, Kuwahara, and Soleimanifar (arXiv:2004.07266) gave an algorithm to learn a Hamiltonian on $n$ qubits to precision $\epsilon$ 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 $\epsilon$ from polynomially many copies of the Gibbs state at any constant $\beta > 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Paper claims the first polynomial-time algorithm for learning local quantum Hamiltonians from Gibbs states at any constant beta, via new flat polynomial approximations to exp and a commutator translation for sum-of-squares.

read the letter

The paper claims to resolve the open problem of learning a local quantum Hamiltonian to precision epsilon from polynomially many copies of its Gibbs state at any fixed inverse temperature beta greater than zero. Earlier work gave an exponential-time algorithm that worked for any beta, plus polynomial-time results only for high temperature or commuting terms. The new result removes the exponential runtime barrier for the general constant-beta case. The main technical steps are a flat polynomial approximation to the exponential function and a translation that converts multivariate scalar polynomials into nested commutators. These let the authors cast the learning task as a polynomial system whose low-degree sum-of-squares relaxation recovers the Hamiltonian coefficients. If the approximation stays flat and the translation keeps the degree polynomial while controlling error, the overall runtime stays polynomial in n and 1/epsilon. The approach looks like a direct response to the computational gap left by prior results. The abstract states the tools suffice, and the stress-test finds no internal contradiction or load-bearing assumption that would break the polynomial scaling at fixed beta. The main soft spot is that the abstract supplies no derivation, explicit construction, or error analysis for the approximation and translation. Soundness cannot be checked without those details, so it remains possible that the degree grows or the error bounds fail to hold uniformly for all constant beta. No circularity appears in the argument, and the citations correctly identify the exponential-time baseline and the restricted positive cases. This paper is for researchers working on quantum learning theory and efficient algorithms for quantum statistical mechanics. Readers following Hamiltonian learning will want to examine the new tools even if they ultimately need revision. It deserves a serious referee because the target problem is well-known and the proposed solution is technically distinct enough to merit expert scrutiny. I would bring it to a reading group to walk through the approximation technique. I would cite the result once the details are verified. It should go to peer review.

Referee Report

0 major / 2 minor

Summary. The paper claims a polynomial-time algorithm to learn any local quantum Hamiltonian H on n qubits to additive precision ε, using only polynomially many copies of its Gibbs state ρ = e^{-βH}/Tr(e^{-βH}) at any fixed constant inverse temperature β > 0. This resolves the computational-efficiency gap left open by Anshu et al. (arXiv:2004.07266), which achieved sample efficiency but required exponential time; prior poly-time results were restricted to high temperature or commuting Hamiltonians. The central technical contribution is a new flat polynomial approximation to the exponential together with a translation from multivariate scalar polynomials to nested commutators, allowing the learning task to be cast as a low-degree polynomial system whose sum-of-squares relaxation recovers the Hamiltonian.

Significance. If the claimed approximation and translation are correct, the result is a substantial advance: it supplies the first poly-time algorithm for Hamiltonian learning at constant temperature, a problem of central importance in quantum many-body physics and quantum information. The new polynomial-approximation and commutator-translation tools are likely to be reusable in other quantum learning and simulation settings. The manuscript supplies explicit polynomial runtime and sample bounds together with a reduction to a standard SOS solver.

minor comments (2)

[Abstract] Abstract, paragraph on main technical contribution: the dependence of the polynomial degree on β and ε is not stated explicitly, making it harder for a reader to verify at a glance that the overall runtime remains polynomial for fixed β.
The manuscript would benefit from a short table or paragraph comparing the new runtime and sample complexity with the exponential-time algorithm of Anshu et al. and the high-temperature result of Haah et al.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript, their accurate summary of our results, and their recommendation of minor revision. The referee correctly identifies the resolution of the computational-efficiency gap left by prior work and highlights the new technical tools (flat polynomial approximation and commutator translation). No specific major comments or requested changes were provided in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained via new technical tools

full rationale

The paper's central derivation introduces a new flat polynomial approximation to the exponential function together with a translation from multivariate polynomials to nested commutators. These allow reformulating Hamiltonian learning as a polynomial system whose low-degree SOS relaxation yields the learner. No step reduces by construction to a fitted input, self-defined quantity, or load-bearing self-citation chain. The cited prior results (Anshu et al., Haah-Kothari-Tang) establish the problem statement and special cases but are not invoked to justify the new approximation or the SOS sufficiency argument for arbitrary constant β. The algorithm is therefore independent of its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the validity of a newly introduced flat polynomial approximation to the exponential and a correspondence between polynomials and nested commutators; these are presented as the main technical contributions rather than standard background results.

axioms (2)

domain assumption Low-degree sum-of-squares relaxations can accurately solve the formulated polynomial system for the Hamiltonian coefficients
Invoked to obtain the polynomial-time algorithm from the polynomial formulation.
ad hoc to paper A flat polynomial approximation to the exponential exists with the required approximation properties for the Gibbs state
Cited as the main technical contribution enabling the reduction.

pith-pipeline@v0.9.0 · 5821 in / 1296 out tokens · 28347 ms · 2026-05-24T06:03:48.644379+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

2 extracted references · 2 canonical work pages · 1 internal anchor

[1]

Quantum Computing in the NISQ era and beyond

1327 pp. ISBN : 9780511584398. DOI:10.1017/cbo9780511584398 (page 2). [Par00] Pablo A Parrilo. “Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization”. PhD thesis. California Institute of Technology, 2000 (page 17). [Pre18] John Preskill. “Quantum computing in the NISQ era and beyond”. In: Quantum 2 (Aug. 2018)...

work page internal anchor Pith review Pith/arXiv arXiv doi:10.1017/cbo9780511584398 2000
[2]

Relaxations and Exact Solutions to Quantum Max Cut via the Algebraic Structure of Swap Operators

arXiv:2101.01509 [cs.DS](pages 8, 44). [TT23] Ewin Tang and Kevin Tian.A CS guide to the quantum singular value transforma- tion. 2023. arXiv:2302.14324 [quant-ph](page 24). [WCEHK23] Adam Bene Watts, Anirban Chowdhury, Aidan Epperly, J William Helton, and Igor Klep. “Relaxations and Exact Solutions to Quantum Max Cut via the Algebraic Structure of Swap O...

work page doi:10.1103/physrevlett.112.190501 2023

[1] [1]

Quantum Computing in the NISQ era and beyond

1327 pp. ISBN : 9780511584398. DOI:10.1017/cbo9780511584398 (page 2). [Par00] Pablo A Parrilo. “Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization”. PhD thesis. California Institute of Technology, 2000 (page 17). [Pre18] John Preskill. “Quantum computing in the NISQ era and beyond”. In: Quantum 2 (Aug. 2018)...

work page internal anchor Pith review Pith/arXiv arXiv doi:10.1017/cbo9780511584398 2000

[2] [2]

Relaxations and Exact Solutions to Quantum Max Cut via the Algebraic Structure of Swap Operators

arXiv:2101.01509 [cs.DS](pages 8, 44). [TT23] Ewin Tang and Kevin Tian.A CS guide to the quantum singular value transforma- tion. 2023. arXiv:2302.14324 [quant-ph](page 24). [WCEHK23] Adam Bene Watts, Anirban Chowdhury, Aidan Epperly, J William Helton, and Igor Klep. “Relaxations and Exact Solutions to Quantum Max Cut via the Algebraic Structure of Swap O...

work page doi:10.1103/physrevlett.112.190501 2023