NLTS conjecture

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.^[1] 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.^[2][3][4]

A proof of the NLTS conjecture was given in 2023 by Anurag Anshu, Nikolas Breuckmann, and Chinmay Nirkhe, and was presented at STOC 2023.^[5]

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 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.^[3]

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.^[6][7]

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

Main article: QMA § The_local_Hamiltonian_problem

See also: Hamiltonian (quantum mechanics)

A k-local Hamiltonian (quantum mechanics) ${\displaystyle H}$ is a Hermitian matrix acting on n qubits which can be represented as the sum of ${\displaystyle m}$ Hamiltonian terms acting upon at most ${\displaystyle k}$ qubits each:

${\displaystyle H=\sum _{i=1}^{m}H_{i}.}$

The general k-local Hamiltonian problem is, given a k-local Hamiltonian ${\displaystyle H}$, to find the smallest eigenvalue ${\displaystyle \lambda }$ of ${\displaystyle H}$.^[8] ${\displaystyle \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:^[3]

Let I ⊂ N be an index set. A family of local Hamiltonians is a set of Hamiltonians {H⁽ⁿ⁾}, n ∈ I, where each H⁽ⁿ⁾ is defined on n finite-dimensional subsystems (in the following taken to be qubits), that are of the form

${\displaystyle H^{(n)}=\sum _{n}H_{m}^{(n)},}$

where each H_m⁽ⁿ⁾ acts non-trivially on O(1) qubits. Another constraint is the operator norm of H_m⁽ⁿ⁾ is bounded by a constant independent of n and each qubit is only involved in a constant number of terms H_m⁽ⁿ⁾.

Topological order

Main article: Symmetry-protected topological order

See also: Topological order, Periodic table of topological invariants, and Topological insulator

In physics, topological order^[9] is a kind of order in the zero-temperature phase of matter (also known as quantum matter). In the context of NLTS, Kliesch states: "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".^[3]

NLTS property

As stated by Kliesch, the NLTS property is defined as follows: Let I be an infinite set of system sizes. A family of local Hamiltonians {H⁽ⁿ⁾}, n ∈ I has the NLTS property if there exists ε > 0 and a function f : N → N such that

1. for all n ∈ I, H⁽ⁿ⁾ has ground energy 0,
2. ⟨0ⁿ|U^†H⁽ⁿ⁾U|0ⁿ⟩ > εn for any depth-d circuit U consisting of two qubit gates and for any n ∈ I with n ≥ f(d).^[3]

NLTS conjecture

There exists a family of local Hamiltonians with the NLTS property.^[3]

Related results and conjecture

Quantum PCP conjecture

Main article: PCP theorem

Proving the NLTS conjecture is an obstacle for resolving the qPCP conjecture, an even harder theorem to prove.^[2] The qPCP conjecture is a quantum analogue of the classical PCP theorem. The classical PCP theorem states that satisfiability problems like 3SAT are NP-hard when estimating the maximal number of clauses that can be simultaneously satisfied in a hamiltonian system.^[6] 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.^[7] qPCP increases the complexity by trying to solve PCP for quantum states.^[7] Though it hasn't been proven yet, a positive proof of qPCP would imply that quantum entanglement in Gibbs states could remain stable at higher-energy states above absolute zero.^[6]

No low-error trivial states theorem

NLTS on its own is difficult to prove, though a simpler no low-error trivial states (NLETS) theorem has been proven, and that proof is a precursor for NLTS.^[10]

NLETS is defined as:^[10]

Let k > 1 be some integer, and {H_n}_{n ∈ N} be a family of k-local Hamiltonians. {H_n}_{n ∈ N} is NLETS if there exists a constant ε > 0 such that any ε-impostor family F = {ρ_n}_{n ∈ N} of {H_n}_{n ∈ N} is non-trivial.