Sample-efficient learning of quantum many-body systems

Anurag Anshu; Srinivasan Arunachalam; Tomotaka Kuwahara; Mehdi Soleimanifar

Source-linked AI summary

Sample-efficient learning of quantum many-body systems

Anurag Anshu, Srinivasan Arunachalam, Tomotaka Kuwahara, Mehdi Soleimanifar

arXiv:2004.07266v1Apr 15, 2020quant-phcond-mat.stat-mechcs.LGmath.OC

TL;DR

The paper asks whether a quantum many-body Hamiltonian can be learned efficiently from samples of its Gibbs state, extending classical graphical-model learning. It uses maximum entropy estimation together with strong convexity analysis, obtaining unconditional polynomial sample complexity for spatially local Hamiltonians and developing a variance bound for quasi-local operators. The approach has computational and quantitative-bound limitations, including partition-function approximation that is NP-hard and bounds not yet independent of system size.

Problem
Quantum Hamiltonian learning asks whether Hamiltonian parameters can be learned efficiently from copies of a Gibbs state, extending the classical graphical-model problem.
Method
The paper combines maximum entropy estimation with strong convexity analysis and a lower bound on variances of quasi-local operators, without relying on the quantum Markov property.
Results
For spatially local Hamiltonians, the paper gives the first unconditional rigorous upper bound with sample complexity polynomial in the number of qudits.
Takeaways & Limitations
The result supports rigorous use of machine-learning and optimization ideas for quantum many-body Hamiltonian learning.
Takeaways & Limitations
The approach requires approximating the partition function, which is NP-hard, while the variance lower bound is not yet constant independent of system size.

Abstract

from arXiv · show

We study the problem of learning the Hamiltonian of a quantum many-body system given samples from its Gibbs (thermal) state. The classical analog of this problem, known as learning graphical models or Boltzmann machines, is a well-studied question in machine learning and statistics. In this work, we give the first sample-efficient algorithm for the quantum Hamiltonian learning problem. In particular, we prove that polynomially many samples in the number of particles (qudits) are necessary and sufficient for learning the parameters of a spatially local Hamiltonian in l_2-norm. Our main contribution is in establishing the strong convexity of the log-partition function of quantum many-body systems, which along with the maximum entropy estimation yields our sample-efficient algorithm. Classically, the strong convexity for partition functions follows from the Markov property of Gibbs distributions. This is, however, known to be violated in its exact form in the quantum case. We introduce several new ideas to obtain an unconditional result that avoids relying on the Markov property of quantum systems, at the cost of a slightly weaker bound. In particular, we prove a lower bound on the variance of quasi-local operators with respect to the Gibbs state, which might be of independent interest. Our work paves the way toward a more rigorous application of machine learning techniques to quantum many-body problems.

1 Introduction

The paper formulates quantum Hamiltonian learning from Gibbs-state samples and establishes a rigorous, polynomial-sample approach based on maximum entropy estimation.

Motivation: The problem extends classical graphical-model and Boltzmann-machine learning to quantum many-body systems with exponentially large state spaces.Classical Ising models have efficient provable learning algorithms, motivating the quantum analogue.
Problem formulation: Quantum Hamiltonian learning seeks to recover local interaction coefficients from multiple copies of a many-body system's Gibbs state.The setup allows arbitrary local measurements and access to all κ-local marginals.
Physics perspective: Hamiltonian learning can estimate effective interactions in complicated systems, including highly entangled finite-temperature Gibbs states.The stated physics motivation includes approximating interactions relevant to systems such as high-temperature superconductors.
Verification of quantum devices: The result also connects Hamiltonian learning to quantum-device verification, where Gibbs-state preparation and measurement are relevant to certifying noisy quantum computers.The introduction identifies quantum Gibbs sampling as a widely used subroutine in quantum algorithms.
Contribution: The paper rigorously obtains a sample complexity polynomial in the number of qudits using statistical and machine-learning tools such as maximum entropy estimation.The authors describe this as the first unconditional non-trivial sample-complexity result for the Hamiltonian Learning Problem.

2 Main result

The paper formalizes Hamiltonian learning from Gibbs-state copies and gives a sample-efficient algorithm for estimating spatially local Hamiltonian parameters in l_2-norm. Its guarantees are polynomial in system size, while sample requirements worsen near infinite and zero temperature; a lower bound shows near-tightness up to polynomial factors.

