Quantum advantage from energy measurements of many-body quantum systems

The problem of sampling outputs of quantum circuits has been proposed as a candidate for demonstrating a quantum computational advantage (sometimes referred to as quantum "supremacy"). An open question is whether quantum advantage demonstrations backed by complexity-theoretic evidence can be achieved for physically motivated problems. In this work, we show quantum advantage for the natural problem of measuring the energy of a many-body quantum system. In particular, we describe a family of Hamiltonians with nearest-neighbour interactions on a 2D lattice that can be measured with high resolution by sampling from a quantum device, which can conceivably be implemented in the near-term. At the same time, we provide strong complexity theoretic evidence that an efficient classical simulation of this problem is impossible. Our proof exploits the ability to build a simple quantum circuit which efficiently diagonalizes these Hamiltonians. Furthermore, we highlight limitations of current theoretical tools to develop quantum advantage proposals involving Hamiltonians where such diagonalization is not known or, more generally, for Hamiltonians whose time-evolution cannot be \emph{exponentially fast-forwarded}. We believe our work brings a new perspective to the problem of demonstrating quantum advantage and leads to interesting new questions in Hamiltonian complexity.