The Problem Nobody Solved (Until Now)
Quantum computers are notoriously fragile. The qubits at their heart lose their quantum properties in microseconds unless protected by quantum error correction—a set of techniques that encode information into highly entangled states of many physical qubits. For error correction to work, these encoded states must be difficult for random noise to create or destroy. In the language of complexity theory, they must be "nontrivial": not preparable by simple, shallow circuits. But proving that any natural quantum system actually produces such robust states has been a frustratingly elusive goal. In a paper posted to arXiv in July 2026, a team of researchers from multiple institutions has now provided a rigorous answer for one of the most natural random models: quantum spin glasses. They show that shallow circuits—the kind that near-term quantum devices can execute—are fundamentally incapable of preparing the low-energy states of these disordered systems. [arXiv:2607.14384]
The question at stake goes back to the No Low-Energy Trivial States (NLTS) conjecture, formulated by Michael Freedman and Matthew Hastings in 2013. They asked whether there exists a quantum Hamiltonian whose low-energy states are all nontrivial, meaning no constant-depth circuit can prepare them. Such a Hamiltonian would be a goldmine for quantum error correction, providing a natural substrate for fault tolerant logical qubits. Despite progress on code-based constructions, the question remained open for physically motivated random models. The new paper cracks this open by proving that quantum p-spin glasses—random Hamiltonians with interactions among p qubits—exhibit precisely this kind of obstruction. The result doesn't just say that some spin glasses are hard; it shows that hardness is the rule, not the exception.
The Core Finding
The paper studies the circuit complexity of preparing states that come close to the ground energy of a quantum p-spin glass. In 2024, Anschuetz, Gamarnik, and Kiani proved that product states—the simplest possible quantum states with zero entanglement—cannot achieve the optimum energy. That left open whether shallow circuits, which can generate entanglement, might close the gap. The new work delivers a decisive no. It proves two main theorems. First, in the regime where the average number of interactions per qubit grows with the system size n, any circuit that prepares a state with energy within a constant fraction of the optimum must have a depth that scales at least logarithmically with n. In asymptotic notation: depth Ω_p(log n). Second, in the bounded-degree regime where each qubit interacts with a fixed number of others, a fixed-depth obstruction emerges: for any chosen depth D, making the interaction prefactor sufficiently large rules out depth-D preparation of near-ground states. Both results hold uniformly over circuits that can use an arbitrary number of ancilla qubits—auxiliary qubits that don't appear in the final state but can assist in the computation.
Think of it like a vast, rugged energy landscape with countless peaks and valleys. A shallow circuit is like a hiker who can only take a few steps from a starting point; it can explore local terrain but remains trapped in the foothills. The true ground state lies in a deep, narrow crevasse that requires a long, coordinated sequence of moves to reach. The authors prove that no matter how cleverly you design your shallow circuit, it simply cannot reach that depth.
"Any circuit preparing an n-qubit state whose normalized energy is within a fixed positive constant of the optimum must have depth Ω_p(log n)," the authors write.The proof technique is a striking departure from traditional combinatorial arguments. It recasts state-preparation lower bounds as a problem of uniformly controlling Gaussian processes—collections of correlated random variables—indexed by shallow circuits. By bounding the supremum of this Gaussian process, the authors show that the energy achievable by any shallow circuit is, with high probability, far from the true optimum. This probabilistic method opens a new front in the quest for circuit lower bounds.
The State of the Field
This breakthrough lands at a moment when quantum computing is straddling the line between academic curiosity and industrial reality. Companies like IBM, Google, and Quantinuum have built processors with over 100 qubits, and the first demonstrations of logical qubits that outlive their physical constituents have arrived. Yet the theoretical foundations of what makes a good quantum error-correcting code remain incomplete. The NLTS conjecture has been a guiding star, but progress has been slow. In 2022, Anshu, Breuckmann, and Nirkhe constructed a family of code-based Hamiltonians that satisfy a version of NLTS, but their ground states can be prepared by polynomial-size circuits—leaving the constant-depth question open. The new paper tackles random spin glasses instead, and proves a fixed-depth obstruction in the bounded-degree setting, a result that directly echoes the original NLTS vision.
What sets this work apart is its probabilistic lens. Rather than handcrafting a single Hamiltonian with the desired property, the authors show that almost all spin glasses exhibit the obstruction. This shift from constructive to probabilistic mirrors the revolution in classical complexity theory sparked by random 3-SAT and other random constraint satisfaction problems. It suggests that randomness itself can be a powerful ally in proving quantum hardness. The technique also connects to the flourishing field of Gaussian processes in machine learning, hinting at cross-pollination between quantum complexity and statistical learning theory. Meanwhile, the experimental push toward fault tolerant quantum computing makes these theoretical bounds more than academic: they help delineate the boundary between what near-term noisy devices can and cannot do.
From Lab to Reality
For scientists, this paper delivers a versatile new tool. The Gaussian process framework can be applied to other random quantum models, such as the SYK model of fermionic interactions or quantum glasses with continuous variables. It provides a template for proving circuit lower bounds in any setting where the Hamiltonian can be viewed as a random process. For engineers building fault tolerant quantum computers, the hardness of preparing spin glass ground states suggests these states could serve as resources for encoding logical qubits. In a surface code architecture—the leading candidate for large-scale error correction—a logical qubit is stored in a highly entangled state that must be difficult for local noise to corrupt. Understanding which physical systems naturally produce such robust states could guide the choice of hardware platforms, from superconducting qubits to trapped ions to neutral atoms.
For investors, the quantum error correction market, projected to reach $1.8 billion by 2030 according to industry analysts, hinges on fundamental advances that close the gap between theoretical promise and practical implementation. This work doesn't directly build a better qubit, but it sharpens the mathematical criteria for what a good error-correcting code looks like. Companies like IBM, Google Quantum AI, and startups such as Alice & Bob and QuEra are investing heavily in error correction R&D. A deeper understanding of state preparation complexity could influence which qubit modalities are pursued and how error-correcting codes are designed. In the nearer term, the insights may improve variational quantum algorithms, which use shallow circuits to solve optimization problems in finance and logistics, by revealing their fundamental limitations.
What Still Needs to Happen
Despite its elegance, the paper leaves several mountains unclimbed. First, the lower bounds are asymptotic or require large interaction prefactors. Translating them into concrete depth limits for, say, 100-qubit systems demands a careful analysis of constants and finite-size effects. The quantum computing community is actively investigating the finite-size scaling of such bounds, but a practical, quantitative guide for engineers is still years away. Second, the results apply to random spin glasses, not to the structured Hamiltonians used in practical error-correcting codes like the surface code or LDPC codes. Extending the Gaussian process technique to these deterministic models is an open problem that researchers are beginning to explore. Third, the proof relies on properties of Gaussian processes that may not generalize to non-Gaussian noise or to systems with symmetries. Making the argument more combinatorial could yield tighter bounds and broader applicability. Finally, the paper proves an obstruction for preparing near-ground states, but it doesn't provide an explicit protocol for verifying that a given state is indeed low-energy—a necessary step for using these states in an error-correction pipeline. No one expects these theoretical insights to change tomorrow's quantum chips, but they redraw the map of what is possible, and that map will guide the next decade of quantum error correction research.
The Bottom Line
In short: quantum error correction research now has rigorous evidence that random quantum spin glasses resist shallow-circuit preparation, providing a new obstruction in the spirit of NLTS and a probabilistic toolkit for future lower bounds. The work transforms a longstanding conjecture into a provable property of a natural random model, marking a significant step toward understanding the complexity of quantum states.