Problem: The Hamiltonian Learning Problem estimates local interaction coefficients from copies of a Gibbs state at fixed inverse temperature.The Hamiltonian is κ-local, acts on n qudits, and contains m local terms; the estimate must achieve prescribed l_2 error with probability at least 1−δ.
Algorithm and guarantee: The paper’s main result is a sample-efficient algorithm for the Hamiltonian Learning Problem.
Algorithm and guarantee: For spatially local Hamiltonians, the theorem yields sample complexity polynomial in the number of qudits because m=O(n).The constants in the Gibbs-state sample bound depend on the geometry of the Hamiltonian.
Temperature dependence: The number of required samples increases as β approaches either 0 or infinity, because the Gibbs state becomes less informative for distinguishing parameters.At β→0 the state approaches the maximally mixed state, while at β→∞ it approaches the ground space.
Lower bound: An Ω(√m) lower bound for l_2 Hamiltonian learning shows that the upper bound is tight up to polynomial factors.The lower bound follows from a reduction to state discrimination.

3 Proof overview

The proof combines quantum maximum-entropy estimation with a strong-convexity bound for the log-partition function, converting marginal estimation error into Hamiltonian-parameter error. To establish strong convexity without the quantum Markov property, it relates Hessian quadratic forms to variances of quasi-local operators and proves local variance lower bounds.

3.1 Maximum entropy estimation and sufficient statistics: Maximum-entropy estimation uses local Gibbs-state marginals as sufficient statistics, recovering the Hamiltonian parameters when the marginals match.The empirical program replaces exact marginals with estimates obtained from finitely many samples.
3.2 Strong convexity: Strong convexity of the log-partition function is the main technical contribution and supplies the curvature needed for robust parameter estimation.The Hessian lower bound is established uniformly for local Hamiltonians under the stated coefficient and temperature conditions.
3.2 Strong convexity: Strong convexity bounds the difference between the empirical and exact optimization solutions when each estimated marginal has error at most δ.This connects statistical errors in local observables to errors in the learned coefficients.
3 Proof overview: The resulting sample-complexity bound is within polynomial factors of the Ω(√m) lower bound, and becomes polynomial in the number of qudits for spatially local Hamiltonians.For spatial locality, the number of interaction terms satisfies m = O(n).
3.4.1 Relating the Hessian to a variance: The quantum Hessian cannot generally be expressed through ordinary covariance because the local Hamiltonian terms may not commute.The proof instead lower-bounds each Hessian quadratic form by the variance of a suitably defined quasi-local operator.
3.4.2 Lower bounding the variance: Local-unitary reductions and a local variance lower bound yield the global variance estimate needed for strong convexity, without assuming the quantum Markov property.The construction combines invariance under constant-size local unitaries with a unitary-supported-on-O(1)-sites variance bound.

4 Further discussions

The discussion situates the quantum Hamiltonian learning problem relative to shadow tomography and classical graphical-model learning, while identifying computational efficiency and sharper bounds as open challenges.

4.1 Connection to previous work: Shadow tomography estimates local state marginals, whereas Hamiltonian learning estimates the underlying coefficients; spatial locality therefore permits measuring only local observables.The paper uses a variant of shadow-tomography methods to estimate local Gibbs-state expectations, but does not require the full machinery for non-local observables.
4.1 Connection to previous work: For spatially local Hamiltonians, the paper achieves polynomially many samples in n for l_2 estimation, but cannot match classical O(log n) sample complexity for l_∞ estimation.The gap reflects both the node-wise structure of classical convex programs and strong-convexity arguments based on the classical Markov property.
4.2 Open questions: The maximum-entropy approach reduces the learning analysis to sufficient statistics, but approximating the partition function is NP-hard and can make the method computationally inefficient.The paper therefore focuses on sample complexity rather than an efficient running-time guarantee.
4.2 Open questions: The variance lower bound is proved for constant inverse temperature, while stronger bounds under decay-of-correlation assumptions and improved results for commuting Hamiltonians remain open.The authors specifically seek bounds independent of system size and expect commuting Hamiltonians to admit constant lower bounds.
4.2 Open questions: Combining efficient partition-function algorithms with maximum-entropy estimation, or using calibrated quantum devices, may yield efficient Hamiltonian-learning algorithms.These are proposed approaches rather than results established in this work.
4.2 Open questions: The paper identifies refined objective functions as a future direction because non-commutativity complicates matching the performance of classical learning algorithms.The authors connect this challenge to the information-theoretic properties of quantum Gibbs states.

5 Preliminaries

This section defines geometrically local Hamiltonians, Gibbs states, operator locality, and the sufficient-statistics structure underlying Hamiltonian learning. It also introduces quantum belief propagation and the estimation-to-sample-complexity reduction.

