BEGIN:VCALENDAR
PRODID:-//AddEvent Inc//AddEvent.com v1.7//EN
VERSION:2.0
BEGIN:VTIMEZONE
TZID:America/New_York
BEGIN:STANDARD
DTSTART:20261101T010000
RRULE:FREQ=YEARLY;BYDAY=1SU;BYMONTH=11
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
END:STANDARD
BEGIN:DAYLIGHT
DTSTART:20260308T030000
RRULE:FREQ=YEARLY;BYDAY=2SU;BYMONTH=3
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
DESCRIPTION:Pseudo-Deterministic Quantum Algorithms\n\nHugo Aaronson | University of Cambridge\n\nWe initiate a systematic study of pseudo-deterministic quantum algorithms. These are quantum algorithms that\, for any input\, output a canonical solution with high probability. Focusing on the query complexity model\, our main contributions include the following complexity separations\, which require new lower bound techniques specifically tailored to pseudo-determinism:\n\nWe exhibit a problem\, Avoid One Encrypted String (AOES)\, whose classical randomized query complexity is O(1) but is maximally hard for pseudo-deterministic quantum algorithms (Ω(N) query complexity).\n\nWe exhibit a problem\, Quantum-Locked Estimation (QL-Estimation)\, for which pseudo-deterministic quantum algorithms admit an exponential speed-up over classical pseudo-deterministic algorithms (O(log(N)) vs. Θ(√N))\, while the randomized query complexity is O(1).\n\nComplementing these separations\, we show that for any total problem R\, pseudo-deterministic quantum algorithms admit at most a quintic advantage over deterministic algorithms\, i.e.\, D(R) = O˜(psQ(R)^5). On the algorithmic side\, we identify a class of quantum search problems that can be made pseudo-deterministic with small overhead\, including Grover search\, element distinctness\, triangle finding\, k-sum\, and graph collision.\n\nLocation\n\nQNC 3206\n\nOnline on Zoom\n\nMeeting ID: 955 2636 6664\n\nPasscode: 419811
X-ALT-DESC;FMTTYPE=text/html:Pseudo-Deterministic Quantum Algorithms<br />Hugo Aaronson | University of Cambridge<br />We initiate a systematic study of pseudo-deterministic quantum algorithms. These are quantum algorithms that, for any input, output a canonical solution with high probability. Focusing on the query complexity model, our main contributions include the following complexity separations, which require new lower bound techniques specifically tailored to pseudo-determinism:<br><br>We exhibit a problem, Avoid One Encrypted String (AOES), whose classical randomized query complexity is O(1) but is maximally hard for pseudo-deterministic quantum algorithms (Ω(N) query complexity).<br />We exhibit a problem, Quantum-Locked Estimation (QL-Estimation), for which pseudo-deterministic quantum algorithms admit an exponential speed-up over classical pseudo-deterministic algorithms (O(log(N)) vs. Θ(√N)), while the randomized query complexity is O(1).<br><br>Complementing these separations, we show that for any total problem R, pseudo-deterministic quantum algorithms admit at most a quintic advantage over deterministic algorithms, i.e., D(R) = O˜(psQ(R)^5). On the algorithmic side, we identify a class of quantum search problems that can be made pseudo-deterministic with small overhead, including Grover search, element distinctness, triangle finding, k-sum, and graph collision.<br><br>Location<br />QNC 3206<br />Online on Zoom<br />Meeting ID: 955 2636 6664<br />Passcode: 419811
UID:79a8d5237b4440d8ada029a567b010e8addeventcom
SUMMARY:IQC Math and CS seminar featuring Hugo Aaronson
DTSTART;TZID=America/New_York:20260417T140000
DTEND;TZID=America/New_York:20260417T150000
DTSTAMP:20260616T014350Z
TRANSP:OPAQUE
STATUS:CONFIRMED
SEQUENCE:0
LOCATION:QNC 3206
X-MICROSOFT-CDO-BUSYSTATUS:BUSY
BEGIN:VALARM
TRIGGER:-PT30M
ACTION:DISPLAY
DESCRIPTION:Reminder
END:VALARM
END:VEVENT
END:VCALENDAR