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 Complexity of Stoquastic Local Hamiltonian Problems
5 Pith papers cite this work. Polarity classification is still indexing.
5
Pith papers citing it
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.
citation-role summary
background 1
citation-polarity summary
verdicts
UNVERDICTED 5roles
background 1polarities
background 1representative citing papers
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 when promise gap, overlap, and spectral gap are constant with constant-depth local-pre
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 sign problem.
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.
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 annealing on embedded instances.
citing papers explorer
-
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 when promise gap, overlap, and spectral gap are constant with constant-depth local-pre
-
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 sign problem.
-
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 annealing on embedded instances.