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
6 Pith papers cite this work. Polarity classification is still indexing.
6
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 6roles
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.
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.
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.
-
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.