aiqbench analysis
This research establishes new theoretical limits for constant-depth quantum circuits (QAC$^0$), demonstrating that they struggle to compute fundamental functions like PARITY and MAJORITY even with polynomial resources. By developing novel classical simulation techniques, the authors show that for boolean total functions, these shallow quantum architectures may not offer significant computational advantages over their classical AC$^0$ counterparts. These findings refine our understanding of the boundaries between classical and quantum complexity in restricted circuit models.
Improved Lower Bounds for QAC0
arXiv:2512.14643v4 Announce Type: replace Abstract: 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 $\Omega(\exp(\sqrt{n}))$ gates to compute MAJORITY. (2) Depth-2 circuits cannot approximate high-influence Boolean functions (e.g., PARITY) with non-negligible advantage, regardless of size. We develop new classical simulation techniques for QAC$^0$ to obtain our depth-3 bounds. In these results, we relax the output requirement of the quantum circuit to a single bit, making our depth $2$ approximation bound stronger than the previous best bound of Rosenthal (2021). This also enables us to draw natural comparisons with classical AC$^0$ circuits, which can compute PARITY exactly in depth $2$ (exp size). Our techniques further suggest that, for boolean total functions, constant-depth quantum circuits do not necessarily provide more power than their classical counterparts. Our third result shows that depth $2$ QAC$^0$ circuits, regardless of size, cannot exactly synthesize an $n$-target nekomata state (a state whose synthesis is directly related to the computation of PARITY). This complements the depth $2$ exponential size upper bound of Rosenthal (2021) for approximating nekomatas (which is used as a sub-circuit in the only known constant depth PARITY upper bound). Finally, we argue that approximating PARITY in QAC0, with significantly better than 1/poly(n) advantage on average, is just as hard as computing it exactly. Thus, extending our techniques to higher depths would also rule out approximate circuits for PARITY and related problems
Abstract: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 $\Omega(\exp(\sqrt{n}))$ gates to compute MAJORITY. (2) Depth-2 circuits cannot approximate high-influence Boolean functions (e.g., PARITY) with non-negligible advantage, regardless of size. We develop new classical simulation techniques for QAC$^0$ to obtain our depth-3 bounds. In these results, we relax the output requirement of the quantum circuit to a single bit, making our depth $2$ approximation bound stronger than the previous best bound of Rosenthal (2021). This also enables us to draw natural comparisons with classical AC$^0$ circuits, which can compute PARITY exactly in depth $2$ (exp size). Our techniques further suggest that, for boolean total functions, constant-depth quantum circuits do not necessarily provide more power than their classical counterparts. Our third result shows that depth $2$ QAC$^0$ circuits, regardless of size, cannot exactly synthesize an $n$-target nekomata state (a state whose synthesis is directly related to the computation of PARITY). This complements the depth $2$ exponential size upper bound of Rosenthal (2021) for approximating nekomatas (which is used as a sub-circuit in the only known constant depth PARITY upper bound). Finally, we argue that approximating PARITY in QAC0, with significantly better than 1/poly(n) advantage on average, is just as hard as computing it exactly. Thus, extending our techniques to higher depths would also rule out approximate circuits for PARITY and related problems
Quantum Physics (quant-ph); Computational Complexity (cs.CC)
arXiv:2512.14643 [quant-ph]
(or arXiv:2512.14643v4 [quant-ph] for this version)
https://doi.org/10.48550/arXiv.2512.14643 Focus to learn more arXiv-issued DOI via DataCite
https://doi.org/10.1145/3798129.3800922 Focus to learn more DOI(s) linking to related resources
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 349 words
Related coverage
Unconditional Quantum Advantage for Sampling with Shallow Circuits
Quantum Journal · Aug 12, 2026
Breaking the $T^{2/3}$ Barrier for Sequential Calibration
arXiv · Sep 17, 2026
Humanity’s Last Invention — Richard Socher of Recursive
Latent Space · Sep 14, 2026
Certifying Lower Bounds for Risk-Sensitive Reinforcement Learning under Adversarial State Perturbations
arXiv · Sep 11, 2026