Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 59 min ago
PreprintCC BY 4.0arXiv

Fanout Complexity of Symmetric Boolean Functions in QAC0

  • Boyan Xu
  • Lvzhou Li
Open at sourcePDFDOICite

Abstract

Whether QAC0 can compute PARITYn remains open. Computing PARITYn is equivalent to implementing FANOUTn under QAC0 reductions. This raises a more general question: for an arbitrary symmetric Boolean function f:{0,1}n→{0,1}, what fanout size is necessary and sufficient for computing f in QAC0? We show that the answer is exactly the transition radius ρ(f): computing f and implementing FANOUTρ(f) are equivalent under QAC0 reductions. In particular, if ρ(f)≥ nδ for some constant δ>0, then computing f is QAC0f-complete. Combined with Paturi's theorem, our characterization implies that if PARITYn ∉ QAC0, then any Boolean function in QAC0 of approximate degree n1/2+Ω(1) must be nonsymmetric.

Related

  1. Exact Quantum Query Complexity of the Five-Bit Symmetric Boolean Function Exact53,4
    Guoliang Xu, Haoran Zhang, Mengfan Wu +2
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
  2. Nearly Optimal Quantum Sample Complexity of Learning Fourier-Sparse Boolean Functions
    Zekun Ye
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
  3. Efficient Depth--Ancilla Tradeoffs for Hamming Weight Computation and Symmetric Boolean Functions
    Wei Zi, Pei Yuan, Junhong Nie +1
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
  4. On the quantum communication complexity of total functions
    Dmytro Gavinsky
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
  5. Constant-round quantum advantage in communication complexity for total functions
    Atsuya Hasegawa, François Le Gall
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv

Cite

BibTeXRIS
BibTeX
@misc{xu2026fanout,
  title = {{Fanout Complexity of Symmetric Boolean Functions in $\mathsfQAC^0$}},
  author = {Boyan Xu and Lvzhou Li},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.05153},
  eprint = {2609.05153},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.05153},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Fanout Complexity of Symmetric Boolean Functions in QAC^0
AU  - Boyan Xu
AU  - Lvzhou Li
PY  - 2026
DA  - 2026/09/04
PB  - arXiv
DO  - 10.48550/arxiv.2609.05153
UR  - https://arxiv.org/abs/2609.05153
AB  - Whether QAC^0 can compute PARITY_n remains open. Computing PARITY_n is equivalent to implementing FANOUT_n under QAC^0 reductions. This raises a more general question: for an arbitrary symmetric Boolean function f:{0,1}^n→{0,1}, what fanout size is necessary and sufficient for computing f in QAC^0? We show that the answer is exactly the transition radius ρ(f): computing f and implementing FANOUT_ρ(f) are equivalent under QAC^0 reductions. In particular, if ρ(f)≥ n^δ for some constant δ>0, then computing f is QAC^0_f-complete. Combined with Paturi's theorem, our characterization implies that if PARITY_n ∉ QAC^0, then any Boolean function in QAC^0 of approximate degree n^1/2+Ω(1) must be nonsymmetric.
ER  -