Improved approximation algorithms for bounded-degree local Hamiltonians

Understand

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$.