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:6827a38edf71c
DTSTART;TZID=America/Toronto:20250512T113000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20250512T123000
URL:/combinatorics-and-optimization/events/algebraic-gr
 aph-theory-lorenzo-ciardo
SUMMARY:Algebraic Graph Theory-Lorenzo Ciardo
CLASS:PUBLIC
DESCRIPTION:Summary \n\nTITLE: Alice\, Bob\, and colours: An algebraic app
 roach to quantum\nadvantage\n\nSPEAKER:\n\nLorenzo Ciardo\n\nAFFILIATION:\
 n University of Oxford\n\nLOCATION:\n Please contact Sabrina Lato for Zo
 om link.\n\nABSTRACT: Two-player one-round games exhibit quantum advantag
 e if the\navailability of quantum resources results in non-classical\ncorr
 elations between the players' answers\, which allow outperforming\nany cla
 ssical strategy. The first part of the talk illustrates a link\nbetween (i
 ) the occurrence of quantum advantage in a game\, and (ii)\nthe complexity
  of the corresponding classical computational problem.\nIn particular\, I 
 will show that both (i) and (ii) are determined by\nthe same algebraic inv
 ariants of the game\, known as polymorphisms.\nThis allows transferring me
 thods from the universal-algebraic theory\nof constraint satisfaction to t
 he setting of quantum advantage. In\nparticular\, this approach yields a c
 omplete characterisation of the\noccurrence of quantum advantage for games
  played on graphs.   \n\nThe second part of the talk outlines recent wor
 k on the quantum\nchromatic number introduced in\n[Cameron--Montanaro--New
 man--Severini--Winter'07]. The gap between\nthis parameter and its classic
 al counterpart is a measure of quantum\nadvantage for the graph colouring 
 game. Using the polymorphic\napproach\, I will show that the maximum gap i
 s linear when the quantum\nchromatic number makes use of entangled strateg
 ies on a constant\nnumber of qubits. In contrast\, in the case of unlimite
 d entanglement\nresources\, I will prove the existence of graphs whose qua
 ntum\nchromatic number is 3 and whose classical chromatic number is\narbit
 rarily large\, conditional to the quantum variants of Khot's\nd-to-1 Conje
 cture [Khot'02] and Håstad's inapproximability of linear\nequations [Hås
 tad'01].\n 
DTSTAMP:20250516T204358Z
END:VEVENT
END:VCALENDAR