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

AI summary

Overview

Research area: Quantum many-body physics, convex relaxation hierarchies, semidefinite programming, and message-passing algorithms for estimating ground-state energies.

Technical level: Advanced. The paper assumes familiarity with density matrices, reduced density matrices, quantum Hamiltonians, semidefinite programs, duality, and message passing.

Scope: The paper develops local relaxation hierarchies for quantum ground-state energies, proves exactness and convergence guarantees for restricted Hamiltonian families, and introduces highly parallelisable message-passing algorithms with runtime bounds and numerical benchmarks.

What This Paper Is About

Estimating the ground-state energy of a quantum many-body system is a central but computationally hard problem: for general local Hamiltonians, even inverse-polynomial precision is QMA-complete. Convex relaxation hierarchies provide polynomial-time classical lower bounds by replacing global quantum consistency with local consistency of reduced density matrices, but these methods are often solved as black-box semidefinite programs and have few efficiency guarantees. This paper studies local relaxation hierarchies, proves when they are exact or rapidly convergent, and derives specialised message-passing algorithms that exploit their local structure.

Key Contributions

1. Exactness on trees for commuting Hamiltonians. The authors show that the first level of the hierarchy, based on local consistency of pairwise reduced density matrices, is exact for 2-local commuting Hamiltonians on trees. The optimal marginals are consistent with a global quantum Markov network ground state.

2. Exponential convergence for weakly interacting chains. For short-range perturbations of separable Hamiltonians on a chain with a unique gapped ground state, the level-(t) hierarchy defined by locally consistent density matrices on intervals of size (t) converges exponentially fast in (t) to the exact ground-state energy. This yields a classical polynomial-time and polynomial-space algorithm for this setting.

3. Two message-passing algorithms. The authors derive a subgradient method and a Nesterov-type accelerated gradient method applied to an entropy-smoothed objective. For any fixed level of the local hierarchy on bounded-degree graphs, these run in (\mathcal{O}(n/\epsilon^{2})) and (\mathcal{O}(n/\epsilon)) time, respectively, where (\epsilon) is the precision for the relaxed ground-state energy per site. The bounds assume that optimal messages have (\mathcal{O}(1)) norm, a condition observed in experiments.

4. Benchmarks and open-source library. The message-passing algorithms are benchmarked across different quantum Hamiltonians, lattice geometries, and relaxation levels, and compared with standard convex optimisation solvers such as CVXPY. The library is released at github.com/rick1924/gse-message-passing.

Main Findings

• Level-one exactness on trees: For a commuting Hamiltonian (H=\sum_{(i,j)\in E}h_{i,j}) on a tree of qudits with local dimension (d), the relaxation (f_{1}^{*}=\min_{\mu\in\mathbb{L}(T)}\sum_{(i,j)\in E}\langle \mu_{i,j},h_{i,j}\rangle) yields the exact ground-state energy. The optimal reduced density matrices are consistent with a global quantum Markov network ground state.

• Simpler alternative to prior algorithms: This provides an alternative proof of an efficient algorithm by Aharonov, Arad, and Irani for such Hamiltonians. The authors argue their method is simpler, does not require computing local subspace decompositions, and returns local marginals rather than an efficient global state representation. The local marginals suffice for computing expectations of local observables.

• Bridge to quantum Markov networks: The paper proves that on a tree (T), the Petz-iterable locally consistent marginal set equals the marginal set restricted to quantum Markov networks: (\mathbb{L}{\mathrm{PI}}(T)=\mathbb{M}{\mathrm{QMN}}(T)). This equality underpins the exactness result.

• Hierarchy of lower bounds: The level-(t) local consistency sets (\mathbb{L}{t}) give lower bounds (f{t}^{}) satisfying (E_{0}=f_{n}^{}\geq\cdots\geq f_{0}^{}). The zeroth level (f_{0}^{}) equals the Anderson bound (\sum_{i}\lambda_{\min}(h_{i})). For any constant (t), the relaxation is a polynomial-size semidefinite program with matrices of size (d^{t}\times d^{t}), solvable to (\epsilon)-precision in (\mathrm{poly}(n,\log(1/\epsilon))) time.

• Simple exact cases: The relaxation is trivially tight for frustration-free Hamiltonians at any (t\geq 1), and for Hamiltonians diagonal in a fixed product basis on a tree, where the classical marginal and locally consistent sets coincide.

• Approximately commuting qubits on trees: Combining the exactness result with a rounding result of Faisal, Natarajan, and Poremba gives an (\mathcal{O}(m\epsilon^{1/6}))-approximation to the ground-state energy for 2-local qubit Hamiltonians whose terms approximately commute and whose interaction graph is a tree. The rounding preserves locality and the interaction graph.

• Exponential convergence on chains: For weak perturbations of separable Hamiltonians on a chain with a unique gapped ground state, the interval-based hierarchy converges exponentially fast in the interval size (t). The authors stress that this is not the first efficient classical algorithm for this regime, since cluster expansion already gives one in any dimension; rather, it is a validity guarantee for local relaxation hierarchies. They expect the chain restriction to be a limitation of their proof strategy, not of the algorithm.

