Sample-efficient learning of quantum many-body systems

Main contribution

• The work provides the first sample-efficient algorithm for quantum Hamiltonian learning, achieving sample complexity polynomial in the number of qudits.It is presented as the first rigorous result with guaranteed, non-trivial sample complexity for this problem.Source: §1 · pp. 3, 5

Problem definition

• The Hamiltonian Learning Problem estimates the coefficients of a κ-local, traceless Hamiltonian from local measurements on multiple copies of its Gibbs state.The Hamiltonian is parameterized by interaction coefficients µ, and the available measurements include all κ-local marginals.Source: §1 · p. 3

Physics perspective

• Hamiltonian learning can approximate effective interactions in strongly entangled many-body systems, including systems at finite temperature.Although interactions are local, the global Gibbs state can remain highly entangled, motivating direct inference of effective interactions.Source: §1 · pp. 3–4

Verification of quantum devices

• The problem also supports certification and calibration of noisy quantum Gibbs samplers by testing whether sampled outputs correspond to the intended Hamiltonian.Gibbs-state preparation is used in quantum algorithms for semidefinite programming, simulated annealing, Metropolis sampling, quantum machine learning, and finite-temperature simulation.Source: §1 · p. 4

Methodological significance

• Maximum entropy estimation and tools from statistics and machine learning yield the polynomial sample-complexity guarantee unconditionally.The result establishes a rigorous connection between machine-learning methods and quantum many-body Hamiltonian learning without relying on heuristic grounds.Source: §1 · p. 5

Problem formulation

• The Hamiltonian learning problem estimates the coefficients of a κ-local Hamiltonian from N copies of its Gibbs state at fixed inverse temperature β, with an ℓ2 accuracy guarantee.The coefficients satisfy maxℓ∈[m] |µℓ| ≤ 1, and the estimate must succeed with probability at least 1−δ.Source: §2 · p. 5

Sample-efficient upper bound

• Theorem 2 establishes a sample-efficient algorithm for solving the Hamiltonian learning problem using copies of the Gibbs state, with constants determined by the Hamiltonian geometry.This is presented as the first unconditional and rigorous upper bound on the problem’s sample complexity.Source: §2 · p. 5
• For spatially local Hamiltonians, m=O(n), so Theorem 2 yields sample complexity polynomial in the number of qudits.The result applies to Hamiltonians whose number of interaction terms scales linearly with n.Source: §2 · p. 5

Temperature dependence

• Sample requirements increase as β approaches either 0 or infinity because the Gibbs state becomes less informative about the Hamiltonian parameters.At high temperature it approaches the maximally mixed state, while at low temperature it approaches the ground space.Source: §2 · pp. 5–6

Lower bound

• The Hamiltonian learning problem has an Ω(√m) sample lower bound in ℓ2 norm, making the upper bound tight up to polynomial factors.The lower bound follows from a reduction to state discrimination.Source: §2 · p. 6

3.1 Maximum entropy estimation and sufficient statistics

• Matching all κ-local Gibbs-state marginals uniquely determines the global Gibbs state and its Hamiltonian coefficients.This supports a quantum maximum-entropy estimator that fits measured local marginals, with the empirical dual program accounting for finite-sample errors.Source: §3.1 · pp. 6–7

3.2 Strong convexity

• Strong convexity of log Z_β yields the main technical route from marginal-estimation error to Hamiltonian-parameter error.For κ-local Hamiltonians with ||μ|| ≤ 1, the Hessian obeys v^T∇^2 log Z_β(μ)v ≥ e^−O(βc)β^c′; combining this with the error bound for empirical marginals gives the paper’s main result.Source: §3.2 · p. 8

3.3 Strong convexity of log-partition function: Review of the classical case

• In the classical case, the Hessian is governed by covariances, and the Gibbs Markov property converts local conditional variances into an extensive global variance lower bound.The resulting classical sample complexity is more efficient than the paper’s bound by only a polynomial factor in m.Source: §3.3 · pp. 9–10

