



01710nas a2200121   4500008004100000245011300041210006900154260001400223520127200237100002201509700002001531856003701551       2020                        eng d00aEffective gaps are not effective: quasipolynomial classical simulation of obstructed stoquastic Hamiltonians0 aEffective gaps are not effective quasipolynomial classical simul  c4/21/20203 a<p>All known examples confirming the possibility of an exponential separation between classical simulation algorithms and stoquastic adiabatic quantum computing (AQC) 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 efficiently sample from the effective subspace of a 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=(V,E) with |V|=O(poly(n)) where n is the number of qubits. Given the well-known result of Babai, we exploit graph isomorphism to study the automorphisms of G and arrive at an algorithm quasi-polynomial in |V| for producing samples from the effective subspace eigenstates of H. Our results rule out exponential separations between stoquastic AQC and classical computation that arise from hidden symmetries in k-local Hamiltonians. Furthermore, 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.</p>1 aBringewatt, Jacob1 aJarret, Michael  uhttps://arxiv.org/abs/2004.08681