Effective gaps are not effective: quasipolynomial classical simulation of obstructed stoquastic Hamiltonians

Abstract

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\left(\mathrm{poly}(n)\right)$ 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.

12 pages, 6 figures, added footnotes (v2), updated following peer review (v3)

References in corpus (15)

• Bounds for the adiabatic approximation with applications to quantum computation
• Graph Isomorphism in Quasipolynomial Time
• Simulation of Many-Body Hamiltonians using Perturbation Theory with Bounded-Strength Interactions
• Quantum Adiabatic Evolution Algorithms versus Simulated Annealing
• Tunneling and speedup in quantum optimization for permutation-symmetric problems
• A note on the switching adiabatic theorem
• The Power of Adiabatic Quantum Computation with No Sign Problem
• Adiabatic optimization versus diffusion Monte Carlo
• Polynomial-time classical simulation of quantum ferromagnets
• Graph isomorphisms in quasi-polynomial time
• Spectral Gap Analysis for Efficient Tunneling in Quantum Adiabatic Optimization
• Diffusion Monte Carlo approach versus adiabatic computation for local Hamiltonians
• Tunneling through high energy barriers in simulated quantum annealing
• Hamiltonian surgery: Cheeger-type gap inequalities for nonpositive (stoquastic), real, and Hermitian matrices
• Polynomial Time Algorithms for Estimating Spectra of Adiabatic Hamiltonians

Cited by in corpus (5)

• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Classical symmetries and the Quantum Approximate Optimization Algorithm
• Sharp complexity phase transitions generated by entanglement
• Lefschetz Thimble Quantum Monte Carlo for Spin Systems
• Simultaneous Stoquasticity