3.4.1 Relating the Hessian to a variance

• For noncommuting Hamiltonians, the Hessian is not directly a covariance matrix, so it is lower-bounded instead by the variance of a suitably defined quasi-local operator.This extends the classical variance strategy without requiring the Hamiltonian terms to commute.Source: §3.4.1 · p. 10

3.4 Strong convexity of log-partition function: Proof of the quantum case

• Quantum conditional independence cannot supply the classical argument unconditionally because Gibbs states can have nonzero quantum conditional mutual information.Approximate decay of qCMI is conjectured generally but is established only in restricted regimes, including sufficiently high temperatures and one-dimensional chains.Source: §3.4.2 · p. 11

3.4.2 Lower bounding the variance

• The quantum proof reduces the variance of a general quasi-local observable to a single local variance, costing an extra factor of m in the strong-convexity bound.Haar-random local unitaries isolate terms acting on one qudit, while local-unitary invariance controls the Gibbs-state spectral changes.Source: §3.4.2 · pp. 11–12
• A local basis change compares finite-temperature local variance with its infinite-temperature counterpart, enabling a constant lower bound and hence the global variance estimate.The construction uses a unitary supported on O(1) sites and the maximally mixed state η.Source: §3.4.2 · p. 12

4.1 Connection to previous work

• Unlike shadow tomography [Aar18a] [AR19] [BKL+17], the goal is to estimate Hamiltonian coefficients from local observables, using methods such as [HKP20], [CW20], and [BMBO19].Shadow tomography estimates observable marginals and does not itself bound Hamiltonian coefficients; spatial locality avoids its machinery for nonlocal observables.Source: §4.1 · p. 13
• Prior Hamiltonian-learning methods [BAL19] [EHF19] depend on an unbounded spectral-gap assumption, while simulator-based methods [WGFC14b] [WGFC14a] [VMN+19] use numerical or heuristic analysis.Amin et al. instead proposed training quantum Boltzmann machines with gradient descent.Source: §4.1 · p. 13
• The work achieves polynomial sample complexity for spatially local Hamiltonians in ℓ2-norm, whereas classical methods can learn graph structure and parameters in ℓ∞-norm from O(log n) samples.The quantum analysis cannot reach O(log n), partly because noncommutativity prevents node-wise convex programs and Markov-property-based strong-convexity arguments.Source: §4.1 · p. 13

4.2 Open questions

• Maximum-entropy estimation may require approximating an NP-hard partition function [Mon15a], so this work bounds sample complexity while leaving efficient running time for future work.Achieving both few samples and efficient computation remains challenging even for classical problems at all inverse temperatures β.Source: §4.2 · pp. 13–14
• Open problems include size-independent variance bounds under correlation decay, stronger high-temperature or commuting-case guarantees, and efficient algorithms combining partition-function methods or quantum Gibbs samplers.The authors also seek refined objectives matching classical learning performance, requiring new insights into quantum Gibbs-state information properties.Source: §4.2 · p. 14

5.1 Some mathematical facts

• The preliminaries define operator norms, Hilbert-Schmidt inner products, entropy, relative entropy, PSD Hessians, and exponential-sum estimates used later.Source: §5.1 · pp. 14–15

5.2 Local Hamiltonians and quantum Gibbs states

• Geometrically local Hamiltonians decompose into O(n) Hermitian basis terms, while quasi-locality and Lieb-Robinson bounds control locality under time evolution.Interactions act on connected neighborhoods of a constant number of qudits; the canonical representation uses m = O(n) terms.Source: §5.2 · pp. 15–16
• Matching all κ-local expectation values uniquely identifies the Gibbs state and its Hamiltonian coefficients, with approximate matching yielding a relative-entropy bound.The approximate statement gives S(ρβ(µ)∥ρβ(λ)) ≤ O(mε), followed by a trace-distance consequence via Pinsker’s inequality.Source: §5.2 · p. 17

