NLTS conjecture

{{Short description|Quantum computational theorem on problem complexity}} {{multiple issues| {{technical|date=August 2022}} {{expert needed|mathematics|ex2=physics|reason = It is very complex|date=August 2022}} }}

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.<ref>{{Cite journal |last1=Freedman |first1=Michael H. |last2=Hastings |first2=Matthew B. |date=January 2014 |title=Quantum Systems on Non-$k$-Hyperfinite Complexes: a generalization of classical statistical mechanics on expander graphs |url=http://dx.doi.org/10.26421/qic14.1-2-9 |journal=Quantum Information and Computation |volume=14 |issue=1&2 |pages=144–180 |doi=10.26421/qic14.1-2-9 |arxiv=1301.1363 |s2cid=10850329 |issn=1533-7146}}</ref> 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.<ref name=":2">{{Cite web |date=2021-06-30 |title=On the NLTS Conjecture |url=https://simons.berkeley.edu/talks/nlts-conjecture |access-date=2022-08-07 |website=Simons Institute for the Theory of Computing |language=en}}</ref><ref name=":0">{{Cite web |last=Kliesch |first=Alexander |date=2020-01-23 |title=The NLTS conjecture |url=https://www-m5.ma.tum.de/foswiki/pub/M5/Allgemeines/HS_ResearchSemQIT2019/NLTSConjecture.pdf |access-date=Aug 7, 2022 |website=Technical University of Munich}}</ref><ref>{{Cite book |last1=Anshu |first1=Anurag |last2=Nirkhe |first2=Chinmay |date=2020-11-01 |title=Circuit lower bounds for low-energy states of quantum code Hamiltonians |series=Leibniz International Proceedings in Informatics (LIPIcs) |volume=215 |pages=6:1–6:22 |doi=10.4230/LIPIcs.ITCS.2022.6|doi-access=free |arxiv=2011.02044 |isbn=9783959772174 |s2cid=226299885 }}</ref>

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.<ref name="t632">{{cite arXiv | last1=Eldar | first1=Lior | last2=Harrow | first2=Aram W. | title=Local Hamiltonians with No Low-energy Trivial States | date=2015-10-07 | class=quant-ph | eprint=1510.02082v2 }}</ref> A full proof of the NLTS conjecture given in 2023 by Anurag Anshu, Nikolas Breuckmann, and Chinmay Nirkhe, and was presented at STOC 2023.<ref>{{Cite book |last1=Anshu |first1=Anurag |last2=Breuckmann |first2=Nikolas P. |last3=Nirkhe |first3=Chinmay |chapter=NLTS Hamiltonians from Good Quantum Codes |date=2023-06-02 |title=Proceedings of the 55th Annual ACM Symposium on Theory of Computing |chapter-url=https://dl.acm.org/doi/10.1145/3564246.3585114 |series=STOC 2023 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=1090–1096 |doi=10.1145/3564246.3585114 |isbn=978-1-4503-9913-5|arxiv=2206.13228 }}</ref>

== 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.<ref name=":0" />

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.<ref name=":3" /><ref name=":4" />

== 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|QMA#The_local_Hamiltonian_problem}} A ''k''-local Hamiltonian <math>H</math> is a Hermitian matrix acting on ''n'' qubits which can be represented as the sum of <math>m</math> Hamiltonian terms acting upon at most <math>k</math> qubits each: : <math>H = \sum_{i=1}^m H_i.</math>

The general ''k''-local Hamiltonian problem is, given a ''k''-local Hamiltonian <math>H</math>, to find the smallest eigenvalue <math>\lambda</math> of <math>H</math>.<ref>{{Cite journal |last1=Morimae |first1=Tomoyuki |last2=Takeuchi |first2=Yuki |last3=Nishimura |first3=Harumichi |date=2018-11-15 |title=Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy |journal=Quantum |volume=2 |article-number=106 |doi=10.22331/q-2018-11-15-106 |arxiv=1711.10605 |bibcode=2018Quant...2..106M |s2cid=3958357 |issn=2521-327X |doi-access=free }}</ref> <math>\lambda</math> 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:<ref name=":0" /> <blockquote> 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 : <math>H^{(n)} = \sum_n H_m^{(n)},</math> 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''). </blockquote>

=== NLTS property and topological order === {{See also|Topological order}} In physics, ''topological order''<ref name="wen">{{cite journal | last1 = Wen | first1 = Xiao-Gang | author-link = Xiao-Gang Wen | year = 1990 | title = Topological Orders in Rigid States | url = http://dao.mit.edu/~wen/pub/topo.pdf | journal = Int. J. Mod. Phys. B | volume = 4 | issue = 2 | page = 239 | doi = 10.1142/S0217979290000139 | citeseerx = 10.1.1.676.4078 | bibcode = 1990IJMPB...4..239W | access-date = 2009-04-09 | archive-date = 2011-07-20 | archive-url = https://web.archive.org/web/20110720000932/http://dao.mit.edu/~wen/pub/topo.pdf | url-status = dead }}</ref> 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".<ref name=":0" /> 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, # ⟨0^''n''|''U''^†''H''^(''n'')''U''|0^''n''⟩ > ''εn'' for any depth-''d'' circuit ''U'' consisting of two qubit gates and for any ''n'' ∈ ''I'' with ''n'' ≥ ''f''(''d'').<ref name=":0" />

=== NLTS conjecture === There exists a family of local Hamiltonians with the NLTS property.<ref name=":0" />

== Related statements == === Quantum PCP conjecture === {{Main|PCP theorem}} Proving the NLTS conjecture is an obstacle for resolving the qPCP conjecture, an even harder theorem to prove.<ref name=":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.<ref name=":3">{{Cite web |date=2014-09-30 |title=Research Vignette: Quantum PCP Conjectures |url=https://simons.berkeley.edu/news/research-vignette-qhc2014 |access-date=2022-08-08 |website=Simons Institute for the Theory of Computing |language=en}}</ref> 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.<ref name=":4">{{Cite web |date=2022-07-18 |title=Computer Science Proof Lifts Limits on Quantum Entanglement |url=https://www.quantamagazine.org/computer-science-proof-lifts-limits-on-quantum-entanglement-20220718/ |access-date=2022-08-08 |website=Quanta Magazine |language=en}}</ref> qPCP increases the complexity by trying to solve PCP for quantum states.<ref name=":4" /> 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.<ref name=":3" />

=== No low-error trivial states theorem === In 2015 Harrow and Eldar announced a solution to the NLTS conjecture, which was later modified to prove the simpler and weaker '''no low-error trivial states (NLETS) theorem''' after a mistake was discovered.<ref name=":5">{{Cite web |last=Eldar |first=Lior |date=2017 |title=Local Hamiltonians Whose Ground States are Hard to Approximate |url=http://ieee-focs.org/FOCS-2017-Papers/3464a427.pdf |access-date=Aug 7, 2022 |website=IEEE Symposium on Foundations of Computer Science (FOCS)}}</ref> One formulation of NLETS can be stated as follows:<ref name=":5" /> : 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.<ref name="e083">{{cite journal | last1=Nirkhe | first1=Chinmay | last2=Vazirani | first2=Umesh | last3=Yuen | first3=Henry | title=Approximate Low-Weight Check Codes and Circuit Lower Bounds for Noisy Ground States | journal=LIPIcs, Volume 107, ICALP 2018 | volume=107 | date=2018 | issn=1868-8969 | doi=10.4230/LIPICS.ICALP.2018.91 | pages=91:1–91:11 | doi-access=free }}</ref>

=== 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.<ref name="r521">{{cite journal | last1=Anshu | first1=Anurag | last2=Breuckmann | first2=Nikolas P. | title=A construction of combinatorial NLTS | journal=Journal of Mathematical Physics | volume=63 | issue=12 | date=2022-12-01 | issn=0022-2488 | doi=10.1063/5.0113731 | url=https://pubs.aip.org/jmp/article/63/12/122201/2846035/A-construction-of-combinatorial-NLTS | article-number=122201 | arxiv=2206.02741 | bibcode=2022JMP....63l2201A }}</ref>

=== 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.<ref name="o728">{{cite journal | last1=Coble | first1=Nolan J. | last2=Coudron | first2=Matthew | last3=Nelson | first3=Jon | last4=Nezhadi | first4=Seyed Sajjad | title=Local Hamiltonians with No Low-Energy Stabilizer States | journal=LIPIcs, Volume 266, TQC 2023 | volume=266 | date=2023 | issn=1868-8969 | doi=10.4230/LIPICS.TQC.2023.14 | pages=14:1–14:21 | doi-access=free }}</ref>

=== 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.<ref name="c754">{{cite journal | last1=Gharibian | first1=Sevag | last2=Le Gall | first2=François | title=Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture | journal=SIAM Journal on Computing | volume=52 | issue=4 | date=2023-08-31 | issn=0097-5397 | doi=10.1137/22M1513721 | pages=1009–1038 | url=https://epubs.siam.org/doi/10.1137/22M1513721 }}</ref>

== References == {{reflist}}

{{Authority control}}

Category:Quantum information theory Category:Conjectures Category:Conjectures that have been proved