QUASAR weekly seminar talk.

• Date: Tuesday, October 21, 2025
• Time: 10:30 AM ET
• Location: STEM Complex
• Speaker: Lorenzo Ciardo
• Affiliation: Graz University of Technology

Abstract

Quantum pseudo-telepathy lies at the core of Bell’s Theorem on the incompatibility of quantum mechanics with local hidden-variable theories. In the language of two-player one-round games, this phenomenon occurs when the availability of quantum resources in the form of shared entanglement results in non-classical correlations between the players’ answers, which allow outperforming any classical strategy. In this talk, I will focus on the quantum chromatic number—the quantum counterpart of the classical chromatic number of graphs, introduced in [Cameron—Montanaro—Newman—Severini—Winter’07]. An exponential lower bound is known for the maximum gap between quantum and classical chromatic number, which measures the pseudo-telepathy occurring in the graph-coloring game. I will show that, conditional on the quantum pseudo-telepathy variants of Khot’s d-to-1 Conjecture [Khot’02] and Hastad’s inapproximability of linear equations [Hastad’01], the gap is unbounded. The proof of this result hinges on an algebraic connection between the occurrence of quantum pseudo-telepathy in two-player one-round games and the computational complexity of constraint satisfaction problems. In addition, I will present an (unconditional) upper bound on the gap in the case of entanglement resources of fixed dimension, coming from joint work with Demian Banakh, Marcin Kozik, and Jan Tulowiecki on the simulation of perfect quantum strategies for two-player one-round games via classical communication channels of small size.