5.3 Quantum belief propagation

• Quantum belief propagation provides locality-respecting derivatives of Gibbs states when a Hamiltonian is perturbed by a generally noncommuting operator, extending the commuting case.The framework is developed in [Kim17], and Proposition 20 is stated as a result cf..Source: §5.3 · p. 18

5.4 Change in the spectrum after applying local operators

• A quasi-local analogue of the local-operator spectral-variation lemma is introduced to support lower bounds on variances of quasi-local operators.The proof analyzes a moment function rather than the moment-generating function used in.Source: §5.4 · pp. 18–19

5.5 Local reduction of global operators

• Local reduction removes operator terms acting trivially on a chosen site, and Claim 23 states that the resulting component retains a non-negligible Frobenius norm relative to the global operator.Source: §5.5 · p. 19

5.6 Stochastic convex optimization applied to Hamiltonian learning

• Strong convexity converts marginal-estimation accuracy into Hamiltonian-parameter accuracy and yields a Gibbs-state sample-complexity bound under ∇2 log Z(λ) ⪰ α1.The optimization is convex because log Zβ(λ) is convex; marginal estimates can use commuting measurements or shadow tomography, including procedures from [CW20] [BMBO19] and [HKP20, Theorem 1].Source: §5.6 · pp. 20–22

Strong convexity theorem

• For every v ∈ R^m, v^T∇²log Z_β(μ)v ≥ βc′e^−O(βc)/m · ||v||², establishing strong convexity with lattice-dependent constants.The theorem assumes a κ-local Hamiltonian on a finite-dimensional lattice and fixed inverse temperature β, with c,c′ > 3 depending on lattice geometry.Source: §6 · p. 22

Hessian representation

• The Hessian is derived using quantum belief propagation because the Hamiltonian terms need not commute, yielding a symmetric real matrix.The derivation defines W_v = ∑_i v_iE_i and uses the quantum belief propagation operator Φ_H(λ).Source: §6 · p. 23

Quasi-local variance bound

• The Hessian is lower-bounded by the variance of a quasi-local operator, specifically log Z_β(λ) ≥ tr(Ẇ²ρ_β(λ)) − tr(Ẇρ_β(λ))².The operator Ẇ is constructed from W_v using a carefully chosen function f_β whose Fourier transform preserves the needed positivity properties.Source: §6 · pp. 24–25

Convexity

• The Hessian is positive semidefinite because it can be expressed through a nonnegative Fourier-weighted form, proving convexity before strengthening the bound.The argument uses positivity and symmetry properties of the relevant kernel and the Hermiticity of W.Source: §6 · pp. 24–25

7.1 Warm-up: Variance at infinite temperature

• At infinite temperature, Theorem 32 lower-bounds the variance of f W when W has locality κ=O(1), using energy-basis expansion and locality to control noncommuting cross terms.The proof uses spectral concentration and chooses a cutoff s̄=O(log(m)) when λ, C, and κ are O(1).Source: §7.1 · pp. 26, 28, 29

7.2 Variance at finite temperature

• Theorem 33 lower-bounds the variance of a centered (τ, a1, a2, 1)-quasi-local operator at finite temperature under β>0, τ≤1, a2=O(1/β), and a1=O(1).The theorem assumes a κ-local Hamiltonian and connected supports, while suppressing lattice-dependent terms such as dimension and graph degree.Source: §7.2 · p. 29

7.3 Some key quantities in the proof and proof sketch

• The proof of Theorem 33 concentrates the Gibbs-state spectrum of A near zero and shows that sufficiently little probability mass can remain in a constant-width interval.A projector onto eigenvalues in [−γ, γ] is used; controlling its probability mass yields a variance lower bound.Source: §7.3 · pp. 30–31, Figure 2 · p. 31

7.4 Reducing the global problem to a local problem

• A global quasi-local operator is decomposed into site-associated operators and approximated by an operator supported on a radius-R ball, with a tail that decays sub-exponentially in R.For the theorem’s parameters, the approximation condition can be ensured with a suitable radius choice.Source: §7.4 · pp. 31–32

7.5 Variance of operators with small support: finite temperature to infinite temperature

• A local unitary can align the eigenvectors of the local operator with those of the reduced Gibbs state, relating its finite-temperature variance to its infinite-temperature variance.The alignment orders the operator eigenvalues and Gibbs-state probabilities to obtain the desired comparison.Source: §7.5 · pp. 33–34

7.6 Invariance under local unitaries

• Claims 37 and 38 show that local unitaries preserve the relevant spectral-concentration behavior up to controlled corrections, enabling variance bounds after local rotations.This invariance supports a polynomial improvement over the initial inverse-polynomial variance bound.Source: §7.6 · pp. 34–35

7.7 Proof of the Theorem 33

• Theorem 33 follows by combining the local-unitary comparison with the global-to-local reduction: concentration of A would contradict the variance lower bound obtained after an appropriate rotation.The proof invokes Claim 36, Corollary 39, and the constant lattice-dimension assumption.Source: §7.7 · pp. 35–37

7.8 Proof of Claims 37 and 38

• The proof of Claim 37 considers arbitrary unitaries UX and decomposes F into quantities QA using eigenvectors and eigenvalues of Hamiltonian H′, with Δ > 0.Source: §7.8 · p. 37
• The proof of Claim 37 combines bounds on two terms, universal-constant estimates, and normalization identities to obtain the claimed upper bound.The derivation uses the triangle inequality and the fact that tr(ρ_β)=1 before concluding the claim.Source: §7.8 · pp. 38–39
• Claim 38 is proved by decomposing Q_A through spectral projectors and bounding the resulting Frobenius-norm terms using Lemma 22 and Claim 37.The argument applies the triangle inequality, Cauchy–Schwarz, Fact 12, and normalization of √ρ_β to control the decomposed contributions.Source: §7.8 · pp. 39, 40, 42

A Proof of Fact 12

• The proof restates Fact 12 and establishes its three summation bounds through separate estimates.The second sum uses the maximum of t^b e^(-ct^p), while the third uses an identity followed by concavity when p < 1.Source: A Proof of Fact 12 · pp. 46–47

B Fourier transform of tanh(βω/2)/(βω/2)

• The Fourier transform calculation begins for t > 0 by integrating along the contour C+ shown in Figure 3.Cauchy’s integral theorem supplies the contour-based framework for evaluating the transform.Source: B Fourier transform of tanh(βω/2)/(βω/2) · p. 48, Figure 3 · p. 48
• The integrand’s singular points occur at βω = iπ(2m + 1), and their residues determine the transform for t > 0.The residues are evaluated at the singularities enclosed by the contour.Source: B Fourier transform of tanh(βω/2)/(βω/2) · p. 48
• For t < 0, the derivation instead uses the contour C− and evaluates the corresponding residues.This supplies the negative-time counterpart to the t > 0 calculation.Source: B Fourier transform of tanh(βω/2)/(βω/2) · p. 48
• Combining the positive- and negative-time expressions yields a unified formula for fβ(t), whose series is then evaluated for x > 0.The resulting summation produces the closed expression used for the transform.Source: B Fourier transform of tanh(βω/2)/(βω/2) · p. 49
• The resulting Fourier transform fβ(t) exhibits exponential decay in |t|.This decay is the final qualitative property established by the calculation.Source: B Fourier transform of tanh(βω/2)/(βω/2) · p. 49

C Derivation of the sub-exponential concentration

• The target lemma concerns a (τ, a1, a2, 1)-quasi-local operator A with τ < 1 and a normalized operator O_X supported on k0 sites.The constants c5 and λ1 depend only on a1 and a2, with c5 proportional to a2/τ.Source: C Derivation of the sub-exponential… · p. 49
• A standard upper-bound strategy uses Ref. to reduce the estimation problem to bounding ∥e^(νA)O_Xe^(-νA)∥.The reduction proceeds through spectral projectors of A and a norm estimate.Source: C Derivation of the sub-exponential… · pp. 49–50
• The main contribution proves the lemma without using inequalities that rely on earlier results.Those inequalities would require controlling the norm of an imaginary-time evolution that diverges for D ≥ 2.Source: C Derivation of the sub-exponential… · p. 50
• For ν = O(1), the norm ∥e^(νA)O_Xe^(-νA)∥ diverges to infinity when D ≥ 2, although it can be finitely bounded for D = 1.Here, A is decomposed into κ-local terms with sub-exponentially decaying coefficients g_ℓ = exp(−O(ℓ^(1/D))).Source: C Derivation of the sub-exponential… · p. 50

C.1 Proof of Lemma 41

• Lemma 41 is proved by expanding over carefully chosen intervals I_j and reducing the projector-norm estimate to Claim 42.The intervals are I_j := (x − (j + 1)a_1, x − ja_1], and the resulting sum over j yields the form of Eq. (131).Source: §C.1 · pp. 50–51
• For an arbitrary interval I := (ω − a_1, ω], Claim 42 supplies the projector bound required in the proof of Lemma 41.The proof applies Claim 42 with ω = x − ja_1 and θ = y + ja_1 before summing over j.Source: §C.1 · p. 50
• The final summation uses Fact 12 (3) with c = (ec_6k_0/a_1)^−1/τ_1, p = 1/τ_1, and a = y/a_1 to obtain Eq. (131).Source: §C.1 · p. 51

C.2 Proof of Claim 42

• Claim 42 bounds the multi-commutator ad^s_Ã(O_X) after introducing à := A − ω1 and using an identity for repeated commutators.The argument applies the multi-commutator estimate to the inequality preceding Claim 42 and chooses m to satisfy a condition involving θ, c_6, and k_0.Source: §C.2 · pp. 51–52
• The choice of m is controlled by ˜m^τ_1 ≤ θ/(ec_6k_0), with c_6 := 8ea_1[2/(a_2τ)]^2/τ, completing Claim 42.The proof takes ˜m as the minimum integer satisfying the required condition and uses the resulting floor-function expression.Source: §C.2 · p. 52

C.3 Proof of Claim 43

• Claim 43 expands the multi-commutator of an operator O_X supported on k_0 sites into nested commutators with the components of A.The expansion is combined with Lemma 3 in Ref. [KMS16], with ζ = 1, to bound nested-commutator norms.Source: §C.3 · p. 52
• The resulting bound factors decay weights g_{k_j} with products of cumulative support sizes, then uses log[g_k/a_1] = −a_2k^τ for τ ≤ 1.The proof sums over multi-indices, bounds cumulative sums by K, and invokes the sub-exponential form of g_K together with Fact 12.Source: §C.3 · pp. 52–53

• The goal is to prove that f W is (τ, a1, a2, ζ)-quasi-local under Definition 14.Source: D Quasi-locality of f W f W f W · p. 53
• Lieb–Robinson estimates, including the bound ∥˜Er_i(t)∥≤2, control contributions outside radius-r balls and yield a quasi-local expansion.The estimate uses the Lieb–Robinson velocity vLR, ∥Ei∥=1, and constants c3, c4; [BHV06] supplies the cited bound.Source: D Quasi-locality of f W f W f W · p. 54
• Each radius-r contribution is replaced by an operator aB(r,i) supported on B(r, i), producing a quasi-local representation of f W.The construction uses |B(r, i)| = O(rD) to control the support size.Source: D Quasi-locality of f W f W f W · pp. 54–55
• The resulting decay is sub-exponential with rate τ = 1/D for every i ∈ Λ, and the parameter ζ is obtained from Eq. (19).Source: D Quasi-locality of f W f W f W · p. 55
• The representation is completed using |B(r, j)| ≤ cB rD and Fact 12 (2) with p = 1, b = 2D, and c = π/(2βvLR).Source: D Quasi-locality of f W f W f W · p. 55

