On the Complexity of the Succinct State Local Hamiltonian Problem

• URL: http://arxiv.org/abs/2509.25821v1
• Date: Tue, 30 Sep 2025 05:55:36 GMT
• Title: On the Complexity of the Succinct State Local Hamiltonian Problem
• Authors: Gabriel Waite, Karl Lin,
• Abstract summary: We show that the Succinct State 3-Local Hamiltonian problem is (promise) MA-complete.<n>Our proof proceeds by systematically characterising succinct quantum states and modifying the original MA-hardness reduction.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the computational complexity of the Local Hamiltonian problem under the promise that its ground state is succinctly represented. We show that the Succinct State 3-Local Hamiltonian problem is (promise) MA-complete. Our proof proceeds by systematically characterising succinct quantum states and modifying the original MA-hardness reduction. In particular, we show that a broader class of succinct states suffices to capture the hardness of the problem, extending and strengthening prior results to classes of Hamiltonians with lower locality.

Related papers

• The Guided Local Hamiltonian Problem for Stoquastic Hamiltonians [0.0]
  We show that the Guided Local Hamiltonian problem for stoquastic Hamiltonians is (promise) BPP-hard.<n>For a range of local Hamiltonian families, this problem is (promise) BQP-hard, though for stoquastic Hamiltonians, the complexity was previously unknown.
  arXiv  Detail & Related papers  (2025-09-30T06:11:26Z)
• Robust analog quantum simulators by quantum error-detecting codes [22.034646136056804]
  We provide a recipe for error-resilient Hamiltonian simulations, making use of an excited encoding subspace stabilized by solely $2$-local commuting Hamiltonians.<n>Our method is scalable as it only requires penalty terms that scale to system size.
  arXiv  Detail & Related papers  (2024-12-10T18:58:05Z)
• On the hardness of learning ground state entanglement of geometrically local Hamiltonians [2.6034750171634107]
  Characterizing the entanglement structure of ground states of local Hamiltonians is a fundamental problem in quantum information. In particular we show this problem is roughly factoring-hard in 1D, and LWE-hard in 2D. Our work suggests that the problem of learning so-called "gapless" phases of matter might be intractable.
  arXiv  Detail & Related papers  (2024-11-07T01:16:15Z)
• Optimizing random local Hamiltonians by dissipation [44.99833362998488]
  We prove that a simplified quantum Gibbs sampling algorithm achieves a $Omega(frac1k)$-fraction approximation of the optimum. Our results suggest that finding low-energy states for sparsified (quasi)local spin and fermionic models is quantumly easy but classically nontrivial.
  arXiv  Detail & Related papers  (2024-11-04T20:21:16Z)
• 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)
• Coherence generation with Hamiltonians [44.99833362998488]
  We explore methods to generate quantum coherence through unitary evolutions. This quantity is defined as the maximum derivative of coherence that can be achieved by a Hamiltonian. We identify the quantum states that lead to the largest coherence derivative induced by the Hamiltonian.
  arXiv  Detail & Related papers  (2024-02-27T15:06:40Z)
• Local Hamiltonian Problem with succinct ground state is MA-Complete [0.788657961743755]
  Finding the ground energy of a quantum system is a fundamental problem in condensed matter physics and quantum chemistry.<n>Existing classical algorithms for tackling this problem often assume that the ground state has a succinct classical description.<n>We study the complexity of the local Hamiltonian problem with succinct ground state and prove it is MA-Complete.
  arXiv  Detail & Related papers  (2023-09-18T21:08:51Z)
• Sparse random Hamiltonians are quantumly easy [105.6788971265845]
  A candidate application for quantum computers is to simulate the low-temperature properties of quantum systems. This paper shows that, for most random Hamiltonians, the maximally mixed state is a sufficiently good trial state. Phase estimation efficiently prepares states with energy arbitrarily close to the ground energy.
  arXiv  Detail & Related papers  (2023-02-07T10:57:36Z)
• Efficient Verification of Ground States of Frustration-Free Hamiltonians [28.03059224016627]
  We propose a recipe for verifying the ground states of general frustration-free Hamiltonians based on local measurements. We derive rigorous bounds on the sample complexity by virtue of the quantum detectability lemma and quantum union bound. Our work is of interest not only to many tasks in quantum information processing, but also to the study of many-body physics.
  arXiv  Detail & Related papers  (2022-06-30T13:50:56Z)
• A construction of Combinatorial NLTS [22.539300644593936]
  NLTS (No Low-Energy Trivial State) conjecture of Freedman and Hastings [2014] posits that there exist families of Hamiltonians with all low energy states of high complexity. Here, we prove a weaker version called the NLTS, where a quantum circuit lower bound is shown against states that violate a (small) constant fraction of local terms.
  arXiv  Detail & Related papers  (2022-06-06T16:55:34Z)
• Iterative Quantum Optimization with Adaptive Problem Hamiltonian [19.4417702222583]
  We describe an iterative algorithm in which a solution obtained with such a restricted problem Hamiltonian is used to define a new problem Hamiltonian that is better suited than the previous one. In numerical examples of the shortest vector problem, we show that the algorithm with a sequence of improved problem Hamiltonians converges to the desired solution.
  arXiv  Detail & Related papers  (2022-04-28T12:04:03Z)
• Pinned QMA: The power of fixing a few qubits in proofs [0.6299766708197883]
  We show that pinning a single qubit via often repeated measurements results in universal quantum computation already with commuting and stoquastic Hamiltonians. We hence identify a comprehensive picture of the computational power of pinning, reminiscent of the power of the one clean qubit model.
  arXiv  Detail & Related papers  (2020-01-10T19:20:29Z)

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.