PaperlayerView exact revision on arXiv

Source-linked AI summary

Local Relaxation Hierarchies for Quantum Ground State Energies: Convergence Guarantees and Message Passing Algorithms

Sheng-Ku Lin, Ricardo Rivera Cardoso, Roberto Bondesan

arXiv:2609.40336v1quant-phcs.DC

TL;DR

Ground-state energy estimation is hard in general, and efficient computation of accurate relaxation bounds remains challenging. This paper develops local-consistency hierarchies and message-passing algorithms, proving exactness for commuting Hamiltonians on trees and exponential convergence for a class of weakly perturbed chains. It also gives runtime guarantees for the algorithms under a bounded-message-norm assumption.

  • Problem

    Ground-state energy estimation is QMA-complete to inverse-polynomial precision even for local Hamiltonians, while scaling convex relaxation methods to large systems and accurate approximations is challenging.

    Source: §1 · p. 1

  • Method

    The paper develops local-consistency marginal hierarchies and two distributed message-passing algorithms for solving their relaxations.

    Source: §1 · p. 2, §1.1 · p. 3

  • Results

    The first level is exact for 2-local commuting Hamiltonians on trees, interval relaxations converge exponentially for weakly interacting gapped separable chains, and the two algorithms run in O(n/ϵ^2) and O(n/ϵ) time under the stated assumptions.

    Source: §1.1 · p. 3

  • Takeaways & Limitations

    The guarantees provide exact or convergent classical energy estimates in these restricted settings, alongside parallel algorithms for local relaxations on bounded-degree graphs.

    Source: §1.1 · p. 3

    The message-passing runtime bounds assume bounded-degree graphs and optimal messages of O(1) norm; the interval-hierarchy convergence result is limited to weakly interacting chains.

    Source: §1.1 · p. 3, §6 · p. 19

Abstract

from arXiv · show

Convex relaxation hierarchies provide lower bounds to the ground state energy of quantum many-body systems that can be computed in polynomial time on a classical computer, at any fixed hierarchy level. However, scaling these methods to large systems and accurate approximations remains challenging due to the computational cost of traditional solvers and the scarcity of efficiency guarantees. In this work, we develop local relaxation hierarchies and efficient, highly parallelisable message passing algorithms for estimating the relaxed ground state energies. We show that the first level of the hierarchy---based on local consistency of pairwise reduced density matrices---is exact for commuting Hamiltonians on trees. We further establish that another hierarchy, based on consistent intervals, converges exponentially fast in the interval size to the ground state energy for weak perturbations of separable Hamiltonians on a chain, thereby providing an efficient classical algorithm for these systems. Then, we introduce two variants of message passing algorithms that run in $\mathcal{O}(n/\epsilon^2)$ and $\mathcal{O}(n/\epsilon)$ time for any fixed level of the local hierarchy on bounded-degree graphs, where $\epsilon$ is the precision for the relaxed ground state energy per site. This assumes that the optimal messages have $\mathcal{O}(1)$ norm---a condition we observe in practical settings in our experiments. These algorithms are based on the subgradient method and the Nesterov-type accelerated gradient descent method applied to an entropy-smoothed objective. Finally, we benchmark the message passing algorithms across different quantum Hamiltonians, lattice geometries, and relaxation levels, validating the theoretical predictions and their potential to surpass standard convex optimisation solvers for this problem. We release the resulting library at github.com/rick1924/gse-message-passing.

1 Introduction

Ground-state energy estimation is computationally hard in general, motivating efficient relaxations that provide lower bounds. This work develops local-consistency hierarchies and message-passing algorithms, with guarantees for commuting Hamiltonians on trees and weakly interacting chains.

1 Introduction

  • Ground-state energy estimation is QMA-complete to inverse-polynomial precision even for local Hamiltonians, while lower bounds can help rigorously bound numerical estimates.The ground-state energy is the smallest eigenvalue of the Hamiltonian; the paper focuses on local relaxations that outer-bound the set of quantum states.Source: §1 · p. 1

1.1 Contributions and related work

  • The paper studies local-consistency relaxations, establishing convergence guarantees for restricted Hamiltonians and parallelizable message passing at fixed hierarchy levels.The contributions include tree exactness, exponential convergence for a class of chains, and two message-passing algorithms.Source: §1 · p. 2, §1.1 · p. 2, §1.2 · p. 3
  • For 2-local commuting Hamiltonians on trees, the first relaxation level is exact and recovers the ground-state energy in polynomial time.The result uses quantum Markov networks and the structure lemma for commuting Hamiltonians; it provides local marginals but not an efficient representation of the global state.Source: §1.1 · p. 3
  • For weakly interacting chains that perturb separable Hamiltonians with a unique, gapped ground state, the interval hierarchy converges exponentially in interval size.This gives a classical polynomial-time and polynomial-space algorithm in that setting; the result is presented as a guarantee for local relaxations, not the first efficient algorithm for the regime.Source: §1.1 · p. 3
  • On bounded-degree graphs, two message-passing algorithms run in O(n/ϵ^2) and O(n/ϵ) time at fixed hierarchy level, assuming optimal messages have O(1) norm.They use subgradients and Nesterov-type accelerated gradient descent on an entropy-smoothed objective; the paper reports verifying the norm condition numerically.Source: §1.1 · p. 3

1.2 Organisation

  • The paper proceeds from marginal sets and local relaxations to convergence guarantees, message-passing algorithms, and numerical comparisons with CVXPY.Most theorem proofs are placed in Appendix A.Source: §1.2 · pp. 3–4

2 Global and locally consistent marginals

The paper distinguishes globally consistent quantum marginals from efficiently described locally consistent ones, which can form outer bounds. It relates special tree restrictions through quantum Markov networks and builds higher-order and geometrically local relaxation hierarchies.

2.1 Marginal sets

  • Global consistency requires marginals to arise from a shared quantum state, a decision problem known to be QMA-complete; local consistency instead enforces consistency among marginals.The global marginal set is contained in the locally consistent set, which can therefore be a loose outer bound.Source: §2.1 · p. 4, §2.2 · p. 5
  • On trees, the paper proves that Petz-iterable locally consistent marginals equal marginals of quantum Markov network states.The proof uses decomposition and reconstruction properties for zero conditional mutual information and iterates the Petz recovery map through tree edges.Source: §2.1 · p. 5

2.2 Outer-bounds

  • Higher-order local consistency adds marginals on larger subsets, yielding nested outer bounds; at level t, the tuple and constraint counts scale as O(n^t).For constant t these sets have polynomial descriptions, but the scaling is unfavorable for large n.Source: §2.2 · pp. 5–6

3 Relaxations to the ground state energy problem

The section develops locally consistent marginal relaxations, then identifies settings where they are exact or converge efficiently. It also explains how geometrically local clusters form a hierarchy and why general accuracy can remain costly.

3.1 A hierarchy of relaxations

  • Locally consistent marginal relaxations lower-bound the ground-state energy by relaxing global consistency, and fixed-level instances are convex semidefinite programs with polynomially many constraints.The hierarchy can be tightened by increasing marginal support; the exact solution is recovered at full system size.Source: §3.1 · p. 6

3.1.1 Exact relaxations

  • For commuting 2-local Hamiltonians on a tree, the first-level pairwise relaxation yields the exact ground-state energy and marginals consistent with a global quantum Markov network state.The proof connects the optimizing marginals to that state structure through the Structure lemma for commuting Hamiltonians.Source: §3.1.1 · p. 7

3.2 Geometrically local hierarchies

  • Geometrically local hierarchies use connected clusters that grow by adjacent sites, ensuring nested relaxation sets while focusing marginal support on nearby sites.Increasing clusters arbitrarily need not produce nested sets; larger clusters spanning distant sites can capture local correlations less faithfully.Source: §3.2 · p. 8

3.3 Other bounds: exponential resource cost

  • In the general case, achieving epsilon accuracy per site requires t = ceil(1/epsilon), so time and memory grow exponentially in 1/epsilon.This scaling follows from the chain rounding argument under the stated bounded interaction-norm assumption.Source: §3.3 · p. 9
  • For fixed patch size, adding consistency between neighboring patches lowers the largest marginal size, but accuracy remains controlled by patch size and still costs exponentially in inverse precision.The construction converges to the larger-patch Anderson bound, not directly to the ground-state energy.Source: §3.3 · p. 9

3.4 Exponential convergence of the local hierarchy for weakly-interacting chains

  • For weak perturbations of separable Hamiltonians on a chain, interval hierarchies converge exponentially in interval size, giving polynomial time and space for energy estimation.The result assumes a unique, gapped ground state for the separable Hamiltonian; t = O(log(1/epsilon)) suffices for epsilon error per site.Source: §3.4 · p. 10

