Product-state Approximations to Quantum Ground States
Fernando G. S. L. Brandão, Aram W. Harrow · 2013
The local Hamiltonian problem consists of estimating the ground-state energy (given by the minimum eigenvalue) of a local quantum Hamiltonian. It can be considered as a quantum gen-eralization of constraint satisfaction problems (CSPs) and has a central role both in quantum many-body physics and quantum complexity theory. A key feature that distinguishes quan-tum Hamiltonians from classical CSPs is that the solutions may involve complicated entangled states. In this paper, we demonstrate several large classes of Hamiltonians for which product (i.e. unentangled) states can approximate the ground state energy to within a small extensive error. First, we show the existence of a good product-state approximation for the ground-state en-ergy of 2-local Hamiltonians with one or more of the following properties: (1) high degree, (2) small expansion, or (3) a ground state with sublinear entanglement with respect to some parti-tion into small pieces. The approximation based on degree is a surprising difference between quantum Hamiltonians and classical CSPs, since in the classical setting, higher degree is usu-ally associated with harder CSPs. The approximation based on low entanglement, in turn, was