The Robustness of QAC0
Abstract
In this work we study the robustness of QAC0 with respect to error tolerance and modifications to its gate-set. First, we investigate whether the non-zero error typically allowed for QAC0 circuits computing Boolean functions is truly necessary. We show that the error inherent in the parallel W-test of \cite{grier_morris_wu} can be eliminated entirely via a novel application of exact amplitude amplification in the many-copies context. Consequently, we find that QAC0 can \textit{exactly} simulate TC0 with polynomially many copies of the classical input and that for every fixed prime p exact QAC0, EQAC0, can compute total Boolean functions outside of AC0[p]. Second, we ask to what extent the computational power of QAC0 follows from the fact that arbitrary single-qubit gates may be used at any point in the circuit. We find that QAC0 is in fact robust to restrictions on which single-qubit gates are permitted: every QAC0 circuit can be approximately implemented by a QAC0 circuit consisting of just generalized Toffoli, S, and Hadamard gates. Moreover, this approximating circuit can be constructed efficiently from a classical description of the original circuit.
Related
- QAC0 Can Prepare Every Logarithmic-Qubit State
- Quasi-Bessel Stokes skyrmions with enhanced topological robustness in free-space and turbulent propagation
- Radial encoding determines deformation robustness in far-field multimode fiber imaging
- Model-fitting perspective on the robustness and speed of CLASS in reflection matrix microscopy
- Theoretical study on ambient-pressure superconductivity in La 3 Ni 2 O 7 thin films: Structural analysis, model construction, and robustness of s ± -wave pairing
BibTeX
@misc{grier2026robustness,
title = {{The Robustness of QAC0}},
author = {Daniel Grier and Jackson Morris and Kewen Wu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02154},
eprint = {2610.02154},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02154},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The Robustness of QAC0
AU - Daniel Grier
AU - Jackson Morris
AU - Kewen Wu
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.02154
UR - https://arxiv.org/abs/2610.02154
AB - In this work we study the robustness of QAC^0 with respect to error tolerance and modifications to its gate-set. First, we investigate whether the non-zero error typically allowed for QAC^0 circuits computing Boolean functions is truly necessary. We show that the error inherent in the parallel W-test of \cite{grier_morris_wu} can be eliminated entirely via a novel application of exact amplitude amplification in the many-copies context. Consequently, we find that QAC^0 can \textit{exactly} simulate TC^0 with polynomially many copies of the classical input and that for every fixed prime p exact QAC^0, EQAC^0, can compute total Boolean functions outside of AC^0[p]. Second, we ask to what extent the computational power of QAC^0 follows from the fact that arbitrary single-qubit gates may be used at any point in the circuit. We find that QAC^0 is in fact robust to restrictions on which single-qubit gates are permitted: every QAC^0 circuit can be approximately implemented by a QAC^0 circuit consisting of just generalized Toffoli, S, and Hadamard gates. Moreover, this approximating circuit can be constructed efficiently from a classical description of the original circuit.
ER -