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• 0 citations
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 method for studying state preparation complexity in dense quantum $p$-spin Hamiltonians on $n$ qubits, going beyond bounds based only on circuit lightcones. The key input is the class's effective profile complexity, which is derived from the metric entropy of its Pauli profiles. These profiles record expectations of all Pauli operators supported on exactly $p$ qubits. Classes with uniformly bounded quadratic effective profile complexity remain separated from the ground-state energy by a positive multiple of $\sqrt n$ for sufficiently large fixed $p$. At subquadratic effective profile complexity, the class cannot outperform a suitable benchmark class at leading order, with product states providing a universal benchmark. The proof combines an adaptation of a nonsymmetric quantum de Finetti theorem of Berta et al. (arXiv:1810.12197) with Gaussian process entropy bounds. Applying this framework, we show that attaining near-ground-state energy requires $Ω(n^2/\log n)$ one- and two-qubit gates, even with arbitrary discardable ancillas. We also obtain depth-width tradeoffs, entanglement-depth and matrix product state bond-dimension lower bounds, and obstructions for both orientations at every fixed level of Parham's magic hierarchy (arXiv:2504.19966), with total circuit width $O(n)$. In first-level reverse magic, a shallow circuit is followed by an unrestricted Clifford circuit. The latter can spread local observables across the system, preventing a direct application of small-lightcone bounds. For this first-level class, our bounds also allow arbitrarily many clean ancillas at fixed shallow-circuit depth. A sharper benchmark shows that Clifford+$T$ circuits with $o(n)$ $T$-gates have no leading-order energy advantage over product stabilizer states, even with unrestricted Clifford operations and arbitrary discardable ancillas.

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•6 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•0 citations

Pseudoentanglement in constant depth: How trivial states can have non-trivial entanglement structure

Alexandru Gheorghiu

We construct a family of 2D-local constant-depth quantum circuits that output states whose entanglement entropy across a specified cut cannot be estimated in quantum polynomial time. As constant-depth quantum circuits can be learned from polynomially many quantum samples, our resulting pseudoentangled states are implicitly public-key and not pseudorandom. This separates pseudoentanglement from pseudorandomness in the shallow-circuit regime: the former is possible, while the latter is not. The construction is based on the quantum intractability of the Dense-Sparse Learning Parity with Noise problem introduced in [DJ25] and uses a bounded-fan-in, bounded-fan-out classical randomized encoding for linear maps $\mathbf{x} \mapsto \mathbf{Mx},$ which could be of independent interest. As applications, we obtain quantum hardness for the problem of learning the entanglement structure (across a fixed cut) of the ground-state of 1D and 2D local Hamiltonians. The 1D Hamiltonian has an inverse polynomial gap, whereas the 2D one has a constant gap. This complements the result of [BZZ24] that showed only factoring-based hardness for the 1D case, though achieving a volume versus area entanglement difference.

quant-pharXiv:2605.31448•Jun 1, 2026•0 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•5 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 method for studying state preparation complexity in dense quantum ppp-spin Hamiltonians on nnn qubits, going beyond bounds based only on circuit lightcones. The key input is the class's effective profile complexity, which is derived from the metric entropy of its Pauli profiles. These profiles record expectations of all Pauli operators supported on exactly ppp qubits. Classes with uniformly bounded quadratic effective profile complexity remain separated from the ground-state energy by a positive multiple of n\sqrt nn​ for sufficiently large fixed ppp. At subquadratic effective profile complexity, the class cannot outperform a suitable benchmark class at leading order, with product states providing a universal benchmark. The proof combines an adaptation of a nonsymmetric quantum de Finetti theorem of Berta et al. (arXiv:1810.12197) with Gaussian process entropy bounds. Applying this framework, we show that attaining near-ground-state energy requires Ω(n2/log⁡n)Ω(n^2/\log n)Ω(n2/logn) one- and two-qubit gates, even with arbitrary discardable ancillas. We also obtain depth-width tradeoffs, entanglement-depth and matrix product state bond-dimension lower bounds, and obstructions for both orientations at every fixed level of Parham's magic hierarchy (arXiv:2504.19966), with total circuit width O(n)O(n)O(n). In first-level reverse magic, a shallow circuit is followed by an unrestricted Clifford circuit. The latter can spread local observables across the system, preventing a direct application of small-lightcone bounds. For this first-level class, our bounds also allow arbitrarily many clean ancillas at fixed shallow-circuit depth. A sharper benchmark shows that Clifford+TTT circuits with o(n)o(n)o(n) TTT-gates have no leading-order energy advantage over product stabilizer states, even with unrestricted Clifford operations and arbitrary discardable ancillas.
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.
We construct a family of 2D-local constant-depth quantum circuits that output states whose entanglement entropy across a specified cut cannot be estimated in quantum polynomial time. As constant-depth quantum circuits can be learned from polynomially many quantum samples, our resulting pseudoentangled states are implicitly public-key and not pseudorandom. This separates pseudoentanglement from pseudorandomness in the shallow-circuit regime: the former is possible, while the latter is not. The construction is based on the quantum intractability of the Dense-Sparse Learning Parity with Noise problem introduced in [DJ25] and uses a bounded-fan-in, bounded-fan-out classical randomized encoding for linear maps x↦Mx,\mathbf{x} \mapsto \mathbf{Mx},x↦Mx, which could be of independent interest. As applications, we obtain quantum hardness for the problem of learning the entanglement structure (across a fixed cut) of the ground-state of 1D and 2D local Hamiltonians. The 1D Hamiltonian has an inverse polynomial gap, whereas the 2D one has a constant gap. This complements the result of [BZZ24] that showed only factoring-based hardness for the 1D case, though achieving a volume versus area entanglement difference.
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.