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:Wednesday May 13\, 2-3pm\, QNC 4104\n\nSpeaker: Alex May (IQC/PI)\n\nTitle: Magic and communication complexity\n\nAbstract:\n\nWe establish novel connections between magic in quantum circuits and communication complexity. In particular\, we show that functions computable with low magic have low communication cost.\n\nOur first result shows that the š–£ā€– (deterministic simultaneous message passing) cost of a Boolean function f is at most the number of single-qubit magic gates in a quantum circuit computing f with any quantum advice state. If we allow mid-circuit measurements and adaptive circuits\, we obtain an upper bound on the two-way communication complexity of f in terms of the magic + measurement cost of the circuit for f. As an application\, we obtain magic-count lower bounds of Ī©(n) for the n-qubit generalized Toffoli gate as well as the n-qubit quantum multiplexer.\n\nOur second result gives a general method to transform š–°ā€–āˆ— protocols (simultaneous quantum messages with shared entanglement) into š–±ā€–āˆ— protocols (simultaneous classical messages with shared entanglement) which incurs only a polynomial blowup in the communication and entanglement complexity\, provided the referee's action in the š–°ā€–āˆ— protocol is implementable in constant T-depth. The resulting š–±ā€–āˆ— protocols satisfy strong privacy constraints and are š–Æš–²š–¬āˆ— protocols (private simultaneous message passing with shared entanglement)\, where the referee learns almost nothing about the inputs other than the function value. As an application\, we demonstrate n-bit partial Boolean functions whose š–±ā€–āˆ— complexity is polylog(n) and whose š–± (interactive randomized) complexity is nĪ©(1)\, establishing the first exponential separations between š–±ā€–āˆ— and š–± for Boolean functions. X-ALT-DESC;FMTTYPE=text/html:Wednesday May 13, 2-3pm, QNC 4104
Speaker: Alex May (IQC/PI)
Title: Magic and communication complexity
Abstract:

We establish novel connections between magic in quantum circuits and communication complexity. In particular, we show that functions computable with low magic have low communication cost.

Our first result shows that the š–£ā€– (deterministic simultaneous message passing) cost of a Boolean function f is at most the number of single-qubit magic gates in a quantum circuit computing f with any quantum advice state. If we allow mid-circuit measurements and adaptive circuits, we obtain an upper bound on the two-way communication complexity of f in terms of the magic + measurement cost of the circuit for f. As an application, we obtain magic-count lower bounds of Ī©(n) for the n-qubit generalized Toffoli gate as well as the n-qubit quantum multiplexer.

Our second result gives a general method to transform š–°ā€–āˆ— protocols (simultaneous quantum messages with shared entanglement) into š–±ā€–āˆ— protocols (simultaneous classical messages with shared entanglement) which incurs only a polynomial blowup in the communication and entanglement complexity, provided the referee's action in the š–°ā€–āˆ— protocol is implementable in constant T-depth. The resulting š–±ā€–āˆ— protocols satisfy strong privacy constraints and are š–Æš–²š–¬āˆ— protocols (private simultaneous message passing with shared entanglement), where the referee learns almost nothing about the inputs other than the function value. As an application, we demonstrate n-bit partial Boolean functions whose š–±ā€–āˆ— complexity is polylog(n) and whose š–± (interactive randomized) complexity is nĪ©(1), establishing the first exponential separations between š–±ā€–āˆ— and š–± for Boolean functions. UID:1777653612addeventcom SUMMARY:IQC Math and CS seminar featuring Alex May DTSTART;TZID=America/New_York:20260513T140000 DTEND;TZID=America/New_York:20260513T150000 DTSTAMP:20260501T164012Z 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