1 Search Results for "Vigdorovich, Itamar"

Document
DOI: 10.4230/LIPIcs.TQC.2018.2
On the Complexity of Two Dimensional Commuting Local Hamiltonians

Authors: Dorit Aharonov, Oded Kenneth, and Itamar Vigdorovich

Published in: LIPIcs, Volume 111, 13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018)

Abstract
The complexity of the commuting local Hamiltonians (CLH) problem still remains a mystery after two decades of research of quantum Hamiltonian complexity; it is only known to be contained in NP for few low parameters. Of particular interest is the tightly related question of understanding whether groundstates of CLHs can be generated by efficient quantum circuits. The two problems touch upon conceptual, physical and computational questions, including the centrality of non-commutation in quantum mechanics, quantum PCP and the area law. It is natural to try to address first the more physical case of CLHs embedded on a 2D lattice, but this problem too remained open apart from some very specific cases [Aharonov and Eldar, 2011; Hastings, 2012; Schuch, 2011]. Here we consider a wide class of two dimensional CLH instances; these are k-local CLHs, for any constant k; they are defined on qubits set on the edges of any surface complex, where we require that this surface complex is not too far from being "Euclidean". Each vertex and each face can be associated with an arbitrary term (as long as the terms commute). We show that this class is in NP, and moreover that the groundstates have an efficient quantum circuit that prepares them. This result subsumes that of Schuch [Schuch, 2011] which regarded the special case of 4-local Hamiltonians on a grid with qubits, and by that it removes the mysterious feature of Schuch's proof which showed containment in NP without providing a quantum circuit for the groundstate and considerably generalizes it. We believe this work and the tools we develop make a significant step towards showing that 2D CLHs are in NP.
Cite as

Dorit Aharonov, Oded Kenneth, and Itamar Vigdorovich. On the Complexity of Two Dimensional Commuting Local Hamiltonians. In 13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 111, pp. 2:1-2:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{aharonov_et_al:LIPIcs.TQC.2018.2,
  author =	{Aharonov, Dorit and Kenneth, Oded and Vigdorovich, Itamar},
  title =	{{On the Complexity of Two Dimensional Commuting Local Hamiltonians}},
  booktitle =	{13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018)},
  pages =	{2:1--2:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-080-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{111},
  editor =	{Jeffery, Stacey},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2018.2},
  URN =		{urn:nbn:de:0030-drops-92498},
  doi =		{10.4230/LIPIcs.TQC.2018.2},
  annote =	{Keywords: local Hamiltonian complexity, commuting Hamiltonians, local Hamiltonian problem, trivial states, toric code, ground states, quantum NP, QMA, topological order, multiparticle entanglement, logical operators, ribbon}
}
  • Refine by Author
  • 1 Aharonov, Dorit
  • 1 Kenneth, Oded
  • 1 Vigdorovich, Itamar

  • Refine by Classification
  • 1 Theory of computation → Quantum complexity theory

  • Refine by Keyword
  • 1 QMA
  • 1 commuting Hamiltonians
  • 1 ground states
  • 1 local Hamiltonian complexity
  • 1 local Hamiltonian problem
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact