NLTS conjecture

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.

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. 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.

Background

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: Let I ⊂ N be an index set. A family of local Hamiltonians is a set of Hamiltonians {H (n) }, n ∈ I, where each H (n) is defined on n finite-dimensional subsystems (in the following taken to be qubits), that are of the form H^{(n)} = \sum_n H_m^{(n)}, where each H m (n) acts non-trivially on O(1) qubits.

Another constraint is the operator norm of H m (n) is bounded by a constant independent of n and each qubit is only involved in a constant number of terms H m (n) . 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. A simplified proof of NLETS was given by Nirkhe, Vazirani, and Yuen in 2018.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1377552230 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

9 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.