PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal learning of quantum Hamiltonians from high-temperature Gibbs states

Jeongwan Haah, Robin Kothari, Ewin Tang

arXiv:2108.04842v3quant-phcs.DScs.LG

TL;DR

The paper asks whether Hamiltonians can be learned efficiently from Gibbs-state copies in the high-temperature regime, beyond geometrically local systems. It uses a Taylor-expansion-based algorithm for low-intersection Hamiltonians and establishes optimal sample complexity with linear-in-sample-size runtime.

  • Problem

    Given Gibbs-state copies at known inverse temperature, the problem is to learn an unknown Hamiltonian while minimizing sample and running-time costs.

    Source: §1 · p. 2

  • Method

    The algorithm uses a high-temperature Taylor expansion of observable expectations and Newton–Raphson to solve the resulting polynomial system.

    Source: §1 · p. 7, §4 · p. 31, §4.1 · p. 32

  • Results

    The sample complexity matches the classical bound in the high-temperature regime, improves on [AAKS21], and has a matching lower bound; runtime is linear in sample size.

    Source: §1 · p. 5

  • Takeaways & Limitations

    The matching lower bound establishes that the algorithm's sample complexity cannot be improved, and its runtime is linear in the input sample size.

    Source: §1 · p. 5, §6 · p. 44

    Efficient learning in the low-temperature regime remains open; the high-temperature expansion does not generally converge for large β.

    Source: §6 · p. 44

Abstract

from arXiv · show

We study the problem of learning a Hamiltonian $H$ to precision $\varepsilon$, supposing we are given copies of its Gibbs state $\rho=\exp(-\beta H)/\operatorname{Tr}(\exp(-\beta H))$ at a known inverse temperature $\beta$. Anshu, Arunachalam, Kuwahara, and Soleimanifar (Nature Physics, 2021, arXiv:2004.07266) recently studied the sample complexity (number of copies of $\rho$ needed) of this problem for geometrically local $N$-qubit Hamiltonians. In the high-temperature (low $\beta$) regime, their algorithm has sample complexity poly$(N, 1/\beta,1/\varepsilon)$ and can be implemented with polynomial, but suboptimal, time complexity. In this paper, we study the same question for a more general class of Hamiltonians. We show how to learn the coefficients of a Hamiltonian to error $\varepsilon$ with sample complexity $S = O(\log N/(\beta\varepsilon)^{2})$ and time complexity linear in the sample size, $O(S N)$. Furthermore, we prove a matching lower bound showing that our algorithm's sample complexity is optimal, and hence our time complexity is also optimal. In the appendix, we show that virtually the same algorithm can be used to learn $H$ from a real-time evolution unitary $e^{-it H}$ in a small $t$ regime with similar sample and time complexity.

1 Introduction

The paper studies learning an unknown Hamiltonian from Gibbs-state copies, addressing whether quantum learning can match classical sample complexity while improving time efficiency. It extends the analysis beyond geometrically local systems to low-intersection Hamiltonians.

Our results

  • Low-intersection Hamiltonians need no geometric constraints and include geometrically local Hamiltonians, but the converse does not hold.The introduction assumes constant degree, although the general algorithm can handle growing degree.Source: §1 · p. 3
  • The algorithm matches the classical sample complexity in the high-temperature regime, improves on [AAKS21], and has optimal time complexity; a matching sample lower bound holds across the full range of β.Its runtime is linear in the sample size.Source: §1 · pp. 4–5
  • The log-partition function is (β²)-strongly convex in the high-temperature regime, improving the earlier bound to within a constant factor of its true value.This yields a local-observable variance lower bound of Ω(β²||v||²), improving on the bound implied by [AAKS21].Source: §1 · p. 5
  • The paper also proves a matching lower bound using simple 2-local Hamiltonians in which each qubit participates in only one term.Thus, restricting to this simpler Hamiltonian family does not improve the sample complexity over the algorithm's bound.Source: §1 · p. 5
  • Virtually the same algorithm learns a low-intersection Hamiltonian from black-box real-time evolution U=e^-itH when the known time t is below a class-dependent constant.The paper reports a quadratic sample-complexity improvement over prior short-time methods and uses constant time resolution.Source: §1 · pp. 5–6

High-level overview of techniques

  • The algorithm uses a convergent high-temperature Taylor expansion of observable expectations, then solves the resulting polynomial system with Newton–Raphson.The resulting runtime is dominated by reading the input.Source: §1 · pp. 6–7

2 Preliminaries

The preliminaries define the Hamiltonian and interaction-graph notation used throughout, specify the computational model and assumptions, and review analytic-series facts used to justify expansions.

