NLTS conjecture

In quantum information theory, the no low-energy trivial state (NLTS) conjecture is a precursor to a quantum PCP theorem (qPCP) and posits the existence of families of Hamiltonians with all low-energy states of non-trivial complexity.^[1][2][3][4] It was formulated by Michael Freedman and Matthew Hastings in 2013. An NLTS proof would be a consequence of one aspect of qPCP problems – the inability to certify an approximation of local Hamiltonians via NP completeness.^[2] In other words, an NLTS proof would be one consequence of the QMA complexity of qPCP problems.^[5] On a high level, if proved, NLTS would be one property of the non-Newtonian complexity of quantum computation.^[5] NLTS and qPCP conjectures posit the near-infinite complexity involved in predicting the outcome of quantum systems with many interacting states.^[6] These calculations of complexity would have implications for quantum computing such as the stability of entangled states at higher temperatures, and the occurrence of entanglement in natural systems.^[7][6] There is currently a proof of NLTS conjecture published in preprint.^[8]

NLTS property

The NLTS property is the underlying set of constraints that forms the basis for the NLTS conjecture.^{[citation needed]}

Definitions

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}$.^[9] ${\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:^[2]

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^[10] 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".^[2]

NLTS property

Kliesch defines the NLTS property thus:^[2]

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

• for all n ∈ I, H⁽ⁿ⁾ has ground energy 0,
• ⟨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).

NLTS conjecture

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

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.^[1] 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.^[7] 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.^[6] qPCP increases the complexity by trying to solve PCP for quantum states.^[6] 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.^[7]

NLETS proof

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

NLETS is defined as:^[11]

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.

References

1. "On the NLTS Conjecture". Simons Institute for the Theory of Computing. 2021-06-30. Retrieved 2022-08-07.
2. Kliesch, Alexander (2020-01-23). "The NLTS conjecture" (PDF). Technical University of Munich. Retrieved Aug 7, 2022.
3. Anshu, Anurag; Nirkhe, Chinmay (2020-11-01). Circuit lower bounds for low-energy states of quantum code Hamiltonians. Leibniz International Proceedings in Informatics (LIPIcs). Vol. 215. pp. 6:1–6:22. arXiv:2011.02044. doi:10.4230/LIPIcs.ITCS.2022.6. ISBN 9783959772174. S2CID 226299885.
4. Freedman, Michael H.; Hastings, Matthew B. (January 2014). "Quantum Systems on Non-$k$-Hyperfinite Complexes: a generalization of classical statistical mechanics on expander graphs". Quantum Information and Computation. 14 (1&2): 144–180. arXiv:1301.1363. doi:10.26421/qic14.1-2-9. ISSN 1533-7146. S2CID 10850329.
5. "Circuit lower bounds for low-energy states of quantum code Hamiltonians". DeepAI. 2020-11-03. Retrieved 2022-08-07.
6. "Computer Science Proof Lifts Limits on Quantum Entanglement". Quanta Magazine. 2022-07-18. Retrieved 2022-08-08.
7. "Research Vignette: Quantum PCP Conjectures". Simons Institute for the Theory of Computing. 2014-09-30. Retrieved 2022-08-08.
8. Anshu, Anurag; Breuckmann, Nikolas P.; Nirkhe, Chinmay (2023). "NLTS Hamiltonians from Good Quantum Codes". Proceedings of the 55th Annual ACM Symposium on Theory of Computing. pp. 1090–1096. arXiv:2206.13228. doi:10.1145/3564246.3585114. ISBN 9781450399135. S2CID 250072529.
9. Morimae, Tomoyuki; Takeuchi, Yuki; Nishimura, Harumichi (2018-11-15). "Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy". Quantum. 2: 106. arXiv:1711.10605. Bibcode:2018Quant...2..106M. doi:10.22331/q-2018-11-15-106. ISSN 2521-327X. S2CID 3958357.
10. Wen, Xiao-Gang (1990). "Topological Orders in Rigid States" (PDF). Int. J. Mod. Phys. B. 4 (2): 239. Bibcode:1990IJMPB...4..239W. CiteSeerX 10.1.1.676.4078. doi:10.1142/S0217979290000139. Archived from the original (PDF) on 2011-07-20. Retrieved 2009-04-09.
11. Eldar, Lior (2017). "Local Hamiltonians Whose Ground States are Hard to Approximate" (PDF). IEEE Symposium on Foundations of Computer Science (FOCS). Retrieved Aug 7, 2022.