Conference abstracts

Session B2 - Graph Theory and Combinatorics - Semi-plenary talk

July 14, 14:30 ~ 15:20

Gaps Between Classical Satisfiability Problems and their Quantum Relaxations

Albert Atserias

Universitat Polit├Ęcnica de Catalunya, Spain   -   atserias@cs.upc.edu

An instance of the constraint satisfaction problem asks for an assignment of values to variables in such a way that a given set of local constraints are satisfied. One can think of such problems operationally in the form of a game: Alice provides value-assignments that satisfy given constraints on request, Bob provides value-assignments to the variables also on request, and a referee checks if Alice's and Bob's assignments are consistent with one another. Many problems of graph theory, combinatorics, logic and computer science fall within this abstract framework. Since the problem of deciding if Alice and Bob have a winning strategy is NP-hard to solve in general, a common approach to provide structure to the problem is to consider relaxations of it where the variables range over larger but more structured domains. We study a relaxation that is actually motivated by a modeling issue: the universe appears to be quantum mechanical, so Alice and Bob could use strategies that are correlated through quantum entanglement. In this relaxation, which is well-studied in quantum information theory, the constraints are represented by polynomials through their Fourier transform, and the variables range over bounded linear operators over a Hilbert space. Among other results we obtain a complete understanding of which types of Boolean constraints show a discrepancy between quantum and classical strategies.

View abstract PDF



FoCM 2017, based on a nodethirtythree design.