4 Distributed algorithm

This section develops distributed message-passing methods for optimizing dual objectives of two-local and higher-order relaxations, using subgradient descent and entropy-smoothed acceleration. It gives convergence and complexity guarantees under bounded-structure and bounded-optimal-message-norm assumptions, including an O(n/ϵ) arithmetic complexity for higher-order accelerated smoothing.

4.1 Two-local marginals

  • For node-and-edge marginals, partial dualization of compatibility constraints is exact by strong duality, and separability reduces the dual objective to local minimum-eigenvalue problems.The strictly feasible uniform marginals establish strong duality.Source: §4.1 · p. 11

4.1.1 Subgradient method

  • Each multiplier update uses only neighbor-local information and can run independently, with optimal marginals also produced as a byproduct.On bounded-degree graphs, O(1) optimal message norms yield O(1/ϵ²) subgradient iterations independently of system size n.Source: §4.1.1 · pp. 12–13

4.1.2 Accelerated smoothing method

  • For bounded-degree graphs with O(1) optimal message norms, entropy-smoothed Nesterov updates achieve error density ϵ in O(1/ϵ) iterations and O(n/ϵ) arithmetic.Smoothing replaces local ground-state subgradients with Gibbs states; the convergence bound splits the error between smoothing and optimization.Source: §4.1.2 · pp. 13–14

4.2 Higher-order marginals

  • For arbitrary cluster families, higher-order message passing assigns multipliers to hyperedge-to-subcluster consistency constraints; adjacent-level constraints suffice because others are implied.The construction generalizes the dual program to higher-order marginals.Source: §4.2 · pp. 14–15

4.2.1 Subgradient method

  • For bounded-degree hypergraphs with bounded maximum cluster size and O(1) optimal message norms, higher-order subgradient descent achieves error density ϵ in O(1/ϵ²) iterations independently of n.The guarantee also assumes bounded local incidence.Source: §4.2.1 · p. 16

4.2.2 Accelerated smoothing method

  • Higher-order accelerated smoothing replaces local augmented-Hamiltonian minimum eigenvalues with free-energy approximations and uses Nesterov acceleration to optimize the smoothed dual objective.The error-density budget is split equally between smoothing approximation and optimization error.Source: §4.2.2 · p. 16
  • O(n/ϵ) arithmetic complexity achieves target error density ϵ for bounded-degree hypergraphs with bounded cluster size and O(1) optimal message norms.The accelerated method requires O(1/ϵ) iterations, independently of system size n.Source: §4.2.2 · p. 17

4.3 Comparison between the subgradient and accelerated smoothing methods

  • The subgradient method’s iteration bound scales as O(1/ϵ^2), versus O(1/ϵ) for accelerated smoothing.Both methods have asymptotic per-iteration cost O(nd^3); accelerated smoothing’s higher-order cluster-size disadvantage is mild in most circumstances, while cases where subgradient iterations are cheaper remain unclear.Source: §4.3 · p. 17

5 Numerics

The numerical results favor geometrically local relaxations over full ones for random chains, show no visible size dependence in optimal multiplier norms, and generally favor the smooth method in practice. However, CVXPY currently outperforms the authors’ Python implementation on the tested problems.

5.1 Full vs. geometrically local relaxations

  • For random chains, Y4 improves on L3’s energy approximation and solves up to 8× faster; greater Hamiltonian symmetry reduces the difference between Lt and Yt.The comparison is relative to Y3 for the energy improvement, and the speed comparison is against CVXPY’s solve time.Source: §5.1 · p. 17, Figure 2 · p. 18

5.2 Size independence of the optimal Lagrange multiplier norm

  • Across the tested chain lengths and Hamiltonians, average optimal multiplier Frobenius norms show no visible correlation with system size.The tested models include isotropic and anisotropic Heisenberg, critical TFIM, and random Hamiltonians.Source: §5.2 · p. 17, Figure 3 · p. 18

