Abstract

Over the past decade there has been a merging of condensed matter physics and computational complexity theory has given rise to the field of Hamiltonian Complexity. The fundamental problem of study is approximating the ground state energy of many-body Hamiltonians (known as the local Hamiltonian problem). Other properties such as the form of the ground state subspace and excited state have also been characterised. However, despite certain phenomena such a phase transitions happening only in the thermodynamic limit, there has little work investigating this limit from a Hamiltonian complexity perspective. In this work we characterise the complexity of finding the ground state energy density in the thermodynamic limit and show that it is classically hard, but quantumly is likely only of QMA -intermediate hardness. We also note that our result is the first complexity result we know of that investigates how hard it is to improve the precision to which a value is known.