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

[edit]

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

Definitions

[edit]

Local hamiltonians

[edit]

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

The general k-local Hamiltonian problem is, given a k-local Hamiltonian , to find the smallest eigenvalue of .[9] 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 IN be an index set. A family of local Hamiltonians is a set of Hamiltonians {H(n)}, nI, where each H(n) is defined on n finite-dimensional subsystems (in the following taken to be qubits), that are of the form

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

Topological order

[edit]

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

[edit]

Kliesch defines the NLTS property thus:[2]

Let I be an infinite set of system sizes. A family of local Hamiltonians {H(n)}, nI has the NLTS property if there exists ε > 0 and a function f : NN such that

  • for all nI, H(n) has ground energy 0,
  • ⟨0n|UH(n)U|0n⟩ > εn for any depth-d circuit U consisting of two qubit gates and for any nI with nf(d).

NLTS conjecture

[edit]

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

Quantum PCP conjecture

[edit]

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

[edit]

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 {Hn}nN be a family of k-local Hamiltonians. {Hn}nN is NLETS if there exists a constant ε > 0 such that any ε-impostor family F = {ρn}nN of {Hn}nN is non-trivial.

References

[edit]
  1. ^ a b "On the NLTS Conjecture". Simons Institute for the Theory of Computing. 2021-06-30. Retrieved 2022-08-07.
  2. ^ a b c d e f 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. ^ a b "Circuit lower bounds for low-energy states of quantum code Hamiltonians". DeepAI. 2020-11-03. Retrieved 2022-08-07.
  6. ^ a b c d "Computer Science Proof Lifts Limits on Quantum Entanglement". Quanta Magazine. 2022-07-18. Retrieved 2022-08-08.
  7. ^ a b c "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. ^ a b 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.