⚛️ quantum physics

Circuit complexity lower bounds for quantum spin glasses

This paper establishes that preparing near-optimal ground states for random quantum $p$ -spin glasses requires circuits with depth growing logarithmically with system size or exceeding any fixed depth, thereby demonstrating that shallow circuits cannot generate the necessary entanglement to close the energy gap between product states and the optimum.

Original authors: Omar Al-Ghattas, David Gamarnik

Published 2026-07-17

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Omar Al-Ghattas, David Gamarnik

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 build a house. In the world of classical computing, building a house is like arranging furniture: you can move a chair from the kitchen to the living room with a single, simple push. It's fast, easy, and doesn't require any magic. But in the quantum world, things are different. Here, the "furniture" isn't just sitting there; it's made of mist that can be in two rooms at once, and the walls themselves can be connected in ways that defy normal logic. This field, known as quantum information theory, asks a big question: How hard is it to build a specific, complex quantum state? We call this "circuit complexity." It's like asking, "What is the shortest, simplest set of instructions needed to assemble this intricate quantum puzzle?"

Why does this matter? Because the universe seems to love complexity. Some theories suggest that the growth of these complex quantum states is linked to the growth of "wormholes" in space-time, the mysterious tunnels connecting distant parts of the universe. If we can figure out how hard it is to build these states, we might learn something profound about the nature of reality itself. However, there's a catch. While we know that random quantum states are incredibly hard to build (requiring an exponential number of steps), we don't know much about the states that nature actually produces, like the "ground states" of certain random quantum systems. These are the lowest-energy, most stable configurations of a system, and figuring out how to build them is a central challenge.

This paper tackles that challenge by looking at a specific type of quantum system called a "quantum $p$ -spin glass." Think of this system as a giant, chaotic game of "connect the dots" played with quantum particles. The rules are random: particles interact in groups of $p$ (where $p$ is a fixed number like 3, 4, or 5), and the strength of their connection is determined by a roll of the dice. The goal is to find the arrangement of these particles that gives the system the lowest possible energy (or highest, depending on how you count). The authors ask a very specific question: Can a simple, shallow quantum circuit—a machine with very few layers of operations—build a state that is almost as good as the best possible arrangement?

The answer, according to this paper, is a resounding no.

The researchers prove that for these random quantum spin glasses, you cannot cheat your way to a near-perfect solution with a simple machine. They show that the "entanglement" (the spooky, deep connection between particles) required to reach the best energy levels is too complex to be created by shallow circuits. Even if you give the circuit a massive number of extra helper particles (called "ancillas") to work with, it still fails.

Here is the breakdown of their findings:

The "Product State" Limit: First, they establish that if you don't use any entanglement at all (just simple, independent particles), you can only reach a certain low level of energy. It's like trying to build a skyscraper out of unconnected bricks; it just won't hold up.
The Shallow Circuit Failure: They then prove that even if you allow the circuit to create some entanglement, as long as the circuit is "shallow" (meaning it has a depth that grows only logarithmically with the number of particles, or even just a fixed number of layers), it still cannot beat the simple, unentangled limit.
The Two Scenarios: They looked at two different versions of this game. In the first, where every particle interacts with many others (a dense network), they proved that any circuit trying to get close to the best energy must be at least logarithmic in depth (growing like $\log n$ ). In the second, where particles only interact with a few neighbors (a sparse network), they proved that for any fixed depth you choose, if you make the system large enough and the interactions strong enough, a circuit of that depth simply cannot do the job.

The authors are very sure of this. They didn't just simulate it on a computer; they provided a mathematical proof. They ruled out the possibility that a simple, shallow circuit could prepare these near-ground states. Their work suggests that the "magic" required to solve these random quantum puzzles is inherently deep and complex, opening a new path to understanding why some quantum states are so hard to create, even for the most powerful quantum computers we can imagine.

Technical Summary: Circuit Complexity Lower Bounds for Quantum Spin Glasses

Problem Statement
This paper investigates the circuit complexity of preparing near-ground states for quantum $p$ -spin glasses. These are random Hamiltonians where interaction terms act on $p$ -tuples of qubits via Pauli strings. A central question in quantum information theory is whether physically natural families of states, such as ground states of succinctly described Hamiltonians, require high circuit complexity (specifically, high depth) to prepare.

Recent work established that for quantum $p$ -spin glasses, the optimal energy is strictly separated from the best energy achievable by unentangled (product) states. However, it remained unresolved whether shallow circuits (e.g., constant depth or logarithmic depth) could generate sufficient entanglement to bridge this "product-state gap." This paper addresses whether such shallow circuits can prepare states with energy close to the ground state optimum.

