The Complexity of Local Stoquastic Hamiltonians on 2D Lattices
This provides a foundational complexity classification for quantum systems, advancing theoretical understanding in quantum computing.
The paper tackles the problem of classifying the computational complexity of 2-local stoquastic Hamiltonians on 2D square qubit lattices, showing it is StoqMA-complete by extending existing constructions to achieve spatial sparsity and stoquastic-preserving perturbative gadgets without increasing particle dimension.
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.