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
- QNC 4104
- Online on Zoom
-
Meeting ID: 912 8146 6256
Passcode
: 494237
-
Add event to calendar
