Karen Morenz

We consider a computational problem where the goal is to approximate the maximum eigenvalue of a two-local Hamiltonian that describes antiferromagnetic Heisenberg interactions between qubits located at the vertices of the graph. Previous work has shed light on this problem’s approximability by \textit{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 triangle-free 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).