A construction of combinatorial NLTS

Anurag Anshu*, Nikolas P. Breuckmann

*Corresponding author for this work

Research output: Contribution to journalArticle (Academic Journal)peer-review

1 Citation (Scopus)
8 Downloads (Pure)


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.

Original languageEnglish
Article number122201
JournalJournal of Mathematical Physics
Issue number12
Publication statusPublished - 1 Dec 2022

Bibliographical note

Funding Information:
We thank Chinmay Nirkhe for helpful discussions. We also thank Robbie King and the anonymous referee for carefully reading our manuscript. A.A. acknowledges support through the NSF award QCIS-FF: Quantum Computing and Information Science Faculty Fellow at Harvard University (Grant No. NSF 2013303). N.P.B. acknowledges support through the EPSRC Prosperity Partnership in Quantum Software for Simulation and Modeling (Grant No. EP/S005021/1).

Publisher Copyright:
© 2022 Author(s).


  • quant-ph


Dive into the research topics of 'A construction of combinatorial NLTS'. Together they form a unique fingerprint.

Cite this