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:All Unitaries Have Constant Depth Quantum Circuits\n\nBarak Nehoran | Columbia\n\nIt is well-known that every n-qubit unitary can be implemented by a 2^O(n)-depth quantum circuit using single- and two-qubit gates. It has been open whether exponential depth is *necessary* for general unitaries\, even when allowing an unlimited number of ancilla qubits. Here we show\, perhaps surprisingly\, that all unitaries can be implemented exactly by a circuit of one- and two-qubit gates of depth 𝗉𝗈𝗅𝗒(n) with 2^O(n) ancilla qubits. In other words\, every n-qubit unitary can be parallelized to polynomial depth. In fact\, our depth bound is *linear* in n\, which is the best possible\, and an exponential improvement on the previous best bound of 2^n/2 due to Rosenthal [TQC 2022\, Quantum 2026]. Moreover\, if we allow unbounded fan-out gates\, these circuits can be further reduced to *constant* depth. Our construction takes advantage of a novel relationship connecting the unitary synthesis problem of Aaronson and Kuperberg to locally-decodable codes and private information retrieval from complexity theory and cryptography\, and has a natural interpretation in bosonic quantum computation.
X-ALT-DESC;FMTTYPE=text/html:All Unitaries Have Constant Depth Quantum Circuits<br />Barak Nehoran | Columbia<br />It is well-known that every n-qubit unitary can be implemented by a 2^O(n)-depth quantum circuit using single- and two-qubit gates. It has been open whether exponential depth is *necessary* for general unitaries, even when allowing an unlimited number of ancilla qubits. Here we show, perhaps surprisingly, that all unitaries can be implemented exactly by a circuit of one- and two-qubit gates of depth 𝗉𝗈𝗅𝗒(n) with 2^O(n) ancilla qubits. In other words, every n-qubit unitary can be parallelized to polynomial depth. In fact, our depth bound is *linear* in n, which is the best possible, and an exponential improvement on the previous best bound of 2^n/2 due to Rosenthal [TQC 2022, Quantum 2026]. Moreover, if we allow unbounded fan-out gates, these circuits can be further reduced to *constant* depth. Our construction takes advantage of a novel relationship connecting the unitary synthesis problem of Aaronson and Kuperberg to locally-decodable codes and private information retrieval from complexity theory and cryptography, and has a natural interpretation in bosonic quantum computation.
UID:9fb60605603f4150926c4dd618543c34addeventcom
SUMMARY:IQC Math and CS seminar featuring Barak Nehoran
DTSTART;TZID=America/New_York:20261029T130000
DTEND;TZID=America/New_York:20261029T140000
DTSTAMP:20261021T075809Z
TRANSP:OPAQUE
STATUS:CONFIRMED
SEQUENCE:0
LOCATION:QNC 1201
X-MICROSOFT-CDO-BUSYSTATUS:BUSY
BEGIN:VALARM
TRIGGER:-PT30M
ACTION:DISPLAY
DESCRIPTION:Reminder
END:VALARM
END:VEVENT
END:VCALENDAR