NLTS conjecture

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 approximation results are typically proven using the classical PCP theorem or under an assumption like the unique games conjecture, which characterizes the approximability of many constraint satisfaction problems. In the quantum setting, one common analog of classical constraint satisfaction problems is the local Hamiltonian problem, which asks for the ground energy (lowest eigenvalue) of a quantum local Hamiltonian. This problem is known to be QMA-hard and is expected to be unsolvable even by quantum polynomial-time algorithms. An analog of the PCP theorem for the local Hamiltonian problem would imply that the ground energy is QMA-hard even to approximate, but is still conjectural. In 2012, Hastings observed that the quantum PCP conjecture implies that there are quantum local Hamiltonians whose ground states cannot be prepared by small quantum circuits, since otherwise approximating the ground energy would be contained in NP. Motivated by this observation, Freedman and Hastings in 2013 formally conjectured the existence of such Hamiltonians as the no low-energy trivial states (NLTS) conjecture. Interpreted more physically, the conjecture states that there exist large quantum systems where entanglement of the ground state persists at nonzero temperatures. == Precise formulation ==

The NLTS conjecture states that there is a family of quantum local Hamiltonians satisfying the NLTS property, which is defined more precisely below. Local Hamiltonians A k-local Hamiltonian H is a Hermitian matrix acting on n qubits which can be represented as the sum of m Hamiltonian terms acting upon at most k qubits each: : H = \sum_{i=1}^m H_i. The general k-local Hamiltonian problem is, given a k-local Hamiltonian H, to find the smallest eigenvalue \lambda of H. \lambda is also called the ground-state energy of the Hamiltonian. The family of local Hamiltonians thus arises out of the k-local problem. Kliesch states the following as a definition for local Hamiltonians in the context of NLTS: is a kind of order in the zero-temperature phase of matter (also known as quantum matter). In the context of NLTS, Kliesch states that "a family of local gapped Hamiltonians is called topologically ordered if any ground states cannot be prepared from a product state by a constant-depth circuit". An informal version of the NLTS conjecture asserts the existence of local Hamiltonians whose low-energy states are topologically ordered. A more precise version of the NLTS property is stated by Kliesch as follows: Let I be an infinite set of system sizes. A family of local Hamiltonians {H(n)}, n ∈ I has the NLTS property if there exists ε > 0 and a function f : N → N such that • for all n ∈ I, H(n) has ground energy 0, • ⟨0n|U†H(n)U|0n⟩ > εn for any depth-d circuit U consisting of two qubit gates and for any n ∈ I with n ≥ f(d). NLTS conjecture There exists a family of local Hamiltonians with the NLTS property. == Related statements ==

Quantum PCP conjecture Proving the NLTS conjecture is an obstacle for resolving the qPCP conjecture, an even harder theorem to prove. In layman's terms, classical PCP describes the near-infinite complexity involved in predicting the outcome of a system with many resolving states, such as a water bath full of hundreds of magnets. qPCP increases the complexity by trying to solve PCP for quantum states. One formulation of NLETS can be stated as follows: Combinatorial NLTS theorem The NLETS theorem was later strengthened in 2022 by Anshu and Breuckmann to show that there is a family of Hamiltonians where any state violating a small constant fraction of local terms must have nontrivial circuit complexity. No low-energy stabilizer states theorem The solution to the original NLTS conjecture constructs a family of Hamiltonians whose ground states are the codewords of a quantum stabilizer code, which are known to be classically simulable by the Gottesman-Knill theorem. The construction of NLTS Hamiltonians was later generalized by Coble, Coudron, Nelson, and Nezhadi to Hamiltonians whose low-energy space contains neither states of trivial circuit complexity nor stabilizer states. No low-energy sampleable states conjecture A stronger conjecture, introduced by Gharibian and Le Gall in 2021, states that there is a family of Hamiltonians whose low-energy space does not contain any states whose measurement in the computational basis can be simulated efficiently by a classical algorithm. == References ==