We will explore synergies between classical discrete optimization problems and the Local Hamiltonian problem, a natural quantum generalization of classical constraint satisfaction problems (CSPs). We will consider Quantum Max Cut, a QMA-hard 2-Local Hamiltonian problem. Quantum Max Cut is emerging as a testbed for approximating 2-Local Hamiltonian problems analogously to Max Cut’s role as a canonical CSP and discrete optimization problem that has driven development of classical heuristics, approximation algorithms, and hardness results.  We will discuss several recent results including an optimal product-state approximation for Quantum Max Cut based on a quantum version of the Lasserre hierarchy, as well as prospects for Unique-Games hardness. This talk is aimed at a broad audience and assumes no background in quantum physics.