⚛️ quantum physics

Lower bounds to variational problems with guarantees

This paper demonstrates that for translationally invariant lattice Hamiltonians with periodic boundary conditions, efficiently computable lower bounds to ground state energies—derived from the Anderson bound and semi-definite relaxations—can be systematically improved and provide performance guarantees that scale favorably with system size, complementing existing variational upper bounds.

Original authors: J. Eisert

Published 2026-02-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: J. Eisert

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the absolute lowest point in a vast, foggy mountain range. This mountain range represents a complex quantum system (like a material made of billions of atoms), and the "lowest point" is the system's ground state energy—the most stable, calmest state it can possibly be in.

For decades, scientists have used two main tools to find this bottom:

Variational Methods (The "Climber"): You pick a path, climb down, and say, "This is the lowest I can get!" This gives you an upper bound. You know the real bottom is at least this low, but you don't know if there's a deeper valley hidden in the fog.
The Problem: If you are using a classical computer, you can get very close. But if you are using a new Quantum Computer (a "Variational Quantum Eigensolver"), you might get stuck on a small hill and think you've reached the bottom, when you haven't. The danger is that you can't prove you found the true bottom; you only know you found a low point.

This paper by Jens Eisert is like handing the climber a "Depth Gauge" and a "Map of the Floor."

Here is the breakdown of the paper's main ideas using simple analogies:

1. The "Anderson Bound" (The Simple Floor)

The paper starts with a very old, simple trick called the Anderson Bound.