2 Preliminaries

  • A Hamiltonian is a sum of Hermitian terms weighted by coefficients, and the paper uses standard natural-log and norm conventions.The terms have norm at most 1, coefficients lie in [−1, 1], and the system is represented on N qubits.Source: §2.1 · p. 8, §2 · p. 8

2.1 Notations and conventions

  • The dual interaction graph connects terms with intersecting supports, and its maximum degree d is constant in the principal setting.The paper also assumes distinct non-identity Pauli terms for its full algorithm; geometrically local classes are examples with degree independent of M.Source: §2.1 · pp. 8–9

2.2 Time complexity

  • The runtime analysis uses a word-RAM model and assumes adjacency-list access to the dual graph, while quantum operations are single-qubit Pauli measurements.The adjacency list can be constructed in O(LMd log d) time; numerical stability is set aside because Newton iterations account for per-iteration error.Source: §2.2 · pp. 9–10

2.3 Analytic functions and series expansions

  • Analyticity and uniform convergence justify using Taylor expansions to recover function values within their real domain of convergence.The paper notes that smooth real differentiability alone does not suffice for this argument.Source: §2.3 · pp. 10–11

3 Series expansions of expectation values

This section develops a convergent Taylor expansion for expectation values of local operators and the logarithmic partition function, establishing properties of the Hamiltonian-learning expansion. It also provides graph-based bounds and efficient procedures for enumerating connected clusters and computing their derivatives.

3 Series expansions of expectation values

  • The Taylor series for local-operator expectation values converges when 2e^2(d + 1)^2β < 1; its degree-m homogeneous polynomial uses λb only if distG(a, b) ≤ m and has at most ed(1 + e(d − 1))^m monomials.Source: §3 · p. 11

3.1 The logarithmic partition function

  • The log-partition function provides a route to the expectation expansion through differentiation, while offering an advantage over expanding a ratio of traces directly.The section connects its differentials to the expansion and studies the log-partition function for this reason.Source: §3.1 · p. 13

3.2 Deriving multivariate Taylor series expansions

  • Complex differentiability first guarantees a Taylor series near the origin, which the authors then recast as a multivariate expansion in Hamiltonian coefficients whose convergence they analyze.The derivation starts from a β-series valid on an unspecified neighborhood before studying the multivariate series.Source: §3.2 · pp. 13–15

3.3 Counting connected clusters

  • Only connected clusters have nonzero log-partition coefficients, and their number at weight w through a fixed node is at most ed(1 + e(d − 1))^(w−1) for d ≥ 2.For d = 1, the stated upper bound is w.Source: §3.3 · pp. 15–16

3.4 Enumerating connected clusters

  • A breadth-first layering and recursive multiset construction enumerate weight-m clusters by extending each partial cluster through neighboring nodes while tracking remaining weight.The recursion starts at the chosen node and returns all possible continuations that complete the cluster to total weight m.Source: §3.4 · p. 18
  • Cluster enumeration runs in O(mdC) time, where C is the number of clusters output and d bounds the dual interaction graph’s degree.The bound accounts for computing each cluster’s neighborhood across its constituent multisets.Source: §3.4 · p. 18

3.5 Estimating cluster derivatives

  • The derivative analysis represents a multiset cluster by a graph whose nodes encode term multiplicities, then bounds associated graph quantities using spanning trees and node degrees.The proof uses graph partitions and coloring counts, with deletion-contraction arguments; the approach follows [WA22].Source: §3.5 · pp. 19, 23, 24

3.6 Computing cluster derivatives

  • For Pauli terms supported on at most L qubits, a deterministic algorithm computes the normalized cluster derivative exactly as a rational number in (8m + L) poly(m) time.The algorithm’s stated input is a cluster of total weight m + 1.Source: §3.6 · p. 25
  • The procedure powers a faithful Pauli-matrix representation and recursively computes the required constant term using O(m^3) integer operations.The coefficient arithmetic uses integers with O(m^2 log m) digits.Source: §3.6 · pp. 26–28
  • Cluster-derivative computation takes O(Lm^3 + 8^m m^5 log^2 m) time.Source: §3.6 · p. 28

3.7 Proof of Theorem 3.1

  • The expectation value of Ea, written as Tr(Ea e−βH)/Tr e−βH, is given by the first derivative of the logarithmic partition function with respect to λa, evaluated at λ=ξ.Source: §3.7 · p. 29
  • The proof shows p_m is homogeneous of degree m, supported within graph distance m, and bounded using cluster counts and derivative magnitude.Cluster enumeration and Proposition 3.13 establish the algorithmic items (A) and (B), completing Theorem 3.1.Source: §3.7 · p. 30

4 Learning algorithm