5.3 Comparison of the subgradient and smooth methods

  • Numerical experiments cover accuracy targets ϵ from 0.02 to 0.002 across standard one-dimensional models and random Hamiltonians.Figure 4 plots iteration counts against ϵ for random and isotropic Heisenberg Hamiltonians; its random-Hamiltonian free-fit gives exponent 2.2, while the constrained quadratic fit has better R2.Source: §5.3 · p. 18, Figure 4 · p. 19
  • For standard Hamiltonians, the smooth method is better in practice; observed iteration exponents reach 2 for subgradient on random Hamiltonians and 0.8 for smoothing on random Hamiltonians.The paper reports that the smooth method’s observed exponents were about 0.5 for the other Hamiltonians; the theoretical iteration bounds scale as O(1/ϵ^2) and O(1/ϵ), respectively.Source: §5.3 · p. 18

5.4 Benchmark against CVXPY

  • CVXPY currently outperforms the authors’ Python implementation on the tested problems, despite under-the-hood solver optimizations.Further runtime optimization is left to future work.Source: §5.4 · pp. 18–19

6 Discussion and future work

The paper derives convergence guarantees for locally consistent marginal relaxations and complexity bounds for parallelizable message-passing algorithms. It identifies open extensions to exactness, convergence, and runtime, including the exponential cost of larger marginals.

6 Discussion and future work

  • The work derives convergence guarantees for locally consistent marginal relaxations and complexity bounds for highly parallelizable message-passing algorithms.The algorithms solve the relaxations; tensor-network messages and GPU implementation are discussed as future optimization directions.Source: §6 · p. 19
  • Whether higher hierarchy levels are exact for Hamiltonian classes beyond commuting Hamiltonians on trees remains open.Source: §6 · p. 19
  • Extending exponential convergence proofs for gapped weakly interacting chains to strongly interacting systems and higher dimensions remains future work.The paper identifies higher-dimensional block diagonalization as a possible direction.Source: §6 · p. 19
  • Marginal size grows exponentially with hierarchy level, producing exponentially growing runtime and memory costs in the algorithms.Tensor-network parameterizations are proposed as a possible route to reducing this burden.Source: §6 · p. 19
  • The algorithms’ runtime still needs optimization for successful benchmark comparisons against CVXPY.GPU implementation is identified as a promising route.Source: §6 · p. 19

A.1 Proof of Theorem 1

The proof relates locally consistent pairwise marginals on a tree to quantum Markov networks. It uses site-space decompositions and consistent sector labels to construct the global state required for the equivalence.

A.1 Proof of Theorem 1

  • At a star center, conditional independence of neighboring leaves permits successive Hilbert-space decompositions that separate the center’s sectors by neighboring sites.The proof repeatedly refines the remaining subspace by peeling off one leaf at a time.Source: §A.1 · p. 24
  • On a tree, the locally consistent marginal set LPI(T) equals the set MQMN(T) of quantum Markov network marginals.Source: §A.1 · p. 25
  • The reverse inclusion is established by iteratively applying the Petz map to locally consistent marginals to construct a global state.For the illustrated three-site reconstruction, the resulting state has the prescribed edge marginals.Source: §A.1 · p. 26
  • The decomposition yields sector marginals that can be combined on edges, while the classical sector labels are the remaining obstacle to a global state.Source: §A.1 · pp. 26–27
  • On trees, the junction-tree theorem supplies joint probabilities for those sector labels, enabling their consistent combination.The cited theorem is identified as the classical result establishing equality between Mc(T) and Lc(T).Source: §A.1 · p. 27

A.2 Proof of Theorem 2

This proof establishes that the local program for a commuting Hamiltonian on a tree yields the exact ground-state energy. At the optimum, the reduced density matrices are consistent with a global quantum Markov network ground state.

A.2 Proof of Theorem 2

  • For a commuting Hamiltonian on a tree, the optimization program yields the exact ground-state energy.The optimal reduced density matrices are consistent with a global quantum Markov network ground state.Source: §A.2 · p. 27
  • The proof uses the Structure lemma for commuting Hamiltonians to decompose the local Hilbert space at a bulk node.The neighboring Hamiltonian terms commute pairwise at that node.Source: §A.2 · p. 27
  • The two programs bound the exact energy from opposite directions: the first is a lower bound and the second an upper bound.The upper-bound program is linked to marginals of a global quantum Markov state.Source: §A.2 · p. 27

A.3 Proof of Theorem 3

This proof develops the interval hierarchy for a chain and uses it to establish Theorem 3 under the stated Hamiltonian assumptions. Its hierarchy uses locally consistent density matrices on intervals, with a system-size-independent range of sufficiently small perturbation parameter.

