Local Hamiltonian Problem with Succinct Ground State is MA-Complete

Abstract

Finding the ground energy of a quantum system is a fundamental problem in condensed-matter physics and quantum chemistry. Existing classical algorithms for tackling this problem often assume that the ground state has a succinct classical description, i.e., a poly-size classical circuit for computing the amplitude. Notable examples of succinct states encompass matrix product states, contractible projected-entangled-pair states, and states that can be represented by classical neural networks. We study the complexity of the local Hamiltonian problem (LHP) with a succinct ground state. We prove that this problem is MA-complete. The Hamiltonian that we consider is general and might not be stoquastic. The MA verification protocol is based on the fixed-node quantum Monte Carlo method, particularly the variant of the continuous-time Markov chain introduced by Bravyi, Carleo, Gosset, and Liu. Based on our work, we also introduce a notion of strong guided states and conjecture that the LHP with a strong guided state is MA-complete, which will be in contrast with the QCMA-complete result of the LHP with standard guided states.

Files

Additional details