  We consider a computational problem where the goal is to approximate the
maximum eigenvalue of a two-local Hamiltonian that describes Heisenberg
interactions between qubits located at the vertices of a graph. Previous work
has shed light on this problem's approximability by product states. For any
instance of this problem the maximum energy attained by a product state is
lower bounded by the Max Cut of the graph and upper bounded by the standard
Goemans-Williamson semidefinite programming relaxation of it. Gharibian and
Parekh described an efficient classical approximation algorithm for this
problem which outputs a product state with energy at least 0.498 times the
maximum eigenvalue in the worst case, and observe that there exist instances
where the best product state has energy 1/2 of optimal. We investigate
approximation algorithms with performance exceeding this limitation which are
based on optimizing over tensor products of few-qubit states and shallow
quantum circuits. We provide an efficient classical algorithm which achieves an
approximation ratio of at least 0.53 in the worst case. We also show that for
any instance defined by a 3- or 4-regular graph, there is an efficiently
computable shallow quantum circuit that prepares a state with energy larger
than the best product state (larger even than its semidefinite programming
relaxation).