A.3 Proof of Theorem 3

  • The level-ℓ hierarchy optimizes over density matrices on intervals of size at most ℓ, subject to local consistency.The relaxation functional evaluates operators supported on such intervals and extends linearly to sums of interval-supported operators, including the Hamiltonian.Source: §A.3 · p. 28
  • For Hamiltonians satisfying the stated assumptions, Theorem 8 applies for 0 < t < t*, where t* is independent of system size.The theorem also specifies a positive function c(t) independent of system size.Source: §A.3 · p. 28
  • The proof proceeds by deriving a quasi-local sum-of-squares decomposition, extending the local relaxation functional, and then proving convergence.The theorem is stated for a Hamiltonian on a chain of qudits.Source: §A.3 · pp. 27–28

A.3.1 Quasi-local sum-of-squares decomposition

The proof block-diagonalizes the perturbed Hamiltonian and constructs a quasi-local sum-of-squares decomposition. Exponential control of truncation errors supports this construction, while a stated parameter condition yields a gap lower bound.

A.3.1 Quasi-local sum-of-squares decomposition

  • The proof reviews a unitary block-diagonalization result and uses it to construct a sum-of-squares decomposition of H − E0 1.The transformed Hamiltonian has ground state |Ω⟩ and the same ground-state energy as H.Source: §A.3.1 · pp. 28–29
  • The unitary U is a product of interval-supported gates, with O(n^2) intervals in the specified ordering.The construction assumes t is below an n-independent threshold for the quasi-locality bound.Source: §A.3.1 · pp. 28, 32
  • For β_i ≤ 1/2, the decomposition gives a gap of at least 1/2 for the transformed Hamiltonian and hence for the original Hamiltonian.The argument uses T_i = h_i − β_i q_i ⪰ 0 when β_i ≤ 1.Source: §A.3.1 · p. 29
  • Conjugating the positive terms by U yields quasi-local operators whose truncation error outside radius r is exponentially small in r.The proof invokes a Lieb-Robinson bound to establish this decay.Source: §A.3.1 · p. 30

A.3.2 Extension of local relaxation and hierarchy bound

This section extends the local relaxation functional to all operators while preserving its value on the hierarchy’s operator space. It uses this extension and bounds on its action under quasi-local conjugation to control the relaxation error and prove Theorem 3.

A.3.2 Extension of local relaxation and hierarchy bound

  • The extended functional agrees with the original relaxation functional on Vℓ, but is defined on all operators.The extension is needed because the sum-of-squares decomposition contains operators outside Vℓ.Source: §A.3.2 · pp. 32–33
  • The extension decomposes operators into support-interval components using projectors Δ[a,b].These projectors isolate traceless operator components whose support has endpoints a and b.Source: §A.3.2 · p. 33
  • The section establishes bounds on the extended functional for interval-supported operators and on positive operators of support size m ≤ ℓ/2.For the positive-operator bound, the proof chooses a truncation whose support fits within the hierarchy level.Source: §A.3.2 · pp. 33–34
  • These estimates are used to control the relaxation error, and the section concludes by proving Theorem 3.The proof bounds separate contributions using the estimates for general and shorter-support operators.Source: §A.3.2 · pp. 34–35

A.4 Proofs from Section 4

The proofs establish convergence guarantees for subgradient descent and accelerated optimization of an entropy-smoothed dual objective. They also relate the methods’ per-iteration work to local effective Hamiltonians.

A.4 Proofs from Section 4

  • With step size α = cϵ, where 0 < c < 1/∆G, Algorithm 1 has a sufficient iteration bound for target error density ϵ.The proof bounds subgradients using the maximum graph degree ∆G.Source: §A.4 · pp. 35–36
  • Algorithm 2’s convergence proof bounds total error by smoothing and accelerated-optimization errors, then selects β and the iteration count to meet target error density ϵ.The theorem specifies β = 2ΓG/(nϵ) and bLβ = βΛG/2.Source: §A.4 · pp. 38–39
  • Each accelerated iteration computes Gibbs states of local effective node and edge Hamiltonians, with O(d^3) arithmetic cost for d-dimensional matrices.The subgradient method instead samples ground-state eigenvectors of local effective Hamiltonians.Source: §A.4 · pp. 36, 39
Loading 2609.40336v1…