Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2212.03014 · Physical Review X

Lower Bounds on Ground-State Energies of Local Hamiltonians through the Renormalization Group

Ilya Kull, Norbert Schuch, Benjamin Dive, Miguel Navascués

Published Apr 9, 2024• 41 citations
arXivHTMLPDF

Abstract

Given a renormalization scheme, we show how to formulate a tractable convex relaxation of the set of feasible local density matrices of a many-body quantum system. The relaxation is obtained by introducing a hierarchy of constraints between the reduced states of ever-growing sets of lattice sites. The coarse-graining maps of the underlying renormalization procedure serve to eliminate a vast number of those constraints, such that the remaining ones can be enforced with reasonable computational means. This process can be used to obtain rigorous lower bounds on the ground-state energy of arbitrary local Hamiltonians by performing a linear optimization over the resulting convex relaxation of reduced quantum states. The quality of the bounds crucially depends on the particular renormalization scheme, which must be tailored to the target Hamiltonian. We apply our method to 1D translation-invariant spin models, obtaining energy bounds comparable to those attained by optimizing over locally translation-invariant states of n≳100 spins. Beyond this demonstration, the general method can be applied to a wide range of other problems, such as spin systems in higher spatial dimensions, electronic structure problems, and various other many-body optimization problems, such as entanglement and nonlocality detection. Published by the American Physical Society 2024

DOI
10.1103/physrevx.14.021008

Related papers

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

Sheng-Ku Lin, Ricardo Rivera Cardoso, Roberto Bondesan

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.

quant-pharXiv:2609.40336•Oct 1, 2026•0 citations

Certifying Ground-State Properties of Many-Body Systems

Jie Wang, Jacopo Surace, Irénée Frérot +4 more

A ubiquitous problem in quantum physics is to understand the ground-state properties of many-body systems. Confronted with the fact that exact diagonalization quickly becomes impossible when increasing the system size, variational approaches are typically employed as a scalable alternative: Energy is minimized over a subset of all possible states and then different physical quantities are computed over the solution state. Despite remarkable success, rigorously speaking, all that variational methods offer are upper bounds on the ground-state energy. On the other hand, so-called relaxations of the ground-state problem based on semidefinite programming represent a complementary approach, providing lower bounds to the ground-state energy. However, in their current implementation, neither variational nor relaxation methods offer provable bound on other observables in the ground state beyond the energy. In this work, we show that the combination of the two classes of approaches can be used to derive certifiable bounds on the value of any observable in the ground state, such as correlation functions of arbitrary order, structure factors, or order parameters. We illustrate the power of this approach in paradigmatic examples of 1D and 2D spin- 1 / 2 Heisenberg models. To improve the scalability of the method, we exploit the symmetries and sparsity of the considered systems to reach sizes of hundreds of particles at much higher precision than previous works. Our analysis therefore shows how to obtain certifiable bounds on many-body ground-state properties beyond energy in a scalable way. Published by the American Physical Society 2024

arXiv:2310.05844•Physical Review X•Jul 11, 2024•32 citations

A variational lower bound on the ground state of a many-body system and the squaring parametrization of density matrices

F. Uskov, O. Lychkovskiy

A variational upper bound on the ground state energy E gs of a quantum system, E gs ⩽ 〈Ψ| H |Ψ〉, is well-known (here H is the Hamiltonian of the system and Ψ is an arbitrary wave function). Much less known are variational lower bounds on the ground state. We consider one such bound which is valid for a many-body translation-invariant lattice system. Such a lattice can be divided into clusters which are identical up to translations. The Hamiltonian of such a system can be written as , where a term H i is supported on the i 'th cluster. The bound reads , where is some wisely chosen set of reduced density matrices of a single cluster. The implementation of this latter variational principle can be hampered by the difficulty of parameterizing the set , which is a necessary prerequisite for a variational procedure. The root cause of this difficulty is the nonlinear positivity constraint ρ > 0 which is to be satisfied by a density matrix. The squaring parametrization of the density matrix, ρ = τ 2 /tr τ 2 , where τ is an arbitrary (not necessarily positive) Hermitian operator, accounts for positivity automatically. We discuss how the squaring parametrization can be utilized to find variational lower bounds on ground states of translation-invariant many-body systems. As an example, we consider a one-dimensional Heisenberg antiferromagnet.

arXiv:1902.09246•Journal of Physics Conference Series•Feb 1, 2019•9 citations

