BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Drupal iCal API//EN
X-WR-CALNAME:Events items teaser
X-WR-TIMEZONE:America/Toronto
BEGIN:VTIMEZONE
TZID:America/Toronto
X-LIC-LOCATION:America/Toronto
BEGIN:DAYLIGHT
TZNAME:EDT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
DTSTART:20250309T070000
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:EST
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
DTSTART:20241103T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:69d45ee9b1e61
DTSTART;TZID=America/Toronto:20250512T113000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20250512T123000
URL:https://uwaterloo.ca/combinatorics-and-optimization/events/algebraic-gr
 aph-theory-lorenzo-ciardo
SUMMARY:Algebraic Graph Theory-Lorenzo Ciardo
CLASS:PUBLIC
DESCRIPTION:TITLE: Alice\, Bob\, and colours: An algebraic approach to qua
 ntum\nadvantage\n\nSPEAKER:\n\nLorenzo Ciardo\n\nAFFILIATION:\n University
  of Oxford\n\nLOCATION:\n Please contact Sabrina Lato for Zoom link.\n\n
 ABSTRACT: Two-player one-round games exhibit quantum advantage if the\nav
 ailability of quantum resources results in non-classical\ncorrelations bet
 ween the players' answers\, which allow outperforming\nany classical strat
 egy. The first part of the talk illustrates a link\nbetween (i) the occurr
 ence of quantum advantage in a game\, and (ii)\nthe complexity of the corr
 esponding classical computational problem.\nIn particular\, I will show th
 at both (i) and (ii) are determined by\nthe same algebraic invariants of t
 he game\, known as polymorphisms.\nThis allows transferring methods from t
 he universal-algebraic theory\nof constraint satisfaction to the setting o
 f quantum advantage. In\nparticular\, this approach yields a complete char
 acterisation of the\noccurrence of quantum advantage for games played on g
 raphs.   \n\nThe second part of the talk outlines recent work on the qua
 ntum\nchromatic number introduced in\n[Cameron--Montanaro--Newman--Severin
 i--Winter'07]. The gap between\nthis parameter and its classical counterpa
 rt is a measure of quantum\nadvantage for the graph colouring game. Using 
 the polymorphic\napproach\, I will show that the maximum gap is linear whe
 n the quantum\nchromatic number makes use of entangled strategies on a con
 stant\nnumber of qubits. In contrast\, in the case of unlimited entangleme
 nt\nresources\, I will prove the existence of graphs whose quantum\nchroma
 tic number is 3 and whose classical chromatic number is\narbitrarily large
 \, conditional to the quantum variants of Khot's\nd-to-1 Conjecture [Khot'
 02] and Håstad's inapproximability of linear\nequations [Håstad'01].
DTSTAMP:20260407T013329Z
END:VEVENT
END:VCALENDAR