Graph Games & Communication Complexity

Add to your list(s) Download to your calendar using vCal

• Pierre BOTTERON (Université de Toulouse)
• Thursday 05 December 2024, 14:30-14:50
• Seminar Room 1, Newton Institute.

If you have a question about this talk, please contact nobody.

QIAW02 - New trends at the intersection of quantum information theory, quantum groups and operator algebras

In quantum information, nonlocal games are particularly useful for differentiating classical, quantum, and non-signalling correlations. In this talk, we present a generalization of the graph isomorphism game, namely the “vertex distance game,” defined with a parameter D∈ℕ. We characterize its perfect strategies, both in the classical, quantum and non-signalling sense, and we connect this notion with a refinement of fractional isomorphism of graphs, namely D-fractional isomorphisms. Surprisingly, we observe that non-signalling strategies provide a finer distinction for this game than classical and quantum strategies since the parameter D is visible only in the non-signalling setting. Finally, we give connections of this game with communication complexity by generating a PR box from a perfect non-signalling strategy. This is a joint work with Moritz Weber [https://arxiv.org/pdf/2406.02199].

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

• All CMS events
• Featured lists
• INI info aggregator
• Isaac Newton Institute Seminar Series
• School of Physical Sciences
• Seminar Room 1, Newton Institute
• bld31

Note that ex-directory lists are not shown.