DROPS

Document

DOI: 10.4230/LIPIcs.TQC.2025.12

The Rotation-Invariant Hamiltonian Problem Is QMA_EXP-Complete

Authors: Jon Nelson and Daniel Gottesman

Published in: LIPIcs, Volume 350, 20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025)

Abstract

In this work we study a variant of the local Hamiltonian problem where we restrict to Hamiltonians that live on a lattice and are invariant under translations and rotations of the lattice. In the one-dimensional case this problem is known to be QMA_EXP-complete. On the other hand, if we fix the lattice length then in the high-dimensional limit the ground state becomes unentangled due to arguments from mean-field theory. We take steps towards understanding this complexity spectrum by studying a problem that is intermediate between these two extremes. Namely, we consider the regime where the lattice dimension is arbitrary but fixed and the lattice length is scaled. We prove that this rotation-invariant Hamiltonian problem is QMA_EXP-complete answering an open question of [Gottesman and Irani, 2013]. This characterizes a broad parameter range in which these rotation-invariant Hamiltonians have high computational complexity.

Cite as

Jon Nelson and Daniel Gottesman. The Rotation-Invariant Hamiltonian Problem Is QMA_EXP-Complete. In 20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 350, pp. 12:1-12:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{nelson_et_al:LIPIcs.TQC.2025.12,
  author =	{Nelson, Jon and Gottesman, Daniel},
  title =	{{The Rotation-Invariant Hamiltonian Problem Is QMA\underlineEXP-Complete}},
  booktitle =	{20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025)},
  pages =	{12:1--12:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-392-8},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{350},
  editor =	{Fefferman, Bill},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2025.12},
  URN =		{urn:nbn:de:0030-drops-240615},
  doi =		{10.4230/LIPIcs.TQC.2025.12},
  annote =	{Keywords: Hamiltonian complexity, Local Hamiltonian problem, Monogamy of entanglement}
}

Search Results

Documents authored by Gottesman, Daniel

The Rotation-Invariant Hamiltonian Problem Is QMA_EXP-Complete

Abstract

Cite as

Thanks for your feedback!

Could not send message