This section presents an algorithm that estimates local Pauli expectations from Gibbs-state copies and inverts the expectation map to recover Hamiltonian coefficients, analyzing coefficient accuracy under high-temperature conditions and runtime linear in the number of terms for constant interaction parameters. It also establishes convergence of the Newton–Raphson method, showing that iteration error decays and the iterates approach an ε-scale solution under stated conditions.

4 Learning algorithm

  • Coloring the dual interaction graph lets the algorithm estimate nonoverlapping Pauli terms simultaneously, using d + 1 measurement rounds to obtain all expectations to βε accuracy.The estimates are combined with a union bound to ensure all M estimates are accurate with probability at least 1 − δ.Source: §4 · p. 31

4.1 Definitions and a sample complexity upper bound

  • The result guarantees that one can find x ∈ [−1, 1]^M with ∥x − λ∥∞ ≤ ε with probability at least 1 − δ, using only copies of the Gibbs state.Source: §4.1 · p. 32
  • The Jacobian analysis also yields a strong-convexity bound for the log-partition function that is optimal up to constants, improving the bound discussed in [AAKS21].The paper states that the strong-convexity constant is only a constant factor from optimal.Source: §4.1 · p. 33

4.2 Time complexity and analysis of the Newton–Raphson method

  • The Newton–Raphson method avoids explicitly inverting the Jacobian, and its runtime is linear in M when L and d are constant; its ε-dependence is better than the sample complexity’s ε^-2 dependence.The analysis does not guarantee success for arbitrarily large d at fixed β and ε.Source: §4.2 · pp. 34–35
  • The Newton–Raphson iteration’s error decays exponentially with K.The analysis bounds the next-iterate error ∥∆′∥∞ and summarizes its decay for the iteration in Eq. (118).Source: §4.2 · pp. 37, 39
  • Under the stated conditions, after T iterations the solution error satisfies ∥x_t−λ∥∞≤18ε.The theorem requires 75εe^2β(d+1)^6τ^2≤1/4 and ∥∆_0∥∞≤1/(25e^2β(d+1)^6τ^2).Source: §4.2 · p. 39
  • Given ∥∆_0∥∞≤1, the theorem’s initialization condition holds when β≤(25e^2(d+1)^6τ^2)^−1 and ε≤1/12.These are sufficient parameter conditions stated for the convergence result.Source: §4.2 · p. 39

5 Lower bounds

The section establishes sample-complexity lower bounds for Hamiltonian learning, first for constant-size instances and then for ℓ∞ and ℓ2 error. Its constructions reduce learning to distinguishing Gibbs-state distributions, using KL divergence and Fano’s lemma.

5.1 Warmup for constant N

  • For constant N, distinguishing the constructed Gibbs states requires Ω(exp(2β)/(β^2 ε^2)) samples when ε ≤ 1/2.The argument bounds their KL divergence and uses the inverse-divergence sample lower bound.Source: §5.1 · pp. 40–41

5.2 Lower bound for ℓ∞error

  • The ℓ∞ construction places one altered two-qubit Hamiltonian among N pairs, making learning distinguish among N + 1 possible Gibbs states.The proof applies Fano’s lemma after relating the distributions’ KL divergence to the constant-size warmup.Source: §5.2 · p. 42
  • For nonadaptively chosen inverse temperatures, the ℓ∞ lower bound scales as Ω(min_β [e^(2β)/(β^2 ε^2)] log N).The bound also applies when different samples use different temperatures; the minimum is over the temperatures used.Source: §5.2 · pp. 42–43

5.3 Lower bound for ℓ2 error

  • For ℓ2 error, a code with linear rate and distance at least N/10 turns sufficiently accurate learning into exact codeword identification.The proof bounds pairwise KL divergence and applies Fano’s lemma to the resulting Gibbs-state distributions.Source: §5.3 · pp. 43–44

6 Discussion

The paper concludes that its high-temperature algorithm has optimal sample and time complexity under a constant-degree assumption. It identifies growing degree and low temperatures as boundaries for the analysis and algorithmic setting.

6 Discussion

  • The algorithm has optimal sample and time complexity, with runtime linear in the total number of qubits across its samples; the optimality claims treat dual-graph degree as constant.The critical temperature for the guarantee depends only on that degree.Source: §6 · p. 44
  • For growing degree, extending the algorithm beyond low-intersection Hamiltonians is feasible in principle, but the Taylor-series monomial count grows exponentially in d.The discussion contrasts an O(d^10) Newton–Raphson convergence threshold with an O(d^2) threshold for the β-series expansion.Source: §6 · p. 44
  • Efficient learning in the low-temperature regime remains open because phase transitions can prevent the high-temperature expansion from converging in general.The paper also notes that low-temperature partition functions are generally at least NP-hard to compute.Source: §6 · p. 44

