NLTS Hamiltonians from Good Quantum Codes

Anurag Anshu, Nikolas P. Breuckmann, Chinmay Nirkhe

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

7 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationSTOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing
EditorsBarna Saha, Rocco A. Servedio
PublisherAssociation for Computing Machinery (ACM)
Pages1090-1096
Number of pages7
ISBN (Electronic)9781450399135
DOIs
Publication statusPublished - 2 Jun 2023
Event55th Annual ACM Symposium on Theory of Computing, STOC 2023 - Orlando, United States
Duration: 20 Jun 202323 Jun 2023

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Conference

Conference55th Annual ACM Symposium on Theory of Computing, STOC 2023
Country/TerritoryUnited States
CityOrlando
Period20/06/2323/06/23

Bibliographical note

Funding Information:
We thank Nolan Coble, Matt Coudron, Jens Eberhardt, Lior Eldar, David Gamarnik, Sevag Gharibian, Yeongwoo Huang, Jon Nelson, Madhu Sudan and Umesh Vazirani for helpful discussions. The majority of this work was conducted while Nikolas P. Breuckmann was affiliated with University College London and Chinmay Nirkhe was affiliated with the University of California, Berkeley. AA acknowledges support through the NSF CAREER Award No. 2238836 and NSF award QCIS-FF: Quantum Computing & Information Science Faculty Fellow at Harvard University (NSF 2013303). NPB acknowledges support through the EPSRC Prosperity Partnership in Quantum Software for Simulation and Modelling (EP/S005021/1). CN was supported by NSF Quantum Leap Challenges Institute Grant number OMA2016245. Part of this work was completed while AA and CN were participants in the Simons Institute for the Theory of Computing The Quantum Wave in Computing: Extended Reunion.

Publisher Copyright:
© 2023 ACM.

Keywords

  • Ground states
  • Local Hamiltonian
  • Quantum circuit lower bounds
  • Quantum PCP conjecture

Fingerprint

Dive into the research topics of 'NLTS Hamiltonians from Good Quantum Codes'. Together they form a unique fingerprint.

Cite this