Methodology
The authors employ a probabilistic approach, recasting state-preparation lower bounds as the uniform control of Gaussian processes indexed by shallow quantum circuits. The core technical strategy involves decomposing the energy of a circuit-prepared state into two components:

A Product-Like Term ( $X_0$ ): Determined solely by the one-qubit marginals of the state. This term is bounded above by the product-state optimum, regardless of circuit depth.
A Residual Term ( $R$ ): Captures the non-product, entangled $p$ -point correlations.

The authors argue that for shallow circuits, the residual term is asymptotically negligible compared to the ground-state energy scale. The proof relies on three main technical pillars:

Backward Supports and Dependency Graphs: The authors define the "backward support" of an output qubit as the set of input qubits that can influence it after tracing the circuit backward. They construct a dependency graph where vertices are qubits and edges exist if their backward supports overlap. A key observation is that if the qubits involved in a $p$ -spin interaction form an independent set in this dependency graph, the corresponding $p$ -point expectation factorizes, causing the residual coefficient to vanish.
Variance Reduction: Due to the locality of shallow circuits, the variance of the residual process is significantly smaller than that of the raw energy. Specifically, while the raw normalized energy has variance of order $1/n$ , the normalized residual has variance of order $2^D/n^2$ (where $D$ is the circuit depth).
Entropy and Covering Bounds: To control the supremum of the residual process over all possible circuits, the authors derive uniform entropy bounds for the class of depth- $D$ circuits. Crucially, they handle the presence of an arbitrary number of ancilla qubits ( $r$ ) by "pruning" the circuit to the joint backward support of the physical output qubits and relabeling active ancillas into a canonical block. This ensures the covering numbers are independent of $r$ .

These bounds are applied across three regimes of the random Hamiltonian:

Mean-Field: All possible $p$ -tuples are present.
Growing-Average-Degree Diluted: A sparse hypergraph where the average degree grows with $n$ .
Bounded-Average-Degree Diluted: A sparse hypergraph where the average degree is bounded (linear number of terms).

Key Contributions and Results
The paper establishes circuit-depth lower bounds for near-ground state preparation in all three regimes, uniformly over the number of ancilla qubits:

Logarithmic Depth Lower Bound (Mean-Field and Growing-Average-Degree):
For sufficiently large fixed $p$ , any circuit preparing an $n$ -qubit state with normalized energy within a fixed positive constant of the optimum must have depth at least $\Omega_p(\log n)$ . This holds even if the circuit uses an arbitrary number of ancillas. The proof shows that for depths $D \leq \delta \log n$ , the residual energy is too small to close the gap between the product-state energy and the ground-state energy.
Fixed-Depth Obstruction (Bounded-Average-Degree):
In the regime where the average degree is bounded (linear number of terms), the paper proves a fixed-depth obstruction. For every fixed depth $D$ , there exists a sufficiently large degree prefactor $\zeta$ such that no depth- $D$ circuit (even with arbitrary ancillas) can prepare a near-ground state with high probability. The probability of success tends to zero in the iterated limit $n \to \infty$ followed by $\zeta \to \infty$ .
Uniformity over Ancillas:
A significant technical contribution is the proof that these lower bounds hold uniformly for any number of ancilla qubits. Previous counting arguments often failed to provide meaningful depth bounds when the number of ancillas was large relative to the system size; the pruning and relabeling technique overcomes this limitation.

Significance and Connection to NLTS
The authors position their results as a probabilistic route to the No Low-Energy Trivial States (NLTS) problem.

Contrast with Code-Based NLTS: Previous breakthroughs (e.g., Anshu, Breuckmann, and Nirkhe [6]) proved NLTS for Hamiltonians constructed from quantum LDPC codes. These constructions rely on commuting local terms, frustration-free ground spaces, and specific code-theoretic structures (isoperimetric properties).
Random, Non-Commuting Setting: In contrast, the Hamiltonians studied here are random, generally non-commuting, and lack a known efficient preparation procedure. The obstruction arises from the interplay between spin-glass disorder and the limited light-cones of shallow circuits, rather than code geometry.
Implications: The results provide a full (rather than merely combinatorial) NLTS-type obstruction for quantum spin-glass Hamiltonians in the mean-field and growing-average-degree regimes. In the bounded-average-degree regime, they provide a fixed-depth obstruction that approaches the full NLTS property as the degree prefactor increases.

The paper concludes by conjecturing that near-ground states of quantum $p$ -spin glasses cannot be prepared by polynomial-size circuits, even with arbitrary ancillas, though proving this would require techniques beyond the current scope, potentially relating to the separation of BQP and QMA.

More like this