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:20230312T070000
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:EST
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
DTSTART:20231105T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:69ed9e81e6265
DTSTART;TZID=America/Toronto:20240130T150000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20240130T160000
URL:https://uwaterloo.ca/institute-for-quantum-computing/events/power-adapt
 ivity-quantum-query-algorithms
SUMMARY:The Power of Adaptivity in Quantum Query Algorithms
CLASS:PUBLIC
DESCRIPTION:CS MATH SEMINAR - KEWEN WU\, UC BERKELEY (ZOOM + IN PERSON)\n\n
 200 University Ave W. Waterloo On. N2G 4K3 QNC 1201\n\nMotivated by limita
 tions on the depth of near-term quantum devices\, we\nstudy the depth-comp
 utation trade-off in the query model\, where the\ndepth corresponds to the
  number of adaptive query rounds and the\ncomputation per layer correspond
 s to the number of parallel queries\nper round. We achieve the strongest k
 nown separation between quantum\nalgorithms with r versus r−1 rounds of 
 adaptivity. We do so by using\nthe k-fold Forrelation problem introduced b
 y Aaronson and Ambainis\n(SICOMP'18). For k=2r\, this problem can be solve
 d using an r round\nquantum algorithm with only one query per round\, yet 
 we show that any\nr−1 round quantum algorithm needs an exponential (in t
 he number of\nqubits) number of parallel queries per round.\n\nOur results
  are proven following the Fourier analytic machinery\ndeveloped in recent 
 works on quantum-classical separations. The key\nnew component in our resu
 lt are bounds on the Fourier weights of\nquantum query algorithms with bou
 nded number of rounds of adaptivity.\nThese may be of independent interest
  as they distinguish the\npolynomials that arise from such algorithms from
  arbitrary bounded\npolynomials of the same degree.\n\nJoint work with Uma
  Girish\, Makrand Sinha\, Avishay Tal
DTSTAMP:20260426T051129Z
END:VEVENT
END:VCALENDAR