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:2607.14384

Circuit complexity lower bounds for quantum spin glasses

Omar Al-Ghattas, David Gamarnik

quant-phcond-mat.dis-nncs.CCmath.PRSubmitted Jul 15, 2026• Announced Jul 17, 2026• 3 citations• Revised Jul 21, 2026 (v2)
v1 · Jul 15, 2026v2 · Jul 21, 2026
arXivHTMLPDF

Abstract

A central question in quantum information theory is the circuit complexity of states arising from standard many-body models. We study this question for quantum $p$-spin glasses, random Hamiltonians whose interactions act on $p$-tuples of qubits through Pauli strings. Anschuetz, Gamarnik, and Kiani (arXiv:2404.07231) showed that the optimum energy is separated from the best energy achievable by product states. This leaves open whether shallow circuits can close the gap, since even depth-one circuits can generate entanglement. We show that the entanglement needed to close the product-state gap cannot be generated at shallow depth. When the average interaction degree grows with $n$, we prove that, for all sufficiently large fixed $p$, 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)$. In the bounded-average-degree regime, we prove a fixed-depth obstruction: for every fixed $D$, a sufficiently large degree prefactor rules out depth-$D$ preparation of near-ground states. Both results hold uniformly over circuits with an arbitrary number of ancilla qubits. Our results give an obstruction in the spirit of the No Low-Energy Trivial States problem of Freedman and Hastings (arXiv:1301.1363), but for random quantum spin glasses rather than code-based Hamiltonians such as those of Anshu, Breuckmann, and Nirkhe (arXiv:2206.13228), whose ground states admit polynomial-size preparation circuits. This setting opens a probabilistic route to NLTS-like questions: we recast state-preparation lower bounds for random quantum Hamiltonians as uniform control of Gaussian processes indexed by shallow circuits.

Comments
58 pages

Related papers

Beyond light cones: State preparation complexity in quantum spin glasses

Omar Al-Ghattas, David Gamarnik, Bobak T Kiani

We introduce a technique for studying state preparation complexity in the quantum $p$-spin model on $n$ qubits, a disordered quantum spin system with random interactions on every set of $p$ qubits. We reduce the task of proving state preparation lower bounds to bounding the local profile complexity of the class, a quantity derived from the metric entropy of the set of vectors recording each state's expectation values against all weight-$p$ Pauli strings. We show that, for sufficiently large fixed $p$, any class with local profile complexity $O(n^2)$ remains separated from the ground-state energy by $Ω(\sqrt n)$, a gap on the leading energy scale. When the profile complexity is $o(n^2)$, we prove the stronger conclusion that the class cannot outperform a benchmark class of simpler states at leading order. Product states always provide such a benchmark. Our framework strengthens known bounds and covers classes beyond the reach of previous methods. These include examples where circuit lightcones extend across the entire system, preventing an application of standard arguments. We obtain an $Ω(n^2/\log n)$ gate lower bound for preparing near-ground states and depth--width tradeoffs, allowing arbitrary one- and two-qubit gates and arbitrarily many discardable ancillas. We also derive lower bounds on entanglement depth and matrix product state bond dimension, and energy obstructions for forward and reverse magic at every fixed level of Parham's magic hierarchy (arXiv:2504.19966). For Clifford circuits doped with $T$-gates, we obtain sharper energy comparisons using product stabilizer states as a more restrictive benchmark. The proof combines an adaptation of a nonsymmetric quantum de Finetti theorem (arXiv:1810.12197) with metric-entropy bounds for the Gaussian process indexed by the local profiles of states in the class.

quant-pharXiv:2610.02166•Oct 2, 2026•0 citations

Circuit Lower Bounds for Low-Energy States of Quantum Code Hamiltonians

Anurag Anshu, Chinmay Nirkhe

The No Low-energy Trivial States (NLTS) conjecture of Freedman and Hastings, 2014 -- which posits the existence of a local Hamiltonian with a super-constant quantum circuit lower bound on the complexity of all low-energy states -- identifies a fundamental obstacle to the resolution of the quantum PCP conjecture. In this work, we provide new techniques, based on entropic and local indistinguishability arguments, that prove circuit lower bounds for all the low-energy states of local Hamiltonians arising from quantum error-correcting codes. For local Hamiltonians arising from nearly linear-rate or nearly linear-distance LDPC stabilizer codes, we prove super-constant circuit lower bounds for the complexity of all states of energy o(n). Such codes are known to exist and are not necessarily locally testable, a property previously suspected to be essential for the NLTS conjecture. Curiously, such codes can also be constructed on a two-dimensional lattice, showing that low-depth states cannot accurately approximate the ground-energy even in physically relevant systems.

