  We consider the task of approximating the ground state energy of two-local
quantum Hamiltonians on bounded-degree graphs. Most existing algorithms
optimize the energy over the set of product states. Here we describe a family
of shallow quantum circuits that can be used to improve the approximation ratio
achieved by a given product state. The algorithm takes as input an $n$-qubit
product state $|v\rangle$ with mean energy $e_0=\langle v|H|v\rangle$ and
variance $\mathrm{Var}=\langle v|(H-e_0)^2|v\rangle$, and outputs a state with
an energy that is lower than $e_0$ by an amount proportional to
$\mathrm{Var}^2/n$. In a typical case, we have $\mathrm{Var}=\Omega(n)$ and the
energy improvement is proportional to the number of edges in the graph. When
applied to an initial random product state, we recover and generalize the
performance guarantees of known algorithms for bounded-occurrence classical
constraint satisfaction problems. We extend our results to $k$-local
Hamiltonians and entangled initial states.
