Approximate low-weight check codes and circuit lower bounds for noisy ground states

Understand

The No Low-Energy Trivial States (NLTS) conjecture of Freedman and Hastings (Quantum Information and Computation 2014), which asserts the existence of local Hamiltonians whose low energy states cannot be generated by constant depth quantum circuits, identifies a fundamental obstacle to resolving the quantum PCP conjecture.

• Progress towards the NLTS conjecture was made by Eldar and Harrow (Foundations of Computer Science 2017), who proved a closely related theorem called No Low-Error Trivial States (NLETS).
• In this paper, we give a much simpler proof of the NLETS theorem, and use the same technique to establish superpolynomial circuit size lower bounds for noisy ground states of local Hamiltonians (assuming $\mathsf{QCMA} \neq \mathsf{QMA}$), resolving an open question of Eldar and Harrow.
• We discuss the new light our results cast on the relationship between NLTS and NLETS.