Extra QLunch: Taro Spirig

Speaker: Taro Spirig from QMATH

Title: Approximation algorithms for noncommutative constraint satisfaction problems

Abstract: Constraint satisfaction problems (CSPs) have been widely studied in computer science in the context of NP-hardness and approximation algorithms. For example, the problem of finding optimal k-colourings of graphs, Max-Cut(k), is NP-hard, but it is easy to approximate in the sense that we can efficiently find colourings which are close to the optimal one. 

We study a noncommutative variant of CSPs (NC-CSPs) that is central in quantum information, where the variables of CSPs are replaced by operators. In this context, even approximating NC-CSPs is known to be much harder than the classical case, in fact it is uncomputably hard. On the other hand, NC-Max-Cut(2) becomes efficiently solvable. Apart from these two facts, not much was previously known about the complexity of NC-CSPs. 

 We introduce a framework for designing approximation algorithms for NC-CSPs based on SDP relaxations. This allows us to find large classes of NC-CSPs that are efficiently approximable but not efficiently solvable. To determine the quality of our approximation algorithm, we prove a random matrix theory result that characterises the distribution of the relative angles between eigenvalues of random unitaries using tools from free probability. 

 This talk is based on work with Eric Culf and Hamoon Mousavi (arxiv.org/abs/2312.16765).