Beyond product state approximations for a quantum analogue of Max Cut

Anurag Anshu, David Gosset, Karen Morenz

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…