The Guided Local Hamiltonian Problem for Stoquastic Hamiltonians

• URL: http://arxiv.org/abs/2509.25829v1
• Date: Tue, 30 Sep 2025 06:11:26 GMT
• Title: The Guided Local Hamiltonian Problem for Stoquastic Hamiltonians
• Authors: Gabriel Waite,
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We show that the Guided Local Hamiltonian problem for stoquastic Hamiltonians is (promise) BPP-hard. The Guided Local Hamiltonian problem is a variant of the Local Hamiltonian problem that incorporates an additional input known as a guiding state, which is promised to overlap with the ground state. For a range of local Hamiltonian families, this problem is (promise) BQP-hard, though for stoquastic Hamiltonians, the complexity was previously unknown. Our results are achieved by first reducing from quantum-inspired BPP circuits to 6-local stoquastic Hamiltonians. We prove particular classes of quantum states, known as semi-classical encoded subset states, can guide the estimation of the ground state energy. Subsequent analysis shows the BPP-hardness is not dependent on the locality, i.e., the result holds for 2-local stoquastic Hamiltonians. Additional arguments further the BPP-hardness to Hamiltonians restricted to a square lattice. We also find for stoquastic Hamiltonians with a fixed local constraint on a subset of the system qubits, the Guided Local Hamiltonian problem is BQP-hard.

Related papers

• Hamiltonian Decoded Quantum Interferometry [69.7049555871155]
  We introduce Hamiltonian Decoded Quantum Interferometry (HDQI)<n>HDQI utilizes coherent measurements and the symplectic representation of the Pauli group to reduce Gibbs sampling and Hamiltonian Bellians.<n>We show that HDQI efficiently prepares Gibbs states at arbitrary temperatures for a class of physically motivated commuting Hamiltonians.
  arXiv  Detail & Related papers  (2025-10-09T08:06:15Z)
• On the Complexity of the Succinct State Local Hamiltonian Problem [0.0]
  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.
  arXiv  Detail & Related papers  (2025-09-30T05:55:36Z)
• 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)
• 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)
• Hamiltonian for a Bose gas with Contact Interactions [49.1574468325115]
  We study the Hamiltonian for a three-dimensional Bose gas of $N geq 3$ spinless particles interacting via zero-range (also known as contact) interactions.<n>Such interactions are encoded by (singular) boundary conditions imposed on the coincidence hyperplanes, i.e., when the coordinates of two particles coincide.<n>We construct a class of Hamiltonians characterized by such modified boundary conditions, that are self-adjoint and bounded from below.
  arXiv  Detail & Related papers  (2024-03-19T10:00:12Z)
• 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)
• Recovery of a generic local Hamiltonian from a degenerate steady state [11.567029926262476]
  Hamiltonian Learning (HL) is essential for validating quantum systems in quantum computing. HL success depends on the Hamiltonian model and steady state. We analyze HL for a specific type of steady state composed of eigenstates with degenerate mixing weight.
  arXiv  Detail & Related papers  (2023-09-01T08:40:50Z)
• 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)
• Improved Hardness Results for the Guided Local Hamiltonian Problem [1.53934570513443]
  Estimating the ground state energy of a local Hamiltonian is a central problem in quantum chemistry. We show that the BQP-completeness persists even with 2-local Hamiltonians. We also show BQP-hardness persists when considering estimating energies of excited states of these Hamiltonians.
  arXiv  Detail & Related papers  (2022-07-21T01:13:32Z)
• 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)
• Average-case Speedup for Product Formulas [69.68937033275746]
  Product formulas, or Trotterization, are the oldest and still remain an appealing method to simulate quantum systems. We prove that the Trotter error exhibits a qualitatively better scaling for the vast majority of input states. Our results open doors to the study of quantum algorithms in the average case.
  arXiv  Detail & Related papers  (2021-11-09T18:49:48Z)
• A Partially Random Trotter Algorithm for Quantum Hamiltonian Simulations [31.761854762513337]
  Given the Hamiltonian, the evaluation of unitary operators has been at the heart of many quantum algorithms. Motivated by existing deterministic and random methods, we present a hybrid approach.
  arXiv  Detail & Related papers  (2021-09-16T13:53:12Z)

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.