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:20240310T070000
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:EST
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
DTSTART:20231105T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:69eca21d90f71
DTSTART;TZID=America/Toronto:20240604T150000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20240604T160000
URL:https://uwaterloo.ca/institute-for-quantum-computing/events/quantum-cir
 cuit-lower-bounds-and-role-structure-quantum
SUMMARY:Quantum circuit lower bounds and the role of structure in quantum\n
 advantage.
CLASS:PUBLIC
DESCRIPTION:MATH/CS SEMINAR - JOSEPH SLOTE\, CALTECH\n\nZOOM ONLY\n\nAn imp
 ortant challenge in quantum computing is to develop quantum\ncircuit lower
  bound techniques beyond lightcone arguments. Towards\nthis goal\, we exam
 ine a circuit model formed from a shallow quantum\ncircuit composed with a
  classical AC0 circuit and ask whether this\nmodel can compute parity. We 
 then bridge ideas from Fourier analysis\,\ninfo-theoretic cryptography\, a
 nd nonlocal games to settle this\nquestion in several cases. We'll also di
 scuss implications for a\nsearch-decision dichotomy in unstructured quantu
 m advantage\, a\nphenomenon that was recently understood in the context of
  query\ncomplexity: for unstructured (promise-free) query problems\,\nexpo
 nential quantum advantage can exist for search problems but never\nfor dec
 ision problems.\n\nBased on https://arxiv.org/abs/2311.13679.
DTSTAMP:20260425T111437Z
END:VEVENT
END:VCALENDAR