{"id":"arxiv/2601.03243","url":"https://arxiv.org/abs/2601.03243","tags":["cs.CC","quant-ph"],"score":0,"title":"$\\mathsf{QAC}^0$ Contains $\\mathsf{TC}^0$ (with Many Copies of the Input)","domain":"cs.CC","source":"arxiv","authors":["Daniel Grier","Jackson Morris","Kewen Wu"],"reviews":0,"subject":"cs.CC","summary":"$\\mathsf{QAC}^0$ is the class of constant-depth polynomial-size quantum circuits constructed from arbitrary single-qubit gates and generalized Toffoli gates. It is arguably the smallest natural class of constant-depth quantum computation which has not been shown useful for computing any non-trivial Boolean function. Despite this, many attempts to port classical $\\mathsf{AC}^0$ lower bounds to $\\mathsf{QAC}^0$ have failed. We give one possible explanation of this: $\\mathsf{QAC}^0$ circuits are significantly more powerful than their classical counterparts. We show the unconditional separation…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-01-06","reactions":{}}