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:Depth-Optimal Quantum Compilation\n\nFrancisca Vasconcelos | UC Berkeley\n\nWe achieve the first constant-depth circuit for arbitrary single-qubit gate synthesis. Unlike prior approaches\, the construction is fully unitary and requires no pre-supplied catalyst. For any constant δ>0\, it ε-approximates an arbitrary single-qubit gate using O(log1+δ(1/ε)) clean ancillae\, Hadamard and T single-qubit gates\, O(log(1/ε))-width generalized Toffoli gates\, and sublogarithmic-width Fan-Out gates. We further eliminate Fan-Out entirely\, showing that Hadamard\, T\, and generalized Toffoli gates alone suffice for constant-depth synthesis. When restricted to the standard bounded-width gate model\, our construction has depth O(loglog(1/ε))\, and we prove a matching Ω(loglog(1/ε))-depth lower bound. Overall\, we establish that Θ(loglog(1/ε))-depth is unavoidable with only bounded width gates\, yet allowing even logarithmic-width multi-qubit gates suffices to achieve constant-depth synthesis.\n\nThese results also reveal new structure in shallow quantum circuit complexity. We give a depth-preserving real simulation of bounded-error decision computation\, showing that every depth-d QAC circuit can be simulated in depth O(d) using only Hadamard\, X\, and generalized Toffoli gates. Thus arbitrary single-qubit rotations and complex amplitudes do not increase the bounded-error decision power of QAC\, even at constant depth. In particular\, this reduces the long-standing conjecture Parity∉QAC0 to proving a Parity lower bound against circuits consisting only of Hadamard\, X\, and generalized Toffoli gates. More generally\, this real normal form exposes a direct correspondence between the standard shallow-depth quantum circuit hierarchy and a hierarchy of Forrelation circuits with restricted oracle families.
X-ALT-DESC;FMTTYPE=text/html:Depth-Optimal Quantum Compilation<br />Francisca Vasconcelos | UC Berkeley<br />We achieve the first constant-depth circuit for arbitrary single-qubit gate synthesis. Unlike prior approaches, the construction is fully unitary and requires no pre-supplied catalyst. For any constant δ&gt;0, it ε-approximates an arbitrary single-qubit gate using O(log1+δ(1/ε)) clean ancillae, Hadamard and T single-qubit gates, O(log(1/ε))-width generalized Toffoli gates, and sublogarithmic-width Fan-Out gates. We further eliminate Fan-Out entirely, showing that Hadamard, T, and generalized Toffoli gates alone suffice for constant-depth synthesis. When restricted to the standard bounded-width gate model, our construction has depth O(loglog(1/ε)), and we prove a matching Ω(loglog(1/ε))-depth lower bound. Overall, we establish that Θ(loglog(1/ε))-depth is unavoidable with only bounded width gates, yet allowing even logarithmic-width multi-qubit gates suffices to achieve constant-depth synthesis.<br><br>These results also reveal new structure in shallow quantum circuit complexity. We give a depth-preserving real simulation of bounded-error decision computation, showing that every depth-d QAC circuit can be simulated in depth O(d) using only Hadamard, X, and generalized Toffoli gates. Thus arbitrary single-qubit rotations and complex amplitudes do not increase the bounded-error decision power of QAC, even at constant depth. In particular, this reduces the long-standing conjecture Parity∉QAC0 to proving a Parity lower bound against circuits consisting only of Hadamard, X, and generalized Toffoli gates. More generally, this real normal form exposes a direct correspondence between the standard shallow-depth quantum circuit hierarchy and a hierarchy of Forrelation circuits with restricted oracle families.
UID:61f2e9c068bb4f61bda83fd5817cd1dbaddeventcom
SUMMARY:IQC Math and CS seminar featuring Francisca Vasconcelos
DTSTART;TZID=America/New_York:20261105T130000
DTEND;TZID=America/New_York:20261105T140000
DTSTAMP:20261028T021217Z
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