Effective Gaps are not Effective: Quasipolynomial Classical Simulation of Obstructed Stoquastic Hamiltonians

Jacob Bringewatt, University of Maryland, College Park

Photo of Jacob Bringewatt

All known examples suggesting an exponential separation between classical simulation algorithms and stoquastic adiabatic quantum computing (StoqAQC) with k-local Hamiltonians exploit symmetries that constrain adiabatic dynamics to effective, symmetric subspaces. The symmetries produce large effective eigenvalue gaps, which in turn make adiabatic computation efficient. We present a classical algorithm to subexponentially sample from an effective subspace of any k-local stoquastic Hamiltonian H without a priori knowledge of its symmetries (or near symmetries). Our algorithm maps any k-local Hamiltonian to a graph G with number of vertices polynomial in the the number of qubits. Given the well-known result of Babai [Graph isomorphism in quasipolynomial time, in Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing (2016), pp. 684-697], we exploit graph isomorphism to study the automorphisms of G and arrive at an algorithm quasipolynomial in the number of qubits for producing samples from effective subspace eigenstates of H. Our results rule out exponential separations between StoqAQC and classical computation that arise from hidden symmetries in k-local Hamiltonians. Our graph representation of H is not limited to stoquastic Hamiltonians and may rule out corresponding obstructions in non-stoquastic cases, or be useful in studying additional properties of k-local Hamiltonians.

Abstract Author(s): Jacob Bringewatt, Michael Jarret