Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

The Quantum Max Cut (QMC) problem has emerged as a test-problem for designing approximation algorithms for local Hamiltonian problems. In this talk I’ll describe an approach to solving this problem using the algebraic structure of QMC, in particular the relationship between the quantum max cut Hamiltonian and the representation theory of the symmetric group. The first major result is an extension of non-commutative Sum of Squares (ncSoS) optimization techniques to give a new hierarchy of relaxations to Quantum Max Cut. This hierarchy is based on optimizations over polynomials in the qubit swap operators. This is in contrast to the “standard” quantum Lasserre Hierarchy, which is based on polynomials expressed in terms of the Pauli matrices. The second major result covered will be 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. Our methods, which use representation theory of the symmetric group, can be seen as a generalization of the Lieb-Mattis result.

Free pizzas:)