Skip to main content

Effective Gaps Are Not Effective: Quasipolynomial Classical Simulation of Obstructed Stoquastic Hamiltonians

Abstract

All known examples suggesting an exponential separation between classical simulation algorithms and stoquastic adiabatic quantum computing (StoqAQC) 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 = (V, E) with vertical bar V vertical bar = O(poly(n)), where n is 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 vertical bar V vertical bar 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 nonstoquastic cases, or be useful in studying additional properties of k-local Hamiltonians.

Publication Details

Authors
Publication Type
Journal Article
Year of Publication
2020
Journal
Physical Review Letters
Volume
125
Date Published
10/2020

Contributors

Groups