The Analogy: Imagine you want to know how deep a swimming pool is. Instead of diving to the bottom, you take a small, known-sized bucket (a "patch" of the system), measure how deep the water is in that bucket, and then use simple math to say, "The whole pool must be at least this deep."
The Result: This method is incredibly easy to program (it takes less than an hour!). It gives you a guaranteed lower bound. It tells you, "The true energy cannot be lower than X."
The Catch: It's not perfectly precise; it's off by a tiny, constant amount (like saying the pool is "at least 2 meters deep" when it's actually 2.05 meters). But for huge systems, that tiny error doesn't matter much.

2. The "Semi-Definite Relaxations" (The Tighter Net)

The paper then looks at more advanced mathematical tools called Semi-Definite Relaxations.

The Analogy: If the Anderson Bound is a loose net catching a fish, these methods are a tighter net. They use complex rules about how quantum particles relate to each other (like a puzzle) to squeeze the possible answers into a smaller range.
The Guarantee: The paper proves that even these complex methods have a "safety margin." They will always give you a number that is below the true answer, and the difference between their number and the true answer is also just a tiny, constant amount.
Why it matters: This means you can run these calculations on a classical computer and get a "certificate of quality." If your Quantum Computer says the energy is $E$ , and your classical lower bound says it's at least $E - 0.01$ , you know your Quantum Computer is very good. If the gap is huge, you know your Quantum Computer is struggling.

3. The "Improved Anderson Bound" (The Better Bucket)

The author takes the simple "bucket" method (Anderson) and makes it smarter using a concept called the Quantum Marginal Problem.

The Analogy: Instead of just looking at one bucket, imagine you look at two overlapping buckets. You check if the water level in the overlapping part makes sense. If the water levels don't match up logically, you know your guess is wrong.
The Result: This creates a hierarchy of better and better lower bounds. You can start with a simple check and keep adding more "overlapping buckets" to get a tighter and tighter estimate, all while keeping the math solvable on a normal computer.

The Big Picture: Why Should You Care?

The author calls these results "De-quantization" statements. Here is what that means in plain English:

The Challenge to Quantum Computers: People are excited about quantum computers solving these problems. But this paper says, "Wait a minute. We can actually calculate a very good 'floor' for the answer using a regular, old-school laptop in a few minutes."
The Benchmark: If a quantum computer wants to prove it is doing something useful, it can't just give an answer. It has to give an answer that is better than what a classical computer can easily prove is the minimum.
The Safety Net: For scientists using quantum computers, these lower bounds act as a "certificate of authenticity." They provide a rigorous way to say, "Yes, our quantum algorithm is working correctly, because our answer is safely above this mathematically proven floor."

Summary

Think of this paper as a quality control inspector for the future of quantum computing.

It shows that we can easily build a floor (lower bound) for the energy of quantum systems.
It proves that this floor is very close to the real answer (within a tiny, constant error).
It tells us that any quantum computer claiming to solve these problems must beat this simple, classical "floor" to be considered truly powerful.

In short: Don't just trust the quantum computer's guess; check it against the mathematically guaranteed floor.

1. Problem Statement

Variational methods are the standard approach for estimating ground state energies of quantum many-body systems, both in classical tensor network simulations and near-term quantum algorithms (Variational Quantum Eigensolvers, VQE). These methods optimize over a restricted family of quantum states to provide an upper bound to the ground state energy density ( $e_{min}$ ).

However, a critical limitation exists:

Lack of Certification: Standard variational approaches do not provide a certificate of accuracy. There is no guarantee on how close the computed upper bound is to the true ground state energy.
Quantum Advantage Threshold: For a quantum algorithm to demonstrate a genuine advantage over classical methods in estimating ground state energies, it must outperform classical lower bounds. If classical methods can easily provide a lower bound with a guaranteed error scaling as $O(1)$ (a constant independent of system size), quantum algorithms must achieve significantly better precision to be meaningful.

The paper addresses the need for efficiently computable lower bounds that come with rigorous performance guarantees, allowing for the certification of variational ansatzes.

2. Methodology

The author considers translationally invariant local Hamiltonians ( $H_N$ ) defined on $D$ -dimensional cubic lattices with periodic boundary conditions, where the Hamiltonian is a sum of nearest-neighbor terms:
$H_N = \sum_{j \in L} \tau_j(h)$

The paper employs three main methodological approaches to derive lower bounds:

A. The Anderson Bound

This is a simple lower bound derived from the triangle inequality of the operator norm. It involves decomposing the lattice into overlapping patches of size $m^D$ and analyzing the ground state energy of these finite patches with open boundary conditions.

B. Semi-Definite Relaxations (SDR)

The paper analyzes hierarchies of semi-definite relaxations used to find ground states.

Core Idea: The constraint that a quantum state $\rho$ must be positive semi-definite ( $\rho \geq 0$ ) is relaxed to a set of operators $\omega$ satisfying $\text{tr}(\omega O^\dagger O) \geq 0$ for a specific set of operators.
Formulation: The problem is cast as a semi-definite program (SDP) minimizing $\text{tr}(hX)$ subject to constraints reflecting local algebraic relations and translational invariance.

C. Improved Anderson Bound via Quantum Marginal Problem

To systematically improve the standard Anderson bound, the author relaxes the problem of finding the ground state of a larger patch ( $2m$ sites) using the quantum marginal problem.

Instead of solving for the exact ground state of a large patch (which is exponentially hard), the method relaxes the consistency conditions between the reduced density matrices of overlapping sub-regions.
This creates a hierarchy of semi-definite problems parameterized by an integer $s$ (the size of the overlap), where $s=m$ recovers the exact Anderson bound for the larger patch, and $s < m$ provides a hierarchy of tighter, efficiently computable bounds.

3. Key Contributions and Results

I. Performance Guarantee of the Anderson Bound

The paper proves that the Anderson bound provides an approximation to the asymptotic ground state energy density ( $e_{min}$ ) with an error that scales as $O(1/N)$ relative to the system size, or more precisely, the difference between the bound and the true energy density is bounded by a small constant that can be made arbitrarily small by increasing the patch size $m$ .

Proposition 1: For a cubic lattice, the Anderson bound $A(m, D)$ satisfies:
$A(m, D) \leq e_{min}$
$|e_{min} - A(m, D)| \leq \frac{D}{m}\|h\| - \lambda_{min}(h_m) \left[ \frac{1}{(m-1)^D} - \frac{1}{m^D} \right]$
Significance: The error term is independent of the total system size $N$ (it depends only on the patch size $m$ ). This means the bound is tight up to a constant error in the energy density, regardless of how large the system is.

II. Performance Guarantee of Semi-Definite Relaxations

The paper establishes that common hierarchies of semi-definite relaxations also provide lower bounds with similar guarantees.

Proposition 2: The solution $x_N$ to the semi-definite relaxation satisfies:
$x_N \leq e_{min}(H_N) \leq x_N + O(1)$
Mechanism: By relaxing the global positive semi-definiteness constraint to a local constraint on a fixed set of sites $T$ (independent of $N$ ), the optimization problem becomes size-independent. The error is bounded by a constant determined by the size of the support of the Hamiltonian terms.

III. Hierarchy of Improved Anderson Bounds

The author introduces a new hierarchy of bounds based on the quantum marginal problem.

Proposition 3: By solving a semi-definite optimization problem involving two density matrices ( $\omega$ and $\sigma$ ) with overlapping constraints, one obtains a sequence of bounds $x_{m,s}$ .
Result: As the overlap parameter $s$ increases from $1$ to $m$ , the lower bound becomes tighter, converging to the standard Anderson bound for a patch of size $2m$ . This allows for systematic improvement without the exponential cost of solving the full $2m$ -site problem.

4. Significance and Implications

Certification of Variational Methods: These results allow researchers to rigorously certify the quality of variational ansatzes (both classical tensor networks and quantum VQE). If a variational method yields an energy $E_{var}$ , comparing it to the lower bound $E_{lower}$ provides a guaranteed error bar: $E_{lower} \leq E_{true} \leq E_{var}$ .
"De-quantization" of Ground State Estimation: The paper argues that since classical computers can efficiently compute lower bounds with $O(1)$ error guarantees, any quantum algorithm claiming an advantage in estimating ground state energies must achieve a precision significantly better than this constant error. This places stringent demands on near-term quantum hardware.
Computational Efficiency: The proposed lower bounds are "elementary" and computationally cheap (polynomial in system size for fixed patch size $m$ ), requiring minimal programming effort compared to complex variational simulations.
Applicability: The methods apply to both bosonic and fermionic Hamiltonians and are relevant for models like the Sachdev-Ye-Kitaev (SYK) model.
Relation to Quantum PCP: The results do not contradict the Quantum PCP conjecture (which states that approximating ground state energy to within a constant fraction of the local terms is QMA-hard). Instead, they suggest that for cubic lattices with periodic boundaries, the constant error achievable by these classical bounds implies that the conjecture's hardness threshold may not be tight for this specific class of problems.

Conclusion

J. Eisert demonstrates that for translationally invariant lattice Hamiltonians, one can easily derive efficiently computable lower bounds to ground state energies that come with rigorous performance guarantees. These bounds scale as a constant in the system size, providing a benchmark against which both classical and quantum variational methods must be measured. This work serves as a "proof pocket" for variational quantum eigensolvers, pushing the community toward more reliable and quantitative quantum simulations.