Quantum Constraint Satisfaction Problems 2026

The theme of this workshop lies at the intersection of two topics which have recently achieved breakthrough results that have enriched our understanding of computational complexity.

Background

Non-local games and \(\mathsf{MIP}^{*} = \mathsf{RE}\). The first result, succinctly summarized as \(\textsf{MIP}^{*} = \textsf{RE}\), concerns non-local games (also known as Bell inequalities in the physics literature, or multi-party verifier-prover games). These games provide a mathematical framework to study how information can be communicated with two parties that have access limited to shared resources. In a typical non-local game, we have two players, Alice and Bob which receive questions from a Verifier who is deciding a predicate. The players respond with answers aiming to convince the verifier that the predicate is true. Classical players can only use shared randomness for formulating their answers, whereas quantum players may share some quantum resource, e.g. an entangled pair of particles. Using quantum resources allows them to exhibit correlations that surpass classical limits. Roughly speaking, the result \(\textsf{MIP}^{*} = \textsf{RE}\) demonstrates that multiple provers with access to quantum resources are powerful enough to verify solutions to even uncomputable problems. Besides proving equality between two ostensibly different complexity classes, the work also refuted an open conjecture in functional analysis called Connes embedding problem. Thus, this result draws an important bridge between computability, quantum information, and mathematical physics.

CSPs and the dichotomy theorem. The second result is the Bulatov-Zhuk dichotomy (2017) and concerns constraint satisfaction problems (CSPs), which capture some of the most fundamental computational problems, including linear equations, graph colourings, and variants and generalizations of satisfiability. Informally, an instance of a CSP consists of a set of variables and a set of constraints, each depending on constantly many variables. Given an instance, the goal is to find an assignment of values to all the variables in such a way that all the constraints are satisfied. The Bulatov-Zhuk dichotomy theorem states that every constraint satisfaction problem is either tractable, i.e. solvable in polynomial time, or \(\textsf{NP}\)-complete. This is in stark contrast to the general class of decision problems, where it is known that if \(\textsf{P} \neq \textsf{NP}\), then there is an infinite hierarchy of problems between \(\textsf{P}\) and \(\textsf{NP}\) which are not polynomially-reducible to one another (Ladner’s classical theorem). This contrast conveys the fruitfulness of studying CSPs in order for us to understand the full complexity picture.

Quantum CSPs. Every CSP can be formulated as a non-local game, opening a path to studying quantum advantage for these problems. For example, consider the Mermin-Peres magic square. This is a Boolean CSP instance, consisting of variables \(x_1,\dots, x_9\) over the Boolean domain \(\{\pm 1\}\) and the following linear constraints written in the multiplicative notation:

This can be represented by a square, where the first three equations correspond to the rows and the remaining to the columns, depicted in the figure on the left.

The system of equations has no solution over the domain \(\{\pm 1\}\). Mermin showed that the system has an operator solution consisting of linear operators on a four-dimensional Hilbert space, depicted on the right; the matrices \(X, Y, Z\) are the well-known Pauli matrices. Mermin used this construction to prove the Bell-Kochen-Specker theorem on the impossibility to explain quantum mechanics via hidden variables. The solution exhibited in the figure can be used to construct a quantum strategy in the corresponding non-local game. Informally, this is achieved by performing the measurements that correspond to the operators in the table on an entangled quantum state shared between Alice and Bob.