arXiv:2011.02044•Leibniz international proceedings in informatics•Nov 3, 2020•19 citations

Circuit lower bounds for quantum code Hamiltonians and an almost linear NLTS theorem

Anurag Anshu, Chinmay Nirkhe

The No Low-energy Trivial States (NLTS) conjecture of Freedman and Hastings (Quantum Information and Computation, 2014) -- which posits the existence of a local Hamiltonian with a super-constant circuit lower bound on the complexity of all low-energy states -- identifies a fundamental obstacle to the resolution of the quantum PCP conjecture. In this paper, we provide new techniques, based on entropic and local indistinguishability arguments, for proving circuit lower bounds for the low-energy states of local Hamiltonians arising from quantum error-correcting codes. For local Hamiltonians arising from nearly linear-rate and polynomial-distance LDPC stabilizer codes, we prove a super-constant circuit lower bounds for the complexity of all states of energy o(n) (which can be viewed as an almost linear NLTS theorem). Such codes are known to exist and, in general, are not locally-testable, a property previously suspected to be essential for the NLTS conjecture. Curiously, such codes can also be constructed on a constant-dimensional lattice, showing that complex entanglement at high energies can persist in physically relevant systems.

•Nov 3, 2020•0 citations

An Entropy-Governed Speedup for Quantum Algorithms on Local Hamiltonians

Ranitha Mataraarachchi, François Le Gall, Suguru Tamaki

Low-energy estimation and state preparation for general $k$-local Hamiltonians are fundamental challenges in quantum complexity theory. For constant relative accuracy, Buhrman et al. (PRL 2025) recently broke the natural Grover bound $O(2^{n/2})$, where $n$ denotes the number of qubits, for both problems. In this paper, for any sufficiently small parameter $d\ge 0$, we present an even faster quantum algorithm that outputs a quantum state with energy bounded by the minimum energy over all depth-$d$ states (i.e., states obtained by applying a depth-$d$ circuit to the all-zero state), together with an estimate of this energy. For the class of Hamiltonians with depth-$d$ ground states, our algorithm furthermore achieves exactly the same energy guarantees as Buhrman et al. Our results also provide insight into the distinction between strongly entangled states and those admitting efficient classical descriptions.

quant-pharXiv:2605.18241•May 19, 2026•2 citations

A construction of combinatorial NLTS

Anurag Anshu, Nikolas P. Breuckmann

The NLTS (No Low-Energy Trivial State) conjecture [M. H. Freedman and M. B. Hastings, Quantum Inf. Comput. 14, 144 (2014)] posits that there exist families of Hamiltonians with all low energy states of high complexity (with complexity measured by the quantum circuit depth preparing the state). Here, we prove a weaker version called the combinatorial no low error trivial states (NLETS), where a quantum circuit lower bound is shown against states that violate a (small) constant fraction of local terms. This generalizes the prior NLETS results [L. Eldar and A. W. Harrow, in 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2017), pp. 427–438] and [Nirkhe et al., in 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Leibniz International Proceedings in Informatics (LIPIcs), edited by Chatzigiannakis et al. (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2018), Vol. 107, pp. 1–11]. Our construction is obtained by combining tensor networks with expander codes [M. Sipser and D. Spielman, IEEE Trans. Inf. Theory 42, 1710 (1996)]. The Hamiltonian is the parent Hamiltonian of a perturbed tensor network, inspired by the “uncle Hamiltonian” of Fernández-González et al. [Commun. Math. Phys. 333, 299 (2015)]. Thus, we deviate from the quantum Calderbank-Shor-Steane (CSS) code Hamiltonians considered in most prior works.

arXiv:2206.02741•Journal of Mathematical Physics•Dec 1, 2022•8 citations

Circuit Lower Bounds for the p-Spin Optimization Problem

David Gamarnik, Aukosh Jagannath, Alexander S. Wein

