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:Parity ∉ QAC0 ⟺ QAC0 is Fourier-Concentrated\nMalvika Joshi | UC Berkeley\nA major open problem in understanding shallow quantum circuits (QAC0) is whether they can compute Parity. We show that this question is solely about the Fourier spectrum of QAC0: any QAC0 circuit with non-negligible high-level Fourier mass suffices to exactly compute PARITY in QAC0. Thus\, proving a quantum analog of the seminal LMN theorem for AC0 is necessary to bound the quantum circuit complexity of PARITY.\nIn the other direction\, LMN does not fully capture the limitations of AC0. For example\, despite MAJORITY having 99% of its weight on low-degree Fourier coefficients\, no AC0 circuit can non-trivially correlate with it. In contrast\, we provide a QAC0 circuit that achieves (1−o(1)) correlation with MAJORITY\, establishing the first average-case decision separation between AC0 and QAC0. This suggests a uniquely quantum phenomenon: unlike in the classical setting\, Fourier concentration may largely characterize the power of QAC0.\nPARITY is also known to be equivalent in QAC0 to inherently quantum tasks such as preparing GHZ states to high fidelity. We extend this equivalence to a broad class of state-synthesis tasks. We demonstrate that existing metrics such as trace distance\, fidelity\, and mutual information are insufficient to capture these states and introduce a new measure\, felinity. We prove that preparing any state with non-negligible felinity\, or derived states such as poly(n)-weight Dicke states\, implies PARITY ∈ QAC0.\nLocation\n\n• QNC 4104\n• Online on ZoomMeeting ID: 912 8146 6256 \nPasscode\n: 494237\n\n X-ALT-DESC;FMTTYPE=text/html:Parity ∉ QAC0 ⟺ QAC0 is Fourier-Concentrated
Malvika Joshi | UC Berkeley
A major open problem in understanding shallow quantum circuits (QAC0) is whether they can compute Parity. We show that this question is solely about the Fourier spectrum of QAC0: any QAC0 circuit with non-negligible high-level Fourier mass suffices to exactly compute PARITY in QAC0. Thus, proving a quantum analog of the seminal LMN theorem for AC0 is necessary to bound the quantum circuit complexity of PARITY.
In the other direction, LMN does not fully capture the limitations of AC0. For example, despite MAJORITY having 99% of its weight on low-degree Fourier coefficients, no AC0 circuit can non-trivially correlate with it. In contrast, we provide a QAC0 circuit that achieves (1−o(1)) correlation with MAJORITY, establishing the first average-case decision separation between AC0 and QAC0. This suggests a uniquely quantum phenomenon: unlike in the classical setting, Fourier concentration may largely characterize the power of QAC0.
PARITY is also known to be equivalent in QAC0 to inherently quantum tasks such as preparing GHZ states to high fidelity. We extend this equivalence to a broad class of state-synthesis tasks. We demonstrate that existing metrics such as trace distance, fidelity, and mutual information are insufficient to capture these states and introduce a new measure, felinity. We prove that preparing any state with non-negligible felinity, or derived states such as poly(n)-weight Dicke states, implies PARITY ∈ QAC0.
Location
UID:3edef27ce0004dd68d89760092cf011baddeventcom SUMMARY:IQC Math and CS seminar featuring Malvika Joshi DTSTART;TZID=America/New_York:20260708T140000 DTEND;TZID=America/New_York:20260708T150000 DTSTAMP:20260624T211157Z TRANSP:OPAQUE STATUS:CONFIRMED SEQUENCE:0 X-MICROSOFT-CDO-BUSYSTATUS:BUSY BEGIN:VALARM TRIGGER:-PT30M ACTION:DISPLAY DESCRIPTION:Reminder END:VALARM END:VEVENT END:VCALENDAR