Misplaced Pages

NLTS conjecture

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
(Redirected from NLTS Conjecture) Quantum computational theorem on problem complexity
This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages)
This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details. (August 2022) (Learn how and when to remove this message)
This article needs attention from an expert in mathematics or physics. The specific problem is: It is very complex. WikiProject Mathematics or WikiProject Physics may be able to help recruit an expert. (August 2022)
(Learn how and when to remove this message)

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. It was formulated by Michael Freedman and Matthew Hastings in 2013. NLTS is a consequence of one aspect of qPCP problems – the inability to certify an approximation of local Hamiltonians via NP completeness. In other words, it is a consequence of the QMA complexity of qPCP problems. On a high level, it is one property of the non-Newtonian complexity of quantum computation. NLTS and qPCP conjectures posit the near-infinite complexity involved in predicting the outcome of quantum systems with many interacting states. 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. A proof of the NLTS conjecture was presented and published as part of STOC 2023.

NLTS property

The NLTS property is the underlying set of constraints that forms the basis for the NLTS conjecture.

Definitions

Local hamiltonians

Main article: QMA § The_local_Hamiltonian_problem See also: Hamiltonian (quantum mechanics)

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

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

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

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

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

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

Topological order

Main article: Symmetry-protected topological order See also: Topological order, Periodic table of topological invariants, and Topological insulator

In physics, topological order 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".

NLTS property

Kliesch defines the NLTS property thus:

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

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

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.

NLETS is defined as:

Let k > 1 be some integer, and {Hn}n ∈ N be a family of k-local Hamiltonians. {Hn}n ∈ N is NLETS if there exists a constant ε > 0 such that any ε-impostor family F = {ρn}n ∈ N of {Hn}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-06-02). "NLTS Hamiltonians from Good Quantum Codes". Proceedings of the 55th Annual ACM Symposium on Theory of Computing. STOC 2023. New York, NY, USA: Association for Computing Machinery. pp. 1090–1096. arXiv:2206.13228. doi:10.1145/3564246.3585114. ISBN 978-1-4503-9913-5.
  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.
Categories: