  The quantum k-Local Hamiltonian problem is a natural generalization of
classical constraint satisfaction problems (k-CSP) and is complete for QMA, a
quantum analog of NP. Although the complexity of k-Local Hamiltonian problems
has been well studied, only a handful of approximation results are known. For
Max 2-Local Hamiltonian where each term is a rank 3 projector, a natural
quantum generalization of classical Max 2-SAT, the best known approximation
algorithm was the trivial random assignment, yielding a 0.75-approximation. We
present the first approximation algorithm beating this bound, a classical
polynomial-time 0.764-approximation. For strictly quadratic instances, which
are maximally entangled instances, we provide a 0.801 approximation algorithm,
and numerically demonstrate that our algorithm is likely a 0.821-approximation.
We conjecture these are the hardest instances to approximate. We also give
improved approximations for quantum generalizations of other related classical
2-CSPs. Finally, we exploit quantum connections to a generalization of the
Grothendieck problem to obtain a classical constant-factor approximation for
the physically relevant special case of strictly quadratic traceless 2-Local
Hamiltonians on bipartite interaction graphs, where a inverse logarithmic
approximation was the best previously known (for general interaction graphs).
Our work employs recently developed techniques for analyzing classical
approximations of CSPs and is intended to be accessible to both quantum
information scientists and classical computer scientists.
