Fetching the paper…
Reading the bibliography…
The NLTS (No Low-Energy Trivial State) conjecture of Freedman and Hastings [2014] 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).
Ramanujan graphs
Alexander Lubotzky, Ralph Phillips, and Peter Sarnak. 1988 · 1988
Earlier work this paper cites.
Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
Grigorii Aleksandrovich Margulis. 1988 · 1988
Earlier work this paper cites.
Inclusion-exclusion: Exact and approximate
Jeff Kahn, Nathan Linial, and Alex Samorodnitsky. 1996 · 1996
Earlier work this paper cites.
Expander codes
Michael Sipser and Daniel A Spielman. 1996 · 1996
Earlier work this paper cites.
Bounds for small-error and zero-error quantum algorithms
H. Buhrman, R. Cleve, R. De Wolf, and C. Zalka. 1999 · 1999
Earlier work this paper cites.
Coding theorem and strong converse for quantum channels
A. Winter. 1999 · 1999
Earlier work this paper cites.
Complexity of Positivstellensatz proofs for the knapsack
D. Grigoriev. 2001 · 2001
Earlier work this paper cites.
Classical and Quantum Computation
A. Yu. Kitaev, A. H. Shen, and M. N. Vyalyi. 2002 · 2002
Earlier work this paper cites.
Commutative Version of the Local Hamiltonian Problem and Common Eigenspace Problem
Sergey Bravyi and Mikhail Vyalyi. 2005 · 2005
Earlier work this paper cites.
Homological connectivity of random 2-complexes
Nathan Linial* and Roy Meshulam*. 2006 · 2006
Earlier work this paper cites.
The Detectability Lemma and Quantum Gap Amplification. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing (Bethesda, MD, USA) (STOC ’09) . Association for Computing Machinery, New York, NY, USA, 417–426
Dorit Aharonov, Itai Arad, Zeph Landau, and Umesh Vazirani. 2009 · 2009
Earlier work this paper cites.
Quantum LDPC codes with positive rate and minimum distance proportional to sqrt(n). In 2009 IEEE International Symposium on Information Theory . 799–803
J. Tillich and G. Zemor. 2009 · 2009
Earlier work this paper cites.
Guest Column: The Quantum PCP Conjecture
Dorit Aharonov, Itai Arad, and Thomas Vidick. 2013 · 2013
Cited alongside, same era.
Product-State Approximations to Quantum Ground States. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing (Palo Alto, California, USA) (STOC ’13) . Association for Computing Machinery, New York, NY, USA, 871–880
Fernando G.S.L. Brandao and Aram W. Harrow. 2013 · 2013
Cited alongside, same era.
Quantum Systems on Non-k-Hyperfinite Complexes: A Generalization of Classical Statistical Mechanics on Expander Graphs
Michael H. Freedman and Matthew B. Hastings. 2014 · 2014
Cited alongside, same era.
The Commuting Local Hamiltonian Problem on Locally Expanding Graphs is Approximable in NP
Dorit Aharonov and Lior Eldar. 2015 · 2015
Cited alongside, same era.
Proofs, beliefs, and algorithms through the lens of sum-of-squares
Boaz Barak and David Steurer. 2016 · 2016
Cited alongside, same era.
Quantum low-density parity-check codes
Nikolas P Breuckmann and Jens Niklas Eberhardt. 2021b · 2021
Later among the works it cites.
Robust Quantum Entanglement at (Nearly) Room Temperature. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) (Leibniz International Proceedings in Informatics (LIPIcs)) , James R. Lee (Ed.), Vol. 185. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 49:1–49:20
Lior Eldar. 2021 · 2021
Later among the works it cites.
The overlap gap property: A topological barrier to optimizing over random structures
David Gamarnik. 2021 · 2021
Later among the works it cites.
Asymptotically Good Quantum and Locally Testable Classical LDPC Codes
Pavel Panteleev and Gleb Kalachev. 2021 · 2021
Later among the works it cites.
An Area Law for 2d Frustration-Free Spin Systems. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Rome, Italy) (STOC 2022) . Association for Computing Machinery, New York, NY, USA, 12–18
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Local Hamiltonians Whose Ground States Are Hard to Approximate. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) . 427–438
L. Eldar and A. W. Harrow. 2017 · 2017
Cited alongside, same era.
Roy Meshulam. 2018 · 2018
Cited alongside, same era.
Low-Degree Testing for Quantum States, and a Quantum Entangled Games PCP for QMA. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018 , Mikkel Thorup (Ed.). IEEE Computer Society, 731–742
Anand Natarajan and Thomas Vidick. 2018 · 2018
Cited alongside, same era.
Approximate Low-Weight Check Codes and Circuit Lower Bounds for Noisy Ground States. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) (Leibniz International Proceedings in Informatics (LIPIcs)) , Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella (Eds.), Vol. 107. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 91:1–91:11
Chinmay Nirkhe, Umesh Vazirani, and Henry Yuen. 2018 · 2018
Cited alongside, same era.
On tensor products of CSS codes
Benjamin Audoux and Alain Couvreur. 2019 · 2019
Cited alongside, same era.
Obstacles to State Preparation and Variational Optimization from Symmetry Protection
Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang. 2019 · 2019
Cited alongside, same era.
Balanced Product Quantum Codes
Nikolas P. Breuckmann and Jens N. Eberhardt. 2021a · 2021
Cited alongside, same era.
Anurag Anshu, Itai Arad, and David Gosset. 2022 · 2022
Closest in time.
A construction of Combinatorial NLTS
Anurag Anshu and Nikolas P. Breuckmann. 2022 · 2022
Closest in time.
Circuit Lower Bounds for Low-Energy States of Quantum Code Hamiltonians. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) (Leibniz International Proceedings in Informatics (LIPIcs)) , Mark Braverman (Ed.), Vol. 215. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 6:1–6:22
Anurag Anshu and Chinmay Nirkhe. 2022 · 2022
Closest in time.
Good Quantum LDPC Codes with Linear Time Decoders
Irit Dinur, Min-Hsiu Hsieh, Ting-Chun Lin, and Thomas Vidick. 2022 · 2022
Closest in time.
Explicit lower bounds against Ω ( n ) \Omega(n) -rounds of sum-of-squares. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) . IEEE, 662–673
Max Hopkins and Ting-Chun Lin. 2022b · 2022
Closest in time.
Quantum Tanner codes
Anthony Leverrier and Gilles Zémor. 2022 · 2022
Closest in time.
Lower bounds on the complexity of quantum proofs
Chinmay Nirkhe. 2022 · 2022
Closest in time.