The Complexity of Stoquastic Local Hamiltonian Problems
read the original abstract
We study the complexity of the Local Hamiltonian Problem (denoted as LH-MIN) in the special case when a Hamiltonian obeys conditions of the Perron-Frobenius theorem: all off-diagonal matrix elements in the standard basis are real and non-positive. We will call such Hamiltonians, which are common in the natural world, stoquastic. An equivalent characterization of stoquastic Hamiltonians is that they have an entry-wise non-negative Gibbs density matrix for any temperature. We prove that LH-MIN for stoquastic Hamiltonians belongs to the complexity class AM -- a probabilistic version of NP with two rounds of communication between the prover and the verifier. We also show that 2-local stoquastic LH-MIN is hard for the class MA. With the additional promise of having a polynomial spectral gap, we show that stoquastic LH-MIN belongs to the class POSTBPP=BPPpath -- a generalization of BPP in which a post-selective readout is allowed. This last result also shows that any problem solved by adiabatic quantum computation using stoquastic Hamiltonians lies in PostBPP.
This paper has not been read by Pith yet.
Forward citations
Cited by 7 Pith papers
-
The Collapse of Unentangled Stoquastic Merlin-Arthur Proof Systems
StoqMa(k) equals StoqMa for any polynomial k via a positive value-based de Finetti theorem that approximates nonnegative product values with symmetric extensions.
-
The Guided Local Hamiltonian Problem for Stoquastic Hamiltonians
The Guided Local Hamiltonian problem for stoquastic Hamiltonians is promise BPP-hard (even 2-local on lattices), BQP-hard under fixed local constraints, and admits a deterministic classical approximation algorithm whe...
-
Twisted quantum doubles are sign problem-free
Twisted quantum double phases for finite groups can be realized in sign problem-free local Hamiltonians via stochastic series expansion, contrary to the prior belief that non-positive wavefunctions imply an intrinsic ...
-
RFOX (Rotated-Field Oscillatory eXchange) quantum algorithm: Towards Parameter-Free Quantum Optimizers
RFOX keeps the instantaneous spectral gap flat across interpolation and disorder by using a constant XX catalyst plus derived ZX counter-diabatic drive, yielding faster ground-state convergence on small RFIM instances.
-
RFOX (Rotated-Field Oscillatory eXchange) quantum algorithm: Towards Parameter-Free Quantum Optimizers
RFOX maintains a flat spectral gap via non-stoquastic XX catalyst plus analytic counter-diabatic ZX driving, yielding near-optimal solutions on random-field Ising models with up to 10x fewer Trotter steps.
-
Exploring Quantum Annealing for Coarse-Grained Protein Folding
Compares quantum annealing models for coarse-grained protein folding, proposes interleaved-grid tetrahedral encoding, and reports hardware limits from embedding alongside scaling gains over classical simulated anneali...
-
Separability and entanglement of resonating valence-bond states
Proves exact separability for disconnected subsystems in dimer RK states and exponentially suppressed entanglement for RVB states on arbitrary lattices, with negativity expressed via partition functions.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.