Preliminaries: A geometrically local Hamiltonian is built from interaction terms acting on constant-size neighborhoods of a lattice, yielding m = O(n) interaction parameters.The canonical representation uses Hermitian basis operators, such as tensor products of at most κ Pauli operators for qubits.
Preliminaries: Quasi-local operators generalize local operators by allowing tails beyond a region, while Lieb–Robinson bounds provide the locality control used in their analysis.The paper reserves quasi-local notation for operators with constant decay parameters and uses geometrically local Hamiltonians throughout.
Preliminaries: The maximum-entropy formulation uses local marginals as sufficient statistics for recovering the Hamiltonian from Gibbs-state samples.The marginal estimates are inserted into an empirical optimization problem because exact expectations are unavailable from finitely many samples.
Preliminaries: Matching all κ-local Gibbs-state marginals uniquely determines the Gibbs state and therefore all Hamiltonian coefficients.The proof uses relative-entropy positivity and orthogonality of the operator basis; approximate marginal matching yields a corresponding state-distance bound.
Preliminaries: Quantum belief propagation handles derivatives of Gibbs states when perturbations do not commute with the Hamiltonian.This framework supplies the derivative relation needed for the paper’s non-commutative Hessian analysis.
Preliminaries: Strong convexity converts marginal-estimation error into parameter error and, via concentration, into a sufficient sample-complexity bound.Theorem 26 bounds coefficient error under strong convexity, while Corollary 27 gives the resulting number of Gibbs-state copies.

6 Strong convexity of log Zβ(λ) log Zβ(λ) log Zβ(λ)

The paper proves that log Zβ(λ) is strongly convex for spatially local quantum Hamiltonians by expressing its Hessian through quantum belief propagation and lower-bounding it with quasi-local variance.

6 Strong convexity of log Zβ(λ) log Zβ(λ) log Zβ(λ): Quantum belief propagation expresses the derivatives of log Zβ through non-commuting operator dynamics, producing a symmetric real Hessian.The Hessian is subsequently related to a suitable quasi-local operator whose variance can be lower-bounded.
6 Strong convexity of log Zβ(λ) log Zβ(λ) log Zβ(λ): For every vector v, the Hessian of log Zβ(λ) is bounded below as vT∇2log Zβ(µ)v ≥ βc′e^−O(βc)/m · ||v||2.The constants depend on geometric lattice properties, and the theorem applies to finite-dimensional lattices with κ-local Hamiltonians.
6 Strong convexity of log Zβ(λ) log Zβ(λ) log Zβ(λ): The Hessian is positive semidefinite because its quadratic form is lower-bounded by the variance of a transformed local operator.The transformation fW is chosen so that the Hessian dominates tr[(fW)^2ρβ] − tr[fWρβ]^2.

7 Lower bound on the variance of quasi-local operators

This section establishes a variance lower bound for centered quasi-local operators by reducing global operators to local approximations and comparing finite-temperature behavior with infinite-temperature quantities.

7.4 Completing the strong-convexity proof: The variance theorem supplies the missing lower bound needed to convert the Hessian’s quasi-local variance representation into strong convexity of log Zβ.Applying the theorem to the filtered operator fW completes the proof strategy for the strong-convexity theorem.
7.2 From finite to infinite temperature: At infinite temperature, the maximally mixed state and orthogonality of the local operator basis simplify the variance analysis.The proof partitions the energy spectrum and controls cross terms using locality and exponential spectral concentration.
7.3 Some key quantities in the proof and proof sketch: The proof reduces variance control to the probability mass of A’s eigenvalues near zero, since small mass in [−γ, γ] yields a constant-scale variance lower bound.The projector onto this central spectral interval is defined using A’s eigenspaces and analyzed through the Gibbs-state distribution.
7.1 From global to local operators: A global quasi-local operator is decomposed into site-centered components, each approximated by an operator supported on a radius-R ball with a decaying tail.The approximation removes terms whose supports extend beyond the local ball, while quasi-locality controls the resulting error.
7.2 From finite to infinite temperature: Local unitary rotations are used to relate a finite-temperature variance to an infinite-temperature variance for a suitably chosen localized component.The argument establishes the existence of a unitary on the local region that enables this comparison.

A Proof of Fact 12

The appendix derives the Fourier transform of fβ(t) using contour integration, treating positive and negative t separately and combining the resulting expressions.

Fourier-transform derivation: The proof evaluates the Fourier transform by choosing separate contour paths for t > 0 and t < 0.The contours are identified as C+ and C−, with singularities handled through residues.
Fourier-transform derivation: The singular points of the transformed integrand occur at βω = iπ(2m + 1), enabling residue calculations.
Fourier-transform derivation: Combining the cases t > 0 and t < 0 yields the expression for fβ(t), whose summation is then evaluated.
Fourier-transform derivation: The resulting function fβ(t) exhibits exponential decay in |t|.

C Derivation of the sub-exponential concentration

