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:Multi-qubit Toffoli with exponentially fewer T gates\nRobin Kothari - Google\nAbstract: \nPrior work of Beverland et al. has shown that any exact Clifford+T implementation of the n-qubit Toffoli gate must use at least n T gates. Here we show how to get away with exponentially fewer T gates\, at the cost of incurring a tiny 1/poly(n) error that can be neglected in most practical situations. More precisely\, the n-qubit Toffoli gate can be implemented to within error ϵ in the diamond distance by a randomly chosen Clifford+T circuit with at most O(log(1/ϵ)) T gates. We also give a matching Ω(log(1/ϵ)) lower bound that establishes optimality\, and we show that any purely unitary implementation achieving even constant error must use Ω(n) T gates. We also extend our sampling technique to implement other Boolean functions. Finally\, we describe upper and lower bounds on the T-count of Boolean functions in terms of non-adaptive parity decision tree complexity and its randomized analogue.\nLocation: QNC 0101
X-ALT-DESC;FMTTYPE=text/html:Multi-qubit Toffoli with exponentially fewer T gates<br />Robin Kothari - Google<br />Abstract: <br />Prior work of Beverland et al. has shown that any exact Clifford+T implementation of the n-qubit Toffoli gate must use at least n T gates. Here we show how to get away with exponentially fewer T gates, at the cost of incurring a tiny 1/poly(n) error that can be neglected in most practical situations. More precisely, the n-qubit Toffoli gate can be implemented to within error ϵ in the diamond distance by a randomly chosen Clifford+T circuit with at most O(log(1/ϵ)) T gates. We also give a matching Ω(log(1/ϵ)) lower bound that establishes optimality, and we show that any purely unitary implementation achieving even constant error must use Ω(n) T gates. We also extend our sampling technique to implement other Boolean functions. Finally, we describe upper and lower bounds on the T-count of Boolean functions in terms of non-adaptive parity decision tree complexity and its randomized analogue.<br />Location: QNC 0101
UID:ed7a2db0349a4b5382b2ca545b5a04f1addeventcom
SUMMARY:IQC Special Seminar featuring Robin Kothari
DTSTART;TZID=America/New_York:20260729T090000
DTEND;TZID=America/New_York:20260729T100000
DTSTAMP:20260726T022619Z
TRANSP:OPAQUE
STATUS:CONFIRMED
SEQUENCE:0
LOCATION:QNC 0101
X-MICROSOFT-CDO-BUSYSTATUS:BUSY
BEGIN:VALARM
TRIGGER:-PT30M
ACTION:DISPLAY
DESCRIPTION:Reminder
END:VALARM
END:VEVENT
END:VCALENDAR