The rotation-invariant Hamiltonian problem is QMA$_{\rm EXP}$-complete

• URL: http://arxiv.org/abs/2509.00161v1
• Date: Fri, 29 Aug 2025 18:03:12 GMT
• Title: The rotation-invariant Hamiltonian problem is QMA$_{\rm EXP}$-complete
• Authors: Jon Nelson, Daniel Gottesman,
• Abstract summary: We study a variant of the local Hamiltonian problem where we restrict to Hamiltonians that live on a lattice.<n>We prove that this rotation-invariant problem is QMA$_rm EXP$-complete.
• Score: 0.08594140167290097
• License: http://creativecommons.org/licenses/by/4.0/
• 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$_{\rm 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$_{\rm EXP}$-complete answering an open question of [Gottesman, Irani 2013]. This characterizes a broad parameter range in which these rotation-invariant Hamiltonians have high computational complexity.

Related papers

• Low-degree Lower bounds for clustering in moderate dimension [53.03724383992195]
  We study the fundamental problem of clustering $n$ points into $K$ groups drawn from a mixture of isotropic Gaussians in $mathbbRd$.<n>We show that while the difficulty of clustering for $n leq dK$ is driven by dimension reduction and spectral methods, the moderate-dimensional regime involves more delicate phenomena leading to a "non-optimal rate"<n>We provide a novel non-spectral algorithm matching this rate, shedding new light on the computational limits of the clustering problem in moderate dimension.
  arXiv  Detail & Related papers  (2026-02-26T14:03:55Z)
• Robust Sublinear Convergence Rates for Iterative Bregman Projections [21.689846521201588]
  We use entropic regularization to approximate linear programs whose constraints split into two (or more) tractable blocks.<n>We derive the flow-Sinkhorn algorithm for the Wasserstein-1 distance on graphs.
  arXiv  Detail & Related papers  (2026-02-01T18:20:19Z)
• Lower Bounds for Learning Hamiltonians from Time Evolution [5.118083299467833]
  We consider the problem of learning Hamiltonians from time evolution.<n>We show that any learning algorithm with inverse time resolution requires super-polynomial total evolution time.
  arXiv  Detail & Related papers  (2025-09-25T01:50:55Z)
• Approximation of diffeomorphisms for quantum state transfers [49.1574468325115]
  We seek to combine two emerging standpoints in control theory.<n>We numerically find control laws driving state transitions in small time in a bilinear Schr"odinger PDE posed on the torus.
  arXiv  Detail & Related papers  (2025-03-18T17:28:59Z)
• Hilbert space geometry and quantum chaos [39.58317527488534]
  We consider the symmetric part of the QGT for various multi-parametric random matrix Hamiltonians. We find for a two-dimensional parameter space that, while the ergodic phase corresponds to the smooth manifold, the integrable limit marks itself as a singular geometry with a conical defect.
  arXiv  Detail & Related papers  (2024-11-18T19:00:17Z)
• Quantum computing and persistence in topological data analysis [41.16650228588075]
  Topological data analysis (TDA) aims to extract noise-robust features from a data set by examining the number and persistence of holes in its topology. We show that a computational problem closely related to a core task in TDA is $mathsfBQP_1$-hard and contained in $mathsfBQP$. Our approach relies on encoding the persistence of a hole in a variant of the guided sparse Hamiltonian problem, where the guiding state is constructed from a harmonic representative of the hole.
  arXiv  Detail & Related papers  (2024-10-28T17:54:43Z)
• Complexity of geometrically local stoquastic Hamiltonians [1.474723404975345]
  The QMA-completeness of the local Hamiltonian problem is a landmark result of the field of Hamiltonian complexity. We show that both the two- and one-dimensional geometrically local analogues remain MA-hard with high enough qudit dimension.
  arXiv  Detail & Related papers  (2024-07-22T09:27:25Z)
• Measuring quantum relative entropy with finite-size effect [53.64687146666141]
  We study the estimation of relative entropy $D(rho|sigma)$ when $sigma$ is known.<n>Our estimator attains the Cram'er-Rao type bound when the dimension $d$ is fixed.
  arXiv  Detail & Related papers  (2024-06-25T06:07:20Z)
• Some Remarks on the Regularized Hamiltonian for Three Bosons with Contact Interactions [77.34726150561087]
  We discuss some properties of a model Hamiltonian for a system of three bosons interacting via zero-range forces in three dimensions. In particular, starting from a suitable quadratic form $Q$, the self-adjoint and bounded from below Hamiltonian $mathcal H$ can be constructed. We show that the threshold value $gamma_c$ is optimal, in the sense that the quadratic form $Q$ is unbounded from below if $gammagamma_c$.
  arXiv  Detail & Related papers  (2022-07-01T10:01:14Z)
• Simultaneous Stoquasticity [0.0]
  Stoquastic Hamiltonians play a role in the computational complexity of the local Hamiltonian problem. We address the question of whether two or more Hamiltonians may be made simultaneously stoquastic via a unitary transformation.
  arXiv  Detail & Related papers  (2022-02-17T19:08:30Z)
• Complexity of Supersymmetric Systems and the Cohomology Problem [0.0]
  We consider the complexity of the local Hamiltonian problem in the context of fermionic Hamiltonians with $mathcal N=2 $ supersymmetry. Our main motivation for studying this is the fact that the ground state energy of a supersymmetric system is exactly zero if and only if a certain cohomology group is nontrivial.
  arXiv  Detail & Related papers  (2021-06-30T18:00:01Z)
• Termwise versus globally stoquastic local Hamiltonians: questions of complexity and sign-curing [3.762360672951513]
  We show that the stoquastic local Hamiltonian problem is $textbfStoqMA$-complete even for globally stoquastic Hamiltonians. We expand the class of sign-curing transformations by showing how Clifford transformations can sign-cure a class of disordered 1D $XYZ$ Hamiltonians.
  arXiv  Detail & Related papers  (2020-07-23T12:29:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.