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:69eb6a367ac2d
DTSTART;TZID=America/Toronto:20240423T150000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20240423T160000
URL:https://uwaterloo.ca/institute-for-quantum-computing/events/quantum-pol
 ynomial-hierarchies-karp-lipton-and-lower-bounds
LOCATION:QNC - Quantum Nano Centre 200 University Avenue West 1201 Waterloo
  ON N2L 3G1 Canada
SUMMARY:Quantum Polynomial Hierarchies: Karp-Lipton and Lower Bounds
CLASS:PUBLIC
DESCRIPTION:CS/MATH SEMINAR - AVANTIKA AGARWAL IQC\n\nQuantum-Nano Centre\,
  200 University Ave West\, Room QNC 1201 + ZOOM\nWaterloo\, ON CA N2L 3G1\
 n\nThe Polynomial-Time Hierarchy (PH) is a staple of classical complexity\
 ntheory\, with applications spanning randomized computation to circuit\nlo
 wer bounds to ''quantum advantage'' analyses for near-term quantum\ncomput
 ers. Quantumly\, however\, even though at least four definitions\nof quant
 um PH exist\, it has been challenging to prove analogues for\nthese or eve
 n basic facts from PH. This work studies three\nquantum-verifier based gen
 eralizations of PH\, two of which are from\n[Gharibian\, Santha\, Sikora\,
  Sundaram\, Yirka\, 2022] and use classical\nstrings (QCPH) and quantum mi
 xed states (QPH) as proofs\, and one of\nwhich is new to this work\, utili
 zing quantum pure states (pureQPH) as\nproofs. We first talk about solutio
 ns to open problems from GSSSY22\nwhich include a collapse theorem for QCP
 H and a quantum-classical\nKarp-Lipton. We then talk about our results for
  pureQPH\, including\nlower bounds relating QCPH to pureQPH\, and finally 
 discuss some\ninteresting open problems related to QCPH. This talk is base
 d on\nhttps://arxiv.org/abs/2401.01633\, a joint work with Sevag Gharibian
 \,\nVenkata Koppula and Dorian Rudolph.
DTSTAMP:20260424T130350Z
END:VEVENT
END:VCALENDAR