Solving Quantum Max Cut via Swap Operators

The Quantum Max Cut (QMC) problem has emerged as a test-problem for designing approximation algorithms for local Hamiltonian problems. In this talk we attack this problem using the algebraic structure of QMC; we will explore the relationship between QMC and the representation theory of the symmetric group.

The first contribution is an application of noncommutative polynomial optimization techniques developed and championed by Navascués, Pironio and Acín (NPA) to give a new hierarchy of relaxations to Quantum Max Cut.

The hierarchy we present is based on polynomials in the swap operators. To prove completeness of this hierarchy, we give a finite presentation of the algebra generated by the swap operators. We find that level-2 of this new hierarchy is exact (up to tolerance 10^−7) on all QMC instances with uniform edge weights on small graphs.
The second contribution of this talk is a polynomial-time algorithm that exactly computes the maximum eigenvalue of the QMC Hamiltonian for certain graphs, including graphs that can be ``decomposed'' as a signed combination of cliques. A special case of the latter are complete bipartite graphs with uniform edge-weights, for which exact solutions are known from the work of Lieb and Mattis (1962).

The talk is based on joint work with Adam Bene Watts, Anirban Chowdhury, Aidan Epperly, Bill Helton, and work in progress with Tea Štrekelj and Jurij Volčič.