In an important recent development, Anshu, Breuckmann, and Nirkhe \cite{anshu2022nlts} resolved positively the so-called No Low-Energy Trivial State (NLTS) conjecture by Freedman and Hastings. The conjecture postulated the existence of linear-size local Hamiltonians on n qubit systems for which no near-ground state can be prepared by a shallow (sublogarithmic depth) circuit. The construction in \cite{anshu2022nlts} is based on recently developed good quantum codes. Earlier results in this direction included the constructions of the so-called Combinatorial NLTS – a weaker version of NLTS – where a state is defined to have low energy if it violates at most a vanishing fraction of the Hamiltonian terms \cite{anshu2022construction}. These constructions were also based on codes. In this paper we provide a "non-code" construction of a class of Hamiltonians satisfying the Combinatorial NLTS. The construction is inspired by one in \cite{anshu2022construction}, but our proof uses the complex solution space geometry of random K-SAT instead of properties of codes. Specifically, it is known that above a certain clause-to-variables density the set of satisfying assignments of random K-SAT exhibits an overlap gap property, which implies that it can be partitioned into exponentially many clusters each constituting at most an exponentially small fraction of the total set of satisfying solutions. We establish a certain robust version of this clustering property for the space of near-satisfying assignments and show that for our constructed Hamiltonians every combinatorial near-ground state induces a near-uniform distribution supported by this set. Standard arguments then are used to show that such distributions cannot be prepared by quantum circuits with depth o(log n). Since the clustering property is exhibited by many random structures, including proper coloring and maximum cut, we anticipate that our approach is extendable to these models as well.
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.
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(logn). 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.
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.
Understanding the complexity of low-energy quantum states is a central problem in quantum complexity theory and many-body physics. Here we prove the no low-energy trivial magic (NLTM) conjecture, constructing a family of local Hamiltonians for which every state within a positive energy density window requires circuit depth
Ω(logn) to prepare from arbitrary stabilizer state that may themselves be highly entangled. Notably, our result is intrinsic in the sense that the same Hamiltonian family and energy density threshold apply to arbitrary qudit stabilizer inputs with any bounded local dimensions. Our construction builds on non-Abelian gauged sheaf codes obtained using the cup product structure on good quantum locally testable codes. We establish constant operator soundness for the associated Hamiltonians, enabling their protected logical structure to constrain all states at sufficiently low energy density. By excluding shallow stabilizer-based classical witnesses, Our result substantially strengthens NLTS and advances our understanding of low-energy complexity relevant to quantum PCP.