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:On Scalable Pseudorandom Unitaries and the Unitary Synthesis Problem\n\nZvika Brakerski | Weizmann\n\nWe consider the task of constructing pseudorandom unitaries (PRUs) with scalable security\, i.e. families in which the security parameter may vary independently of the dimension (or input bit-length). It is not known whether scalable PRUs can be constructed. In this work we show that if scalable PRUs can be constructed via the prevailing paradigm for analyzing PRUs\, then there would be a positive solution to the Aaronson-Kuperberg unitary synthesis problem\, a longstanding question in quantum complexity theory about whether implementing arbitrary unitaries can be efficiently reduced to computing a Boolean function.\n\nSpecifically\, we formalize the notion of ROM-PRUs\, which are statistically secure PRUs in the random oracle model (ROM). All prior known constructions of cryptographically secure PRUs are based on a ROM-PRU construction. We prove novel connections between ROM-PRUs\, approximate unitary designs\, epsilon-nets over the unitary group\, and the unitary synthesis problem. In particular\, we prove that any unitary synthesis algorithm (and thus any ROM-PRU) must use a classical oracle with input length (2 - o(1)) log d bits\, where d is the dimension of the unitary to be implemented. This bound rules out all existing candidates for scalable PRUs in the literature.\n\nTogether\, these connections indicate that ROM-PRUs provide a fruitful idealized model for studying pseudorandom unitaries.\n\nLocation\n\nQNC 4104
X-ALT-DESC;FMTTYPE=text/html:On Scalable Pseudorandom Unitaries and the Unitary Synthesis Problem<br />Zvika Brakerski | Weizmann<br />We consider the task of constructing pseudorandom unitaries (PRUs) with scalable security, i.e. families in which the security parameter may vary independently of the dimension (or input bit-length). It is not known whether scalable PRUs can be constructed. In this work we show that if scalable PRUs can be constructed via the prevailing paradigm for analyzing PRUs, then there would be a positive solution to the Aaronson-Kuperberg unitary synthesis problem, a longstanding question in quantum complexity theory about whether implementing arbitrary unitaries can be efficiently reduced to computing a Boolean function.<br><br>Specifically, we formalize the notion of ROM-PRUs, which are statistically secure PRUs in the random oracle model (ROM). All prior known constructions of cryptographically secure PRUs are based on a ROM-PRU construction. We prove novel connections between ROM-PRUs, approximate unitary designs, epsilon-nets over the unitary group, and the unitary synthesis problem. In particular, we prove that any unitary synthesis algorithm (and thus any ROM-PRU) must use a classical oracle with input length (2 - o(1)) log d bits, where d is the dimension of the unitary to be implemented. This bound rules out all existing candidates for scalable PRUs in the literature.<br><br>Together, these connections indicate that ROM-PRUs provide a fruitful idealized model for studying pseudorandom unitaries.<br><br>Location<br />QNC 4104
UID:1780815931addeventcom
SUMMARY:IQC Math and CS seminar featuring Zvika Brakerski
DTSTART;TZID=America/New_York:20260624T140000
DTEND;TZID=America/New_York:20260624T150000
DTSTAMP:20260607T070531Z
TRANSP:OPAQUE
STATUS:CONFIRMED
SEQUENCE:0
LOCATION:QNC 4104
X-MICROSOFT-CDO-BUSYSTATUS:BUSY
BEGIN:VALARM
TRIGGER:-PT30M
ACTION:DISPLAY
DESCRIPTION:Reminder
END:VALARM
END:VEVENT
END:VCALENDAR