Lower bounds for ground states of condensed matter systems

Tillmann Baumgratz, Martin Bodo Plenio

Standard variational methods tend to obtain upper bounds on the ground state energy of quantum many-body systems. Here we study a complementary method that determines lower bounds on the ground state energy in a systematic fashion, scales polynomially in the system size and gives direct access to correlation functions. This is achieved by relaxing the positivity constraint on the density matrix and replacing it by positivity constraints on moment matrices, thus yielding a semi-definite programme. Further, the number of free parameters in the optimization problem can be reduced dramatically under the assumption of translational invariance. A novel numerical approach, principally a combination of a projected gradient algorithm with Dykstra's algorithm, for solving the optimization problem in a memory-efficient manner is presented and a proof of convergence for this iterative method is given. Numerical experiments that determine lower bounds on the ground state energies for the Ising and Heisenberg Hamiltonians confirm that the approach can be applied to large systems, especially under the assumption of translational invariance.

arXiv:1106.5275•New Journal of Physics•Feb 13, 2012•53 citations

Classical simulation of quantum many-body systems

Yichen Huang

Classical simulation of quantum many-body systems is in general a challenging problem for the simple reason that the dimension of the Hilbert space grows exponentially with the system size. In particular, merely encoding a generic quantum many-body state requires an exponential number of bits. However, condensed matter physicists are mostly interested in local Hamiltonians and especially their ground states, which are highly non-generic. Thus, we might hope that at least some physical systems allow efficient classical simulation.Starting with one-dimensional (1D) quantum systems (i.e., the simplest nontrivial case), the first basic question is: Which classes of states have efficient classical representations? It turns out that this question is quantitatively related to the amount of entanglement in the state, for states with ``little entanglement'' are well approximated by matrix product states (a data structure that can be manipulated efficiently on a classical computer). At a technical level, the mathematical notion for ``little entanglement'' is area law, which has been proved for unique ground states in 1D gapped systems. We establish an area law for constant-fold degenerate ground states in 1D gapped systems and thus explain the effectiveness of matrix-product-state methods in (e.g.) symmetry breaking phases. This result might not be intuitively trivial as degenerate ground states in gapped systems can be long-range correlated.Suppose an efficient classical representation exists. How can one find it efficiently? The density matrix renormalization group is the leading numerical method for computing ground states in 1D quantum systems. However, it is a heuristic algorithm and the possibility that it may fail in some cases cannot be completely ruled out. Recently, a provably efficient variant of the density matrix renormalization group has been developed for frustration-free 1D gapped systems. We generalize this algorithm to all (i.e., possibly frustrated) 1D gapped systems. Note that the ground-state energy of 1D gapless Hamiltonians is computationally intractable even in the presence of translational invariance.It is tempting to extend methods and tools in 1D to two and higher dimensions (2+D), e.g., matrix product states are generalized to tensor network states. Since an area law for entanglement (if formulated properly) implies efficient matrix product state representations in 1D, an interesting question is whether a similar implication holds in 2+D. Roughly speaking, we show that an area law for entanglement (in any reasonable formulation) does not always imply efficient tensor network representations of the ground states of 2+D local Hamiltonians even in the presence of translational invariance. It should be emphasized that this result does not contradict with the common sense that in practice quantum states with more entanglement usually require more space to be stored classically; rather, it demonstrates that the relationship between entanglement and efficient classical representations is still far from being well understood.Excited eigenstates participate in the dynamics of quantum systems and are particularly relevant to the phenomenon of many-body localization (absence of transport at finite temperature in strongly correlated systems). We study the entanglement of excited eigenstates in random spin chains and expect that its singularities coincide with dynamical quantum phase transitions. This expectation is confirmed in the disordered quantum Ising chain using both analytical and numerical methods.Finally, we study the problem of generating ground states (possibly with topological order) in 1D gapped systems using quantum circuits. This is an interesting problem both in theory and in practice. It not only characterizes the essential difference between the entanglement patterns that give rise to trivial and nontrivial topological order, but also quantifies the difficulty of preparing quantum states with a quantum computer (in experiments).

•Jan 1, 2015•19 citations

Lower bounds to variational problems with guarantees

Jens Eisert

