On the complexity of two dimensional commuting local Hamiltonians

DOI10.4230/LIPICS.TQC.2018.2MaRDI QIDQ5889068zbMATH OpenFDO

Authors Dorit Aharonov, O. Kenneth

Publication date 26 April 2023

Full work available at URL https://arxiv.org/abs/1803.02213

zbMATH Keywords

commuting Hamiltoniansground stateslocal Hamiltonian complexitylocal Hamiltonian problemQMAquantum NPtopologictoric codetrivial states

Mathematics Subject Classification ID

Quantum computation (81P68) Quantum cryptography (quantum-theoretic aspects) (81P94)

Recommendations

• Two-dimensional local Hamiltonian problem with area laws is \textsf{QMA}-complete
• The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\)
• Complexity of commuting Hamiltonians on a square lattice of qubits
• THE 2-LOCAL HAMILTONIAN PROBLEM ENCOMPASSES NP
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science

Cites work

• A course in metric geometry
• Fault-tolerant quantum computation by anyons
• scientific article; zbMATH DE number 3489106 (Why is no real title available?)
• scientific article; zbMATH DE number 2103273 (Why is no real title available?)
• Matrix product operators and central elements: classical description of a quantum state
• Mostly surfaces
• On the Complexity of Commuting Local Hamiltonians, and Tight Conditions for Topological Order in Such Systems
• On the complexity of two dimensional commuting local Hamiltonians
• Quantum error correcting codes and 4-dimensional arithmetic hyperbolic manifolds
• The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\)
• The detectability lemma and quantum gap amplification
• Theory of operator algebras I.

Cited in

(7)

• Two-dimensional local Hamiltonian problem with area laws is \textsf{QMA}-complete
• scientific article; zbMATH DE number 6351479 (Why is no real title available?)
• Hardness and Ease of Curing the Sign Problem for Two-Local Qubit Hamiltonians
• Complexity classification of two-qubit commuting Hamiltonians
• On the complexity of two dimensional commuting local Hamiltonians
• Commuting local Hamiltonian problem on 2D beyond qubits
• Quantum sat problems with finite sets of projectors are complete for a plethora of classes

This page was built for publication: On the complexity of two dimensional commuting local Hamiltonians

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5889068)