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

NLTS Hamiltonians from classical LTCs

Zhiyang He, Chinmay Nirkhe

Published Oct 6, 2022• 0 citations
arXivHTMLPDF

Abstract

We provide a completely self-contained construction of a family of NLTS Hamiltonians [Freedman and Hastings, 2014] based on ideas from [Anshu, Breuckmann, and Nirkhe, 2022], [Cross, He, Natarajan, Szegedy, and Zhu, 2022] and [Eldar and Harrow, 2017]. Crucially, it does not require optimal-parameter quantum LDPC codes and can be built from simple classical LTCs such as the repetition code on an expander graph. Furthermore, it removes the constant-rate requirement from the construction of Anshu, Breuckmann, and Nirkhe.

DOI
10.48550/arxiv.2210.02999

Related papers

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

NLTS Hamiltonians from Good Quantum Codes

Anurag Anshu, Nikolas P. Breuckmann, Chinmay Nirkhe

The NLTS (No Low-Energy Trivial State) conjecture of Freedman and Hastings posits that there exist families of Hamiltonians with all low energy states of non-trivial complexity (with complexity measured by the quantum circuit depth preparing the state). We prove this conjecture by showing that a particular family of constant-rate and linear-distance qLDPC codes correspond to NLTS local Hamiltonians, although we believe this to be true for all current constructions of good qLDPC codes.

ACM Symposium on Theory of Computing (STOC)•May 16, 2023•43 citations

NLTS Hamiltonians from Good Quantum Codes

Anurag Anshu, Nikolas P. Breuckmann, Chinmay Nirkhe

Abstract. The no low-energy trivial state (NLTS) conjecture of Freedman and Hastings [ Quantum Inf. Comput., 14 (2014), pp. 144–180] posits that there exist families of Hamiltonians with all low energy states of nontrivial complexity (with complexity measured by the quantum circuit depth preparing the state). We prove this conjecture by showing that families of constant-rate and linear-distance qLDPC codes correspond to NLTS local Hamiltonians.

arXiv:2206.13228•SIAM Journal on Computing•Sep 4, 2026•1 citation

A construction of quantum LDPC codes from Cayley graphs

Alain Couvreur, Nicolas Delfosse, Gilles Zémor

We study a construction of Quantum LDPC codes proposed by MacKay, Mitchison and Shokrollahi in the draft [6]. It is based on the Cayley graph of F2ntogether with a set of generators regarded as the columns of the parity-check matrix of a classical code. We give a general lower bound on the minimum distance of the quantum code in O(dn2) where d is the minimum distance of the classical code. When the classical code is the [n, 1, n] repetition code, we are able to compute the exact parameters of the associated quantum code which are [[2n-1, 2 n/2, 2 n/2-1]].

arXiv:1206.2656•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2011•8 citations

NLTS Hamiltonians and Strongly-Explicit SoS Lower Bounds from Low-Rate Quantum LDPC Codes

Louis Golowich, Tali Kaufman

Recent constructions of the first asymptotically good quantum LDPC (qLDPC) codes led to two breakthroughs in complexity theory: the NLTS (No Low-Energy Trivial States) theorem (Anshu, Breuckmann, and Nirkhe, STOC'23), and explicit lower bounds against a linear number of levels of the Sum-of-Squares (SoS) hierarchy (Hopkins and Lin, FOCS'22). In this work, we obtain improvements to both of these results using qLDPC codes of low rate: - Whereas Anshu et al. only obtained NLTS Hamiltonians from qLDPC codes of linear dimension, we show the stronger result that qLDPC codes of arbitrarily small positive dimension yield NLTS Hamiltonians. - The SoS lower bounds of Hopkins and Lin are only weakly explicit because they require running Gaussian elimination to find a nontrivial codeword, which takes polynomial time. We resolve this shortcoming by introducing a new method of planting a strongly explicit nontrivial codeword in linear-distance qLDPC codes, which in turn yields strongly explicit SoS lower bounds. Our "planted" qLDPC codes may be of independent interest, as they provide a new way of ensuring a qLDPC code has positive dimension without resorting to parity check counting, and therefore provide more flexibility in the code construction.

arXiv:2311.09503•Leibniz international proceedings in informatics•Nov 16, 2023•1 citation

Circuit complexity lower bounds for quantum spin glasses

Omar Al-Ghattas, David Gamarnik

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.

quant-pharXiv:2607.14384•Jul 17, 2026•0 citations
We provide a completely self-contained construction of a family of NLTS Hamiltonians [Freedman and Hastings, 2014] based on ideas from [Anshu, Breuckmann, and Nirkhe, 2022], [Cross, He, Natarajan, Szegedy, and Zhu, 2022] and [Eldar and Harrow, 2017]. Crucially, it does not require optimal-parameter quantum LDPC codes and can be built from simple classical LTCs such as the repetition code on an expander graph. Furthermore, it removes the constant-rate requirement from the construction of Anshu, Breuckmann, and Nirkhe.
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 study a construction of Quantum LDPC codes proposed by MacKay, Mitchison and Shokrollahi in the draft [6]. It is based on the Cayley graph of F2ntogether with a set of generators regarded as the columns of the parity-check matrix of a classical code. We give a general lower bound on the minimum distance of the quantum code in O(dn2) where d is the minimum distance of the classical code. When the classical code is the [n, 1, n] repetition code, we are able to compute the exact parameters of the associated quantum code which are [[2n-1, 2 n/2, 2 n/2-1]].
Recent constructions of the first asymptotically good quantum LDPC (qLDPC) codes led to two breakthroughs in complexity theory: the NLTS (No Low-Energy Trivial States) theorem (Anshu, Breuckmann, and Nirkhe, STOC'23), and explicit lower bounds against a linear number of levels of the Sum-of-Squares (SoS) hierarchy (Hopkins and Lin, FOCS'22). In this work, we obtain improvements to both of these results using qLDPC codes of low rate: - Whereas Anshu et al. only obtained NLTS Hamiltonians from qLDPC codes of linear dimension, we show the stronger result that qLDPC codes of arbitrarily small positive dimension yield NLTS Hamiltonians. - The SoS lower bounds of Hopkins and Lin are only weakly explicit because they require running Gaussian elimination to find a nontrivial codeword, which takes polynomial time. We resolve this shortcoming by introducing a new method of planting a strongly explicit nontrivial codeword in linear-distance qLDPC codes, which in turn yields strongly explicit SoS lower bounds. Our "planted" qLDPC codes may be of independent interest, as they provide a new way of ensuring a qLDPC code has positive dimension without resorting to parity check counting, and therefore provide more flexibility in the code construction.
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.