Localization around i_+

• The proof localizes f^W to the ball B_r around i_+, using a truncated operator f^W[B_r] whose lower bound follows by the same argument as Theorem 32.Claim 44 supplies the needed O(1)-constant bound for the localized operator.Source: E Proof of Lemma 34 · pp. 55–56

Exponential truncation error

• The contribution of terms outside B_r decays exponentially in r, so f^W(i_+) is controlled by the localized value f^W[B_r](i_+).Claim 45 makes the approximation quantitative, and the proof applies the triangle inequality together with the Frobenius/operator norm relation.Source: E Proof of Lemma 34 · p. 56

Quasi-local approximation

• The localized operator f^W[B_r] is further approximated by the operator f^W[B_r,B_{r'}] supported on B_{r'}, with error bounded by 2c3|v_i+|rDβe^(-c4|r′−r|/β).This is the quasi-locality estimate used to reduce the target inequality to an operator supported on the larger ball.Source: E Proof of Lemma 34 · p. 56

Parameter choice and conclusion

• Choosing r′ = 2r and r = O(1)·Dβ log(β) + 1 makes the accumulated approximation errors sufficiently small, and maximizing over sites completes the proof.The argument uses |B_{r′}| ≤ c8(r′)^D and the inequality max_i∈Λ ∥f^W(i)∥F ≥ ∥f^W(i_+)∥F.Source: E Proof of Lemma 34 · p. 57

Proof of Claim 45

• Claim 45 follows from an integral representation of f_W(i+) and the Lieb–Robinson bound, using f_β(t)'s e−O(t/β) decay beyond distance r.The argument also uses |v_j| ≤ |v_i+| and dist(i+, j) ≥ r for j ∈ B^c.Source: §E.1 · pp. 57–58

Proof of Claim 46

• Claim 46 proves ∥f_W[B_r] − f_W[B_r,B_{r′}]∥ ≤ c3|v_i+|r^Dβe−c4|r′−r|/β.The bound is obtained from an integral representation, the Lieb–Robinson bound, and |B_r| ∝ r^D.Source: §E.1 · p. 58
• The corresponding sitewise error satisfies ∥f_W[B_r](i+) − f_W[B_r,B_{r′}](i+)∥ ≤ 2∥f_W[B_r] − f_W[B_r,B_{r′}]∥.This is the second inequality derived in the proof of Claim 46.Source: §E.1 · p. 58

F Proof of Theorem 3

• Theorem 47 restates Theorem 3 as a lower bound on Gibbs-state copies needed to output ˆµ with ∥ˆµ − µ∥2 ≤ ε and success probability 1 − δ.The bound concerns Hamiltonian learning for parameters in R^m.Source: F Proof of Theorem 3 · p. 59
• The proof uses a set S of 2^m one-local Hamiltonian parameters whose pairwise ℓ2 distances are at least ε.Such a packing is established by selecting points on an orthant of the radius-θ hypersphere and applying a union-bound volume estimate.Source: F Proof of Theorem 3 · p. 59
• Any algorithm achieving ε-accuracy with probability 1 − δ can be converted into an exact identifier for the unknown parameter in S by choosing the closest packed point.The packing guarantees that the recovered point is correct whenever the learning algorithm succeeds.Source: F Proof of Theorem 3 · p. 59
• Quantum state-discrimination lower bounds then imply that identifying the 2^m Gibbs states requires a sample count governed by log |S|, δ, and the maximum Gibbs-state norm.The proof invokes through [HW12, Equation 2], after bounding the relevant state norm.Source: F Proof of Theorem 3 · pp. 59–60