We consider the problem of finding a near ground state of a p-spin model with Rademacher couplings by means of a low-depth circuit. As a direct extension of the authors' recent work [GJW20], we establish that any poly-size n-output circuit that produces a spin assignment with objective value within a certain constant factor of optimality, must have depth at least log n=(2 log log n) as n grows. This is stronger than the known state of the art bounds of the form (log n=(k(n) log log n)) for similar combinatorial optimization problems, where k(n) depends on the optimality value. For example, for the largest clique problem k(n) corresponds to the square of the size of the clique [Ros10]. At the same time our results are not quite comparable since in our case the circuits are required to produce a solution itself rather than solving the associated decision problem. As in our earlier work [GJW20], the approach is based on the overlap gap property (OGP) exhibited by random p-spin models, but the derivation of the circuit lower bound relies further on standard facts from Fourier analysis on the Boolean cube, in particular the Linial-Mansour-Nisan Theorem. To the best of our knowledge, this is the first instance when methods from spin glass theory have ramifications for circuit complexity.

arXiv:2109.01342•Markov Processes And Related Fields•May 27, 2024•22 citations
A central question in quantum information theory is the circuit complexity of states arising from standard many-body models. We study this question for quantum ppp-spin glasses, random Hamiltonians whose interactions act on ppp-tuples of qubits through Pauli strings. Anschuetz, Gamarnik, and Kiani (arXiv:2404.07231) showed that the optimum energy is separated from the best energy achievable by product states. This leaves open whether shallow circuits can close the gap, since even depth-one circuits can generate entanglement.
We show that the entanglement needed to close the product-state gap cannot be generated at shallow depth. When the average interaction degree grows with nnn, we prove that, for all sufficiently large fixed ppp, any circuit preparing an nnn-qubit state whose normalized energy is within a fixed positive constant of the optimum must have depth Ωp(log⁡n)Ω_p(\log n)Ωp​(logn). In the bounded-average-degree regime, we prove a fixed-depth obstruction: for every fixed DDD, a sufficiently large degree prefactor rules out depth-DDD preparation of near-ground states. Both results hold uniformly over circuits with an arbitrary number of ancilla qubits.
Our results give an obstruction in the spirit of the No Low-Energy Trivial States problem of Freedman and Hastings (arXiv:1301.1363), but for random quantum spin glasses rather than code-based Hamiltonians such as those of Anshu, Breuckmann, and Nirkhe (arXiv:2206.13228), whose ground states admit polynomial-size preparation circuits. This setting opens a probabilistic route to NLTS-like questions: we recast state-preparation lower bounds for random quantum Hamiltonians as uniform control of Gaussian processes indexed by shallow circuits.
We introduce a technique for studying state preparation complexity in the quantum ppp-spin model on nnn qubits, a disordered quantum spin system with random interactions on every set of ppp qubits. We reduce the task of proving state preparation lower bounds to bounding the local profile complexity of the class, a quantity derived from the metric entropy of the set of vectors recording each state's expectation values against all weight-ppp Pauli strings. We show that, for sufficiently large fixed ppp, any class with local profile complexity O(n2)O(n^2)O(n2) remains separated from the ground-state energy by Ω(n)Ω(\sqrt n)Ω(n​), a gap on the leading energy scale. When the profile complexity is o(n2)o(n^2)o(n2), we prove the stronger conclusion that the class cannot outperform a benchmark class of simpler states at leading order. Product states always provide such a benchmark. Our framework strengthens known bounds and covers classes beyond the reach of previous methods. These include examples where circuit lightcones extend across the entire system, preventing an application of standard arguments. We obtain an Ω(n2/log⁡n)Ω(n^2/\log n)Ω(n2/logn) gate lower bound for preparing near-ground states and depth--width tradeoffs, allowing arbitrary one- and two-qubit gates and arbitrarily many discardable ancillas. We also derive lower bounds on entanglement depth and matrix product state bond dimension, and energy obstructions for forward and reverse magic at every fixed level of Parham's magic hierarchy (arXiv:2504.19966). For Clifford circuits doped with TTT-gates, we obtain sharper energy comparisons using product stabilizer states as a more restrictive benchmark. The proof combines an adaptation of a nonsymmetric quantum de Finetti theorem (arXiv:1810.12197) with metric-entropy bounds for the Gaussian process indexed by the local profiles of states in the class.
The No Low-energy Trivial States (NLTS) conjecture of Freedman and Hastings, 2014 -- which posits the existence of a local Hamiltonian with a super-constant quantum circuit lower bound on the complexity of all low-energy states -- identifies a fundamental obstacle to the resolution of the quantum PCP conjecture. In this work, we provide new techniques, based on entropic and local indistinguishability arguments, that prove circuit lower bounds for all the low-energy states of local Hamiltonians arising from quantum error-correcting codes. For local Hamiltonians arising from nearly linear-rate or nearly linear-distance LDPC stabilizer codes, we prove super-constant circuit lower bounds for the complexity of all states of energy o(n). Such codes are known to exist and are not necessarily locally testable, a property previously suspected to be essential for the NLTS conjecture. Curiously, such codes can also be constructed on a two-dimensional lattice, showing that low-depth states cannot accurately approximate the ground-energy even in physically relevant systems.
The No Low-energy Trivial States (NLTS) conjecture of Freedman and Hastings (Quantum Information and Computation, 2014) -- which posits the existence of a local Hamiltonian with a super-constant circuit lower bound on the complexity of all low-energy states -- identifies a fundamental obstacle to the resolution of the quantum PCP conjecture. In this paper, we provide new techniques, based on entropic and local indistinguishability arguments, for proving circuit lower bounds for the low-energy states of local Hamiltonians arising from quantum error-correcting codes. For local Hamiltonians arising from nearly linear-rate and polynomial-distance LDPC stabilizer codes, we prove a super-constant circuit lower bounds for the complexity of all states of energy o(n) (which can be viewed as an almost linear NLTS theorem). Such codes are known to exist and, in general, are not locally-testable, a property previously suspected to be essential for the NLTS conjecture. Curiously, such codes can also be constructed on a constant-dimensional lattice, showing that complex entanglement at high energies can persist in physically relevant systems.
Low-energy estimation and state preparation for general kkk-local Hamiltonians are fundamental challenges in quantum complexity theory. For constant relative accuracy, Buhrman et al. (PRL 2025) recently broke the natural Grover bound O(2n/2)O(2^{n/2})O(2n/2), where nnn denotes the number of qubits, for both problems. In this paper, for any sufficiently small parameter d≥0d\ge 0d≥0, we present an even faster quantum algorithm that outputs a quantum state with energy bounded by the minimum energy over all depth-ddd states (i.e., states obtained by applying a depth-ddd circuit to the all-zero state), together with an estimate of this energy. For the class of Hamiltonians with depth-ddd ground states, our algorithm furthermore achieves exactly the same energy guarantees as Buhrman et al. Our results also provide insight into the distinction between strongly entangled states and those admitting efficient classical descriptions.
The NLTS (No Low-Energy Trivial State) conjecture [M. H. Freedman and M. B. Hastings, Quantum Inf. Comput. 14, 144 (2014)] posits that there exist families of Hamiltonians with all low energy states of high complexity (with complexity measured by the quantum circuit depth preparing the state). Here, we prove a weaker version called the combinatorial no low error trivial states (NLETS), where a quantum circuit lower bound is shown against states that violate a (small) constant fraction of local terms. This generalizes the prior NLETS results [L. Eldar and A. W. Harrow, in 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2017), pp. 427–438] and [Nirkhe et al., in 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Leibniz International Proceedings in Informatics (LIPIcs), edited by Chatzigiannakis et al. (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2018), Vol. 107, pp. 1–11]. Our construction is obtained by combining tensor networks with expander codes [M. Sipser and D. Spielman, IEEE Trans. Inf. Theory 42, 1710 (1996)]. The Hamiltonian is the parent Hamiltonian of a perturbed tensor network, inspired by the “uncle Hamiltonian” of Fernández-González et al. [Commun. Math. Phys. 333, 299 (2015)]. Thus, we deviate from the quantum Calderbank-Shor-Steane (CSS) code Hamiltonians considered in most prior works.
We consider the problem of finding a near ground state of a p-spin model with Rademacher couplings by means of a low-depth circuit. As a direct extension of the authors' recent work [GJW20], we establish that any poly-size n-output circuit that produces a spin assignment with objective value within a certain constant factor of optimality, must have depth at least log n=(2 log log n) as n grows. This is stronger than the known state of the art bounds of the form (log n=(k(n) log log n)) for similar combinatorial optimization problems, where k(n) depends on the optimality value. For example, for the largest clique problem k(n) corresponds to the square of the size of the clique [Ros10]. At the same time our results are not quite comparable since in our case the circuits are required to produce a solution itself rather than solving the associated decision problem. As in our earlier work [GJW20], the approach is based on the overlap gap property (OGP) exhibited by random p-spin models, but the derivation of the circuit lower bound relies further on standard facts from Fourier analysis on the Boolean cube, in particular the Linial-Mansour-Nisan Theorem. To the best of our knowledge, this is the first instance when methods from spin glass theory have ramifications for circuit complexity.