NLTS conjecture

In quantum information theory, the no low-energy trivial state (NLTS) conjecture is a precursor to a quantum PCP theorem (qPCP) and posits the existence of families of Hamiltonians with all low-energy states of non-trivial complexity.[1][2][3][4] It was formulated by Michael Freedman and Matthew Hastings in 2013. An NLTS proof would be a consequence of one aspect of qPCP problems – the inability to certify an approximation of local Hamiltonians via NP completeness.[2] In other words, an NLTS proof would be one consequence of the QMA complexity of qPCP problems.[5] On a high level, if proved, NLTS would be one property of the non-Newtonian complexity of quantum computation.[5] NLTS and qPCP conjectures posit the near-infinite complexity involved in predicting the outcome of quantum systems with many interacting states.[6] These calculations of complexity would have implications for quantum computing such as the stability of entangled states at higher temperatures, and the occurrence of entanglement in natural systems.[7][6] There is currently a proof of NLTS conjecture published in preprint.[8]

  1. ^ "On the NLTS Conjecture". Simons Institute for the Theory of Computing. 2021-06-30. Retrieved 2022-08-07.
  2. ^ a b Kliesch, Alexander (2020-01-23). "The NLTS conjecture" (PDF). Technical University of Munich. Retrieved Aug 7, 2022.
  3. ^ Anshu, Anurag; Nirkhe, Chinmay (2020-11-01). Circuit lower bounds for low-energy states of quantum code Hamiltonians. Leibniz International Proceedings in Informatics (LIPIcs). Vol. 215. pp. 6:1–6:22. arXiv:2011.02044. doi:10.4230/LIPIcs.ITCS.2022.6. ISBN 9783959772174. S2CID 226299885.
  4. ^ Freedman, Michael H.; Hastings, Matthew B. (January 2014). "Quantum Systems on Non-$k$-Hyperfinite Complexes: a generalization of classical statistical mechanics on expander graphs". Quantum Information and Computation. 14 (1&2): 144–180. arXiv:1301.1363. doi:10.26421/qic14.1-2-9. ISSN 1533-7146. S2CID 10850329.
  5. ^ a b "Circuit lower bounds for low-energy states of quantum code Hamiltonians". DeepAI. 2020-11-03. Retrieved 2022-08-07.
  6. ^ a b Cite error: The named reference :4 was invoked but never defined (see the help page).
  7. ^ Cite error: The named reference :3 was invoked but never defined (see the help page).
  8. ^ Anshu, Anurag; Breuckmann, Nikolas P.; Nirkhe, Chinmay (2023). "NLTS Hamiltonians from Good Quantum Codes". Proceedings of the 55th Annual ACM Symposium on Theory of Computing. pp. 1090–1096. arXiv:2206.13228. doi:10.1145/3564246.3585114. ISBN 9781450399135. S2CID 250072529.