Abstract
Despite immense progress in quantum Hamiltonian complexity in the past decade, much less is known about the computational complexity of quantum physics at the thermodynamic limit. In fact, even defining the problem properly is not straight forward. We study of the complexity of estimating the ground energy of a translationally invariant Hamiltonian in the thermodynamic limit, to within a given precision; this precision (given by n the number of bits of the approximation) is the sole input to the problem. Understanding the complexity of this problem captures how difficult it is for the physicist to measure or compute another digit in the approximation of a physical quantity in the TL of a given (fixed, translationally invariant) Hamiltonian. We show that the problem is contained in FEXP^{QMA-EXP} and is hard for FEXP^{NEXP} in 2D. This means that the problem is doubly exponentially hard in the size of the input. As a ingredient in our construction, we study the problem of computing the ground energy for translationally invariant finite 1D chains. The finite problem is specified by a single Hamiltonian term h that operates on a pair of d-dimensional particles. The input is an integer N specified in binary and the output is the ground energy up to a precision that is polynomial in N of the Hamiltonian resulting from applying h to every neighboring pair in the chain. We show that this problem is contained in FP^{QMA-EXP} and is hard for FP^{NEXP}.
Joint work with Dorit Aharonov.