The Complexity of Local Stoquastic Hamiltonians on 2D Lattices
read the original abstract
We show the 2-Local Stoquastic Hamiltonian problem on a 2D square qubit lattice is StoqMA-complete. We achieve this by extending the spatially sparse circuit construction of Oliveira and Terhal, as well as the perturbative gadgets of Bravyi, DiVincenzo, Oliveira, and Terhal. Our main contributions demonstrate StoqMA circuits can be made spatially sparse and that geometrical, stoquastic-preserving, perturbative gadgets can be constructed, without an increase to particle dimension.
This paper has not been read by Pith yet.
Forward citations
Cited by 3 Pith papers
-
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...
-
Unentangled stoquastic Merlin-Arthur proof systems: the power of unentanglement without destructive interference
StoqMA(2) contains NP with Õ(√n)-qubit proofs and completeness error 2^{-polylog(n)}, is contained in EXP, and satisfies StoqMA(k)=StoqMA(2) for k≥2 when completeness error is negligible.
-
On the Complexity of the Succinct State Local Hamiltonian Problem
The succinct state 2-local Hamiltonian problem for qubit Hamiltonians is promise-MA-complete.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.