Metraipolis › archive › dc_293bd10b85fb
Fanout Complexity of Symmetric Boolean Functions in $\mathsf{QAC}^0$ — arXiv:2609.05153
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.05153
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-17T00:01:44.539Z
- SHA-256 of the archived text
26a79cb76b1ae3f1d41432780051e55b91544a83f791781d61af758b1b79f064- Stable URL of this page
https://metraipolis.com/documento/dc_293bd10b85fb
How to cite
Fanout Complexity of Symmetric Boolean Functions in $\mathsf{QAC}^0$ — arXiv:2609.05153 — arXiv (en), https://arxiv.org/abs/2609.05153 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_293bd10b85fb (Metraipolis archive dc_293bd10b85fb, sha256 26a79cb76b1ae3f1d41432780051e55b91544a83f791781d61af758b1b79f064)
BibTeX
@misc{dc293bd10b85fb,
title = {Fanout Complexity of Symmetric Boolean Functions in $mathsfQAC^0$ — arXiv:2609.05153},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.05153},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_293bd10b85fb; sha256 26a79cb76b1ae3f1d41432780051e55b91544a83f791781d61af758b1b79f064},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.05153. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Whether $\mathsf{QAC}^0$ can compute $\mathtt{PARITY}_n$ remains open. Computing $\mathtt{PARITY}_n$ is equivalent to implementing $\mathtt{FANOUT}_n$ under $\mathsf{QAC}^0$ reductions. This raises a more general question: for an arbitrary symmetric Boolean function $f:\{0,1\}^n\to\{0,1\}$, what fanout size is necessary and sufficient for computing $f$ in $\mathsf{QAC}^0$? We show that the answer is exactly the transition radius $\rho(f)$: computing $f$ and implementing $\mathtt{FANOUT}_{\rho(f)}$ are equivalent under $\mathsf{QAC}^0$ reductions. In particular, if $\rho(f)\ge n^\delta$ for some constant $\delta>0$, then computing $f$ is $\mathsf{QAC}^0_{\mathrm{f}}$-complete. Combined with Paturi's theorem, our characterization implies that if $\mathtt{PARITY}_n \notin \mathsf{QAC}^0$, then any Boolean function in $\mathsf{QAC}^0$ of approximate degree $n^{1/2+\Omega(1)}$ must be nonsymmetric.
Tema degli esploratori: fisica e astronomia (retro-catalogo arXiv: annunci del 2026-09-07 in quant-ph).
Categorie arXiv: Quantum Physics (quant-ph).
Pagina del lavoro: https://arxiv.org/abs/2609.05153 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T23:41:14.313Z dalla pagina https://arxiv.org/catchup/quant-ph/2026-09-07?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).