QLunch: Taro Spirig

Speaker: Taro Spirig

Title: A Quantum Unique Games Conjecture

Abstract: In this talk, I will discuss the complexity of nonlocal games, focusing on their description as quantum extensions of constraint satisfaction problems (CSPs). 

In classical theoretical computer science, after the NP-hardness of CSPs such as 3SAT or MaxCut was established, a natural question was whether these problems remain hard to approximate. To answer this question, the unique games conjecture (UGC) played a crucial role. 

It is now known that the quantum extensions of some of these CSPs are also hard, in fact even undecidable. However, their hardness of approximation remains largely unresolved. Indeed, one major issue is that it is challenging to state a quantum version of UGC. In this talk, I will show that a new perspective on quantum extensions of CSPs lets us state a quantum UGC and derive similar consequences as in the classical setting.

Based on joint work with Hamoon Mousavi.