Improved Lower Bounds for QAC0
In this work, we prove the strongest known lower bounds for QAC$^0$, allowing polynomially many gates and ancillae. Our main results show that: (1) Depth-3 QAC$^0$ circuits cannot compute PARITY, and require $Ω(\exp(\sqrt{n}))$ gates to compute MAJORITY. (2) Depth-2 circuits cannot approximate h...
Wedi'i Gadw mewn:
| Prif Awduron: | , , , |
|---|---|
| Fformat: | Erthygl |
| Cyhoeddwyd: |
2025
|
| Pynciau: | |
| Mynediad Ar-lein: | https://arxiv.org/abs/2512.14643 http://arxiv.org/abs/2512.14643 |
| Tagiau: |
Dim Tagiau, Byddwch y cyntaf i dagio'r cofnod hwn!
|