Variational methods play an important role in the study of quantum many-body problems, both in the flavor of classical variational principles based on tensor networks as well as of quantum variational principles in near-term quantum computing. This work stresses that for translationally invariant lattice Hamiltonians with periodic boundary conditions, one can easily derive efficiently computable lower bounds to ground state energies that can and should be compared with variational principles providing upper bounds. As small technical results, it is shown that (i) the Anderson bound and a (ii) common hierarchy of semidefinite relaxations both provide approximations with performance guarantees that scale as a constant in the energy density for cubic lattices. (iii) Also, the Anderson bound is systematically improved as a hierarchy of semidefinite relaxations inspired by the quantum marginal problem.

arXiv:2301.06142•Physical Review A•Jan 6, 2026•12 citations
Given a renormalization scheme, we show how to formulate a tractable convex relaxation of the set of feasible local density matrices of a many-body quantum system. The relaxation is obtained by introducing a hierarchy of constraints between the reduced states of ever-growing sets of lattice sites. The coarse-graining maps of the underlying renormalization procedure serve to eliminate a vast number of those constraints, such that the remaining ones can be enforced with reasonable computational means. This process can be used to obtain rigorous lower bounds on the ground-state energy of arbitrary local Hamiltonians by performing a linear optimization over the resulting convex relaxation of reduced quantum states. The quality of the bounds crucially depends on the particular renormalization scheme, which must be tailored to the target Hamiltonian. We apply our method to 1D translation-invariant spin models, obtaining energy bounds comparable to those attained by optimizing over locally translation-invariant states of n≳100 spins. Beyond this demonstration, the general method can be applied to a wide range of other problems, such as spin systems in higher spatial dimensions, electronic structure problems, and various other many-body optimization problems, such as entanglement and nonlocality detection. Published by the American Physical Society 2024
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 O(n/ε2)\mathcal{O}(n/ε^2)O(n/ε2) and O(n/ε)\mathcal{O}(n/ε)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 O(1)\mathcal{O}(1)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.
A ubiquitous problem in quantum physics is to understand the ground-state properties of many-body systems. Confronted with the fact that exact diagonalization quickly becomes impossible when increasing the system size, variational approaches are typically employed as a scalable alternative: Energy is minimized over a subset of all possible states and then different physical quantities are computed over the solution state. Despite remarkable success, rigorously speaking, all that variational methods offer are upper bounds on the ground-state energy. On the other hand, so-called relaxations of the ground-state problem based on semidefinite programming represent a complementary approach, providing lower bounds to the ground-state energy. However, in their current implementation, neither variational nor relaxation methods offer provable bound on other observables in the ground state beyond the energy. In this work, we show that the combination of the two classes of approaches can be used to derive certifiable bounds on the value of any observable in the ground state, such as correlation functions of arbitrary order, structure factors, or order parameters. We illustrate the power of this approach in paradigmatic examples of 1D and 2D spin- 1 / 2 Heisenberg models. To improve the scalability of the method, we exploit the symmetries and sparsity of the considered systems to reach sizes of hundreds of particles at much higher precision than previous works. Our analysis therefore shows how to obtain certifiable bounds on many-body ground-state properties beyond energy in a scalable way. Published by the American Physical Society 2024
A variational upper bound on the ground state energy E gs of a quantum system, E gs ⩽ 〈Ψ| H |Ψ〉, is well-known (here H is the Hamiltonian of the system and Ψ is an arbitrary wave function). Much less known are variational lower bounds on the ground state. We consider one such bound which is valid for a many-body translation-invariant lattice system. Such a lattice can be divided into clusters which are identical up to translations. The Hamiltonian of such a system can be written as , where a term H i is supported on the i 'th cluster. The bound reads , where is some wisely chosen set of reduced density matrices of a single cluster. The implementation of this latter variational principle can be hampered by the difficulty of parameterizing the set , which is a necessary prerequisite for a variational procedure. The root cause of this difficulty is the nonlinear positivity constraint ρ > 0 which is to be satisfied by a density matrix. The squaring parametrization of the density matrix, ρ = τ 2 /tr τ 2 , where τ is an arbitrary (not necessarily positive) Hermitian operator, accounts for positivity automatically. We discuss how the squaring parametrization can be utilized to find variational lower bounds on ground states of translation-invariant many-body systems. As an example, we consider a one-dimensional Heisenberg antiferromagnet.
Standard variational methods tend to obtain upper bounds on the ground state energy of quantum many-body systems. Here we study a complementary method that determines lower bounds on the ground state energy in a systematic fashion, scales polynomially in the system size and gives direct access to correlation functions. This is achieved by relaxing the positivity constraint on the density matrix and replacing it by positivity constraints on moment matrices, thus yielding a semi-definite programme. Further, the number of free parameters in the optimization problem can be reduced dramatically under the assumption of translational invariance. A novel numerical approach, principally a combination of a projected gradient algorithm with Dykstra's algorithm, for solving the optimization problem in a memory-efficient manner is presented and a proof of convergence for this iterative method is given. Numerical experiments that determine lower bounds on the ground state energies for the Ising and Heisenberg Hamiltonians confirm that the approach can be applied to large systems, especially under the assumption of translational invariance.
Classical simulation of quantum many-body systems is in general a challenging problem for the simple reason that the dimension of the Hilbert space grows exponentially with the system size. In particular, merely encoding a generic quantum many-body state requires an exponential number of bits. However, condensed matter physicists are mostly interested in local Hamiltonians and especially their ground states, which are highly non-generic. Thus, we might hope that at least some physical systems allow efficient classical simulation.Starting with one-dimensional (1D) quantum systems (i.e., the simplest nontrivial case), the first basic question is: Which classes of states have efficient classical representations? It turns out that this question is quantitatively related to the amount of entanglement in the state, for states with ``little entanglement'' are well approximated by matrix product states (a data structure that can be manipulated efficiently on a classical computer). At a technical level, the mathematical notion for ``little entanglement'' is area law, which has been proved for unique ground states in 1D gapped systems. We establish an area law for constant-fold degenerate ground states in 1D gapped systems and thus explain the effectiveness of matrix-product-state methods in (e.g.) symmetry breaking phases. This result might not be intuitively trivial as degenerate ground states in gapped systems can be long-range correlated.Suppose an efficient classical representation exists. How can one find it efficiently? The density matrix renormalization group is the leading numerical method for computing ground states in 1D quantum systems. However, it is a heuristic algorithm and the possibility that it may fail in some cases cannot be completely ruled out. Recently, a provably efficient variant of the density matrix renormalization group has been developed for frustration-free 1D gapped systems. We generalize this algorithm to all (i.e., possibly frustrated) 1D gapped systems. Note that the ground-state energy of 1D gapless Hamiltonians is computationally intractable even in the presence of translational invariance.It is tempting to extend methods and tools in 1D to two and higher dimensions (2+D), e.g., matrix product states are generalized to tensor network states. Since an area law for entanglement (if formulated properly) implies efficient matrix product state representations in 1D, an interesting question is whether a similar implication holds in 2+D. Roughly speaking, we show that an area law for entanglement (in any reasonable formulation) does not always imply efficient tensor network representations of the ground states of 2+D local Hamiltonians even in the presence of translational invariance. It should be emphasized that this result does not contradict with the common sense that in practice quantum states with more entanglement usually require more space to be stored classically; rather, it demonstrates that the relationship between entanglement and efficient classical representations is still far from being well understood.Excited eigenstates participate in the dynamics of quantum systems and are particularly relevant to the phenomenon of many-body localization (absence of transport at finite temperature in strongly correlated systems). We study the entanglement of excited eigenstates in random spin chains and expect that its singularities coincide with dynamical quantum phase transitions. This expectation is confirmed in the disordered quantum Ising chain using both analytical and numerical methods.Finally, we study the problem of generating ground states (possibly with topological order) in 1D gapped systems using quantum circuits. This is an interesting problem both in theory and in practice. It not only characterizes the essential difference between the entanglement patterns that give rise to trivial and nontrivial topological order, but also quantifies the difficulty of preparing quantum states with a quantum computer (in experiments).
Variational methods play an important role in the study of quantum many-body problems, both in the flavor of classical variational principles based on tensor networks as well as of quantum variational principles in near-term quantum computing. This work stresses that for translationally invariant lattice Hamiltonians with periodic boundary conditions, one can easily derive efficiently computable lower bounds to ground state energies that can and should be compared with variational principles providing upper bounds. As small technical results, it is shown that (i) the Anderson bound and a (ii) common hierarchy of semidefinite relaxations both provide approximations with performance guarantees that scale as a constant in the energy density for cubic lattices. (iii) Also, the Anderson bound is systematically improved as a hierarchy of semidefinite relaxations inspired by the quantum marginal problem.