{"id":"arxiv/2609.05153","url":"https://arxiv.org/abs/2609.05153","tags":["quant-ph"],"score":0,"title":"Fanout Complexity of Symmetric Boolean Functions in $\\mathsf{QAC}^0$","domain":"quant-ph","source":"arxiv","authors":["Boyan Xu","Lvzhou Li"],"reviews":0,"subject":"quant-ph","summary":"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 $ρ(f)$: computing $f$ and implementing $\\mathtt{FANOUT}_{ρ(f)}$ are equivalent under $\\mathsf{QAC}^0$ reductions. In particular, if $ρ(f)\\ge n^δ$ for some constant…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-04","reactions":{}}