NLTS Hamiltonians from Good Quantum Codes

Anurag Anshu; Nikolas P. Breuckmann; Chinmay Nirkhe

doi:10.1145/3564246.3585114

NLTS Hamiltonians from Good Quantum Codes

Anurag Anshu, Nikolas P. Breuckmann, Chinmay Nirkhe

School of Mathematics

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

28 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 language	English
Title of host publication	STOC 2023
Subtitle of host publication	Proceedings of the 55th Annual ACM Symposium on Theory of Computing
Editors	Barna Saha, Rocco A. Servedio
Publisher	Association for Computing Machinery (ACM)
Pages	1090-1096
Number of pages	7
ISBN (Electronic)	9781450399135
DOIs	https://doi.org/10.1145/3564246.3585114
Publication status	Published - 2 Jun 2023
Event	55th Annual ACM Symposium on Theory of Computing, STOC 2023 - Orlando, United States Duration: 20 Jun 2023 → 23 Jun 2023

Publication series

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

Conference

Conference	55th Annual ACM Symposium on Theory of Computing, STOC 2023
Country/Territory	United States
City	Orlando
Period	20/06/23 → 23/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

Access to Document

10.1145/3564246.3585114Licence: Unspecified

https://arxiv.org/abs/2206.13228

Handle.net

Persistent link

Cite this

Anshu, A., Breuckmann, N. P., & Nirkhe, C. (2023). NLTS Hamiltonians from Good Quantum Codes. In B. Saha, & R. A. Servedio (Eds.), STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing (pp. 1090-1096). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery (ACM). https://doi.org/10.1145/3564246.3585114

@inproceedings{6ad6858196c34b4f891cc69f8e8d653a,

title = "NLTS Hamiltonians from Good Quantum Codes",

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.",

keywords = "Ground states, Local Hamiltonian, Quantum circuit lower bounds, Quantum PCP conjecture",

author = "Anurag Anshu and Breuckmann, {Nikolas P.} and Chinmay Nirkhe",

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: {\textcopyright} 2023 ACM.; 55th Annual ACM Symposium on Theory of Computing, STOC 2023 ; Conference date: 20-06-2023 Through 23-06-2023",

year = "2023",

month = jun,

day = "2",

doi = "10.1145/3564246.3585114",

language = "English",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery (ACM)",

pages = "1090--1096",

editor = "Barna Saha and Servedio, {Rocco A.}",

booktitle = "STOC 2023",

address = "United States",

}

Anshu, A, Breuckmann, NP & Nirkhe, C 2023, NLTS Hamiltonians from Good Quantum Codes. in B Saha & RA Servedio (eds), STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing, Association for Computing Machinery (ACM), pp. 1090-1096, 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, United States, 20/06/23. https://doi.org/10.1145/3564246.3585114

NLTS Hamiltonians from Good Quantum Codes. / Anshu, Anurag; Breuckmann, Nikolas P.; Nirkhe, Chinmay.
STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing. ed. / Barna Saha; Rocco A. Servedio. Association for Computing Machinery (ACM), 2023. p. 1090-1096 (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

TY - GEN

T1 - NLTS Hamiltonians from Good Quantum Codes

AU - Anshu, Anurag

AU - Breuckmann, Nikolas P.

AU - Nirkhe, Chinmay

N1 - 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.

PY - 2023/6/2

Y1 - 2023/6/2

N2 - 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.

AB - 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.

KW - Ground states

KW - Local Hamiltonian

KW - Quantum circuit lower bounds

KW - Quantum PCP conjecture

UR - http://www.scopus.com/inward/record.url?scp=85163065512&partnerID=8YFLogxK

U2 - 10.1145/3564246.3585114

DO - 10.1145/3564246.3585114

M3 - Conference Contribution (Conference Proceeding)

AN - SCOPUS:85163065512

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 1090

EP - 1096

BT - STOC 2023

A2 - Saha, Barna

A2 - Servedio, Rocco A.

PB - Association for Computing Machinery (ACM)

T2 - 55th Annual ACM Symposium on Theory of Computing, STOC 2023

Y2 - 20 June 2023 through 23 June 2023

ER -

NLTS Hamiltonians from Good Quantum Codes

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Handle.net

Other files and links

Fingerprint

Cite this