• Message-passing runtimes: On bounded-degree graphs, the subgradient and accelerated methods run in (\mathcal{O}(n/\epsilon^{2})) and (\mathcal{O}(n/\epsilon)) time for any fixed hierarchy level, assuming (\mathcal{O}(1)) optimal message norms. The dependence on (n) is better than unstructured interior-point methods used by standard SDP solvers such as CVXPY, but worse in (1/\epsilon). The distributed nature allows further parallel speedups.

• Scope of the algorithms: The message-passing methods exploit the local structure of the relaxations and do not apply directly to the quantum Lasserre hierarchy or variational embeddings, which use global constraints. They also lack some distinctive features of belief propagation, such as a semi-ring structure and beliefs, and instead generalise classical message passing from prior work.

• Benchmarks: The numerical section reports benchmarks across different quantum Hamiltonians, lattice geometries, and relaxation levels, validating the theoretical predictions and comparing performance with CVXPY. Specific numerical values are not included in the provided excerpt.

Methodology in Plain English

The authors start from the exact variational formulation of the ground-state energy as a minimisation over all global density matrices. Because global consistency is computationally hard, they replace it with local consistency: optimise over reduced density matrices on edges and vertices, or on larger clusters, requiring only that overlapping marginals agree. Each fixed level gives a convex semidefinite program and therefore a polynomial-time lower bound.

To prove when this relaxation is tight, they connect locally consistent marginals to quantum Markov networks and use the structure lemma for commuting Hamiltonians. On trees, the first level is shown to produce marginals that can be glued into a valid global quantum Markov state, so no energy is lost. For weakly interacting chains, they analyse intervals of increasing size and prove that the error decreases exponentially with interval size.

To solve the relaxations efficiently, they derive the dual optimisation problems, whose structure is local. This enables message-passing updates between neighbouring regions. They propose a simple subgradient method and a faster Nesterov-type accelerated method applied to an entropy-smoothed objective. Finally, they implement the algorithms and benchmark them against CVXPY on several Hamiltonians and lattice geometries.

Why This Matters

This work strengthens the theoretical foundations of convex-relaxation lower bounds for quantum ground-state energies. It identifies restricted settings where a cheap relaxation is provably exact or exponentially convergent, and it provides a scalable, parallelisable alternative to black-box semidefinite programming for the local-consistency hierarchy. Rigorous lower bounds are important because variational methods such as tensor networks, quantum Monte Carlo, and the variational quantum eigensolver typically provide upper bounds; lower bounds are needed to certify how close an estimate is to the true ground-state energy.

Real-world applications include:

• Condensed-matter and materials modelling: Ground-state energies determine stability, structure, and low-temperature thermodynamic properties of materials.
• Quantum chemistry: Chemical reaction rates depend on ground-state energies of molecular systems.
• Quantum computing: Rigorous lower bounds can help validate and benchmark variational quantum algorithms and other near-term quantum simulations.
• Scientific computing and optimisation: The message-passing algorithms offer a distributed, GPU-friendly alternative to general-purpose SDP solvers for structured relaxation problems.

Industry relevance spans quantum-technology companies, materials and drug-discovery groups using quantum-chemical simulation, and developers of optimisation and scientific-computing software.

Future Directions

• Extend the convergence proof beyond chains. The authors expect the restriction to one-dimensional chains to be an artefact of their proof technique, so extending the exponential-convergence guarantee to higher dimensions is a natural next step.

• Clarify the tightness of higher hierarchy levels. The paper addresses the open question of how tight the (t)-th level is for restricted Hamiltonian families, but a general understanding of the relationship between hierarchy levels and between different relaxation hierarchies remains incomplete.

• Remove or justify the (\mathcal{O}(1)) message-norm assumption. The runtime guarantees rely on optimal messages having bounded norm, a condition observed numerically but not established in general.

• Use fast local relaxations to guide variational embeddings. As recently suggested, a cheap and fast algorithm can help identify how to set up clusters for more comprehensive and expensive quantum variational embeddings.

• Develop ground-state message passing further. The paper raises the question of whether a message-passing algorithm can operate directly on the ground state with strong guarantees, and notes that its algorithms differ from finite-temperature quantum belief propagation.

Target Audience

This paper is best suited to researchers and graduate students in quantum information and quantum many-body physics, convex optimisation and semidefinite programming, statistical physics and message passing, and quantum chemistry. It will also interest industry practitioners working on quantum algorithms, materials simulation, or scientific-computing solvers who need rigorous lower bounds and scalable relaxation methods. Readers should be comfortable with density-matrix formalism, duality, and basic semidefinite programming; the paper is not introductory.

Authors’ abstract

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/ε^2)$ and $\mathcal{O}(n/ε)$ time for any fixed level of the local hierarchy on bounded-degree graphs, where $ε$ 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.