This section proves concentration for a quasi-local operator by avoiding an imaginary-time norm bound that fails in dimensions D ≥ 2.

Derivation of the sub-exponential concentration: The argument reduces the target norm estimate to bounding the imaginary-time evolution of a local operator under A.
Derivation of the sub-exponential concentration: The conventional imaginary-time-evolution bound diverges for D ≥ 2, so it cannot establish the required concentration estimate there.The bound is finitely controlled for ν = O(1) only when D = 1.
Derivation of the sub-exponential concentration: The proof instead develops a different route to establish the lemma for operators with sub-exponentially decaying quasi-local terms.The operator is decomposed into κ-local components with sub-exponentially decaying coefficients.

C.1 Proof of Lemma 41

The proof of Lemma 41 bounds spectral-projector contributions and multi-commutators to control the norm associated with a quasi-local operator.

C.1 Proof of Lemma 41: The proof partitions the spectrum into carefully chosen intervals and bounds each spectral-projector contribution before summing over intervals.Intervals are chosen as Ij := (x − a1(j + 1), x − a1j].
C.1 Proof of Lemma 41: Claim 42 supplies the interval-wise projector estimate needed to derive the lemma’s main norm bound.
C.1 Proof of Lemma 41: The proof expands the relevant operator expression into multi-commutators of quasi-local components with the local operator OX.

D Quasi-locality of f W f W f W

The section establishes that f W admits a quasi-local representation by decomposing its terms into finite-radius contributions whose norms decay sub-exponentially.

D Quasi-locality of f W f W f W: The construction targets (τ, a1, a2, ζ)-quasi-locality for f W by representing it through operators supported on finite-radius balls.
D Quasi-locality of f W f W f W: The finite-radius contributions inherit decay from Lieb–Robinson estimates for the time-evolved local terms.The construction uses the Lieb–Robinson velocity vLR and bounds the truncated terms before summing them.
D Quasi-locality of f W f W f W: Each operator aB(r,i) is supported on the ball B(r, i), allowing the representation to be organized by increasing radius.
D Quasi-locality of f W f W f W: The resulting coefficients decay sub-exponentially with rate τ = 1/D for all i ∈ Λ.

E Proof of Lemma 34

The proof establishes a lower bound for the norm of the quasi-local operator f_W by truncating it to increasingly large regions and controlling approximation errors.

Proof of Lemma 34: The truncated operator f_W[B_r] preserves a lower-bound property with an O(1) constant c5.
Proof of Lemma 34: The contribution outside the ball B_r around i+ decays exponentially with r.
Proof of Lemma 34: The proof relates pointwise and Frobenius norms through support-based inequalities before invoking the lower bound for the truncated operator.
Proof of Lemma 34: Approximating f_W[B_r] by the operator supported on B_r′ incurs an error bounded by 2c3|v_i+|r^Dβe^(-c4|r′−r|/β).The constants c3 and c4 are O(1).

E.1 Proof of Claims 45, 46

Claims 45 and 46 show that quasi-local truncations approximate f_W near i+ and quantify the error when the support is enlarged from B_r to B_r′.

Proof of Claims 45, 46: The proof of Claim 45 uses the decay of f_β(t) and the Lieb–Robinson bound to control contributions from sites outside B_r.For sites j outside B_r, dist(i+,j) is at least r, while |v_j| is bounded by |v_i+|.
Proof of Claims 45, 46: The approximation error between f_W[B_r] and f_W[B_r,B_r′] is bounded by c3|v_i+|r^Dβe^(-c4|r′−r|/β).The bound follows from an integral representation and the Lieb–Robinson bound; c3 and c4 are O(1).
Proof of Claims 45, 46: The operator difference at i+ is bounded by twice the corresponding global operator-norm difference.

F Proof of Theorem 3

Theorem 47 proves a sample lower bound for Hamiltonian learning by reducing accurate parameter estimation to distinguishing exponentially many separated one-local Hamiltonians.

Proof of Theorem 3: The required number of Gibbs-state copies is lower bounded by the state-identification expression in Theorem 47.The theorem concerns estimating μ within ε in ℓ2-norm with probability 1−δ.
Proof of Theorem 3: The hard instance class consists of one-local Hamiltonians on m qubits with unknown parameters μ drawn from a separated set.The construction uses 2^m parameter points whose pairwise ℓ2 distances are at least ε.
Proof of Theorem 3: The packing set is constructed by sampling points in an orthant of a hypersphere and bounding close pairs with a union bound.
Proof of Theorem 3: An estimator accurate to ε can be converted into an identification procedure by assigning its output to the closest point in the separated parameter set.With probability 1−δ, separation ensures that the closest point is the correct parameter.