A Learning Hamiltonians from real time dynamics

The appendix considers learning Hamiltonian coefficients through queries to a time-evolution unitary. For sufficiently small known evolution time, it gives an algorithm and discusses the time-parameter dependence of its complexity.

A Learning Hamiltonians from real time dynamics

A.1 Series expansion of time-evolved operators

The appendix extends the series-expansion analysis to time-evolved operators and establishes structural and computational bounds for the resulting polynomials. These bounds constrain which Hamiltonian coefficients can appear at each order and support efficient series computation.

A.1 Series expansion of time-evolved operators

  • The expansion of UPU† has degree-m homogeneous matrix-valued polynomials q_m, with equality when the series converges absolutely.The results apply to single-qubit Pauli P and L-qubit Pauli Q.Source: §A.1 · p. 46
  • At order m, q_m can involve λ_a only when a lies within distance m of P in the augmented interaction graph G(P).The graph adds a node for P and connects it to terms whose supports overlap P.Source: §A.1 · p. 46
  • q_m contains at most max(L, d)e^d(1 + e(d − 1))^(m−1) monomials, and each monomial’s coefficient matrix has spectral norm at most 2^m.Source: §A.1 · p. 46
  • For Pauli interaction terms, the series monomials can be enumerated and the truncated F(Q, P) series computed exactly in the stated polynomial-time procedures.The passages specify enumeration time O(md^C) and exact computation time C(4m + L) poly(m).Source: §A.1 · p. 46
  • A cluster derivative vanishes when its cluster together with P is disconnected, and for a cluster of size n its norm is at most 2^n|t|^n.The vanishing follows because a disconnected interaction term commutes with the intermediate nested commutator.Source: §A.1 · p. 47

A.2 Learning algorithm

The real-time learning procedure adapts the Gibbs-state algorithm by estimating observables after applying the evolution unitary. Its analysis uses the time-series expansion, and the method is restricted to sufficiently small evolution times.

A.2 Learning algorithm

  • The real-time algorithm uses the same overall approach as Gibbs-state learning, with Pauli observables chosen to anticommute with each Hamiltonian term.The resulting F_a has a leading term that is a known constant multiple of λ_a, supporting the classical Newton–Raphson analysis.Source: §A.2 · pp. 48–49
  • Random product-state preparations and measurements after U provide bounded estimators for the observables associated with Hamiltonian terms.The construction conditions on the sampled local state matching P_a, enabling estimators for different terms from one unitary application when their terms do not overlap.Source: §A.2 · p. 48
  • The quantum sampling procedure retains the same time complexity, with only one additional O(1)-time check per sample.Source: §A.2 · pp. 48–49
  • The series analysis only guarantees convergence for t < 1/poly(d), so the learning result applies only at sufficiently small evolution times.The appendix gives an example where, at a certain longer time, the evolution unitary is proportional to identity and the unknown coefficient cannot be determined.Source: §A.2 · p. 49

B Algorithm for parameter learning of Markov random fields

This appendix gives an algorithm for parameter learning in Markov random fields with known interaction structure. It estimates conditional probabilities and uses them to recover the interaction coefficients, with sample and runtime bounds depending on model parameters.

B Algorithm for parameter learning of Markov random fields

  • The parameter-learning setting assumes the MRF interaction hypergraph is known, and uses maximum degree d and average-order parameter L to describe it.The Gibbs distribution is represented using interaction coefficients λ_S for hyperedges S.Source: B Algorithm for parameter learning of… · p. 50
  • Given samples from an MRF, the algorithm estimates the coefficients to ℓ∞ error ε with probability at least 1 − δ using T = Θ(exp(8βLd^2 + 2Ld) · 1/(β^2ε^2) · log(N/δ)) samples.The stated runtime is O(TN(Ld^2 + d^2d)).Source: B Algorithm for parameter learning of… · p. 51
  • For each vertex, the method estimates its conditional probability given its neighbors, which is expressed through a sigmoid of the local interaction function.The resulting estimates of the local functions are then used to recover the interaction coefficients.Source: B Algorithm for parameter learning of… · p. 51
  • Coefficient recovery averages the estimated local function over selected coordinates to isolate the target interaction parameter.The construction chooses disjoint coordinate sets Nin and Nout to separate the target hyperedge from other incident terms.Source: B Algorithm for parameter learning of… · pp. 51–52
  • Conditional probabilities are estimated from empirical joint and marginal event probabilities, with a lower bound on event probabilities controlling the sampling requirement.The argument applies relative-error estimation and a union bound across the required conditional probabilities.Source: B Algorithm for parameter learning of… · p. 52
Loading 2108.04842v3…