NLTS conjecture

Quantum computational theorem on problem complexity In quantum information theory, the no low-energy trivial state (NLTS) conjecture is a lower bound on the complexity of certain classes of quantum states which was conjectured by Michael Freedman and Matthew Hastings in 2013. It was partly intended to be a weaker consequence of a conjectural quantum PCP theorem which would be easier to prove than a full quantum PCP theorem. A solution to the NLTS conjecture was initially announced in 2015 by Lior Eldar and Aram Harrow, but was modified to prove a weaker statement after a mistake was discovered in the proof. A full proof of the NLTS conjecture given in 2023 by Anurag Anshu, Nikolas Breuckmann, and Chinmay Nirkhe, and was presented at STOC 2023. Background The classical theory of NP-hardness is well-suited for characterizing problems which are unlikely to be solvable in polynomial time, but does not capture some of the complexities which arise in more realistic scenarios. For example, many NP-hard optimization problems have polynomial-time approximation algorithms, though often there is an approximation threshold beyond which the problem becomes NP-hard to solve. Such hardness of app