QAC0 Can Prepare Every Logarithmic-Qubit State
Abstract
QAC0 is the class of constant-depth poly(n)-ancilla circuits obtained by extending QNC0, the class of local circuits, to include nonlocal interactions via arbitrary width Toffoli gates. It is believed to be weaker than its counterpart, QNC0f, obtained by including arbitrary-width FANOUT gates instead (QAC0 ⊆ QNC0f [Moo99]). In this note, we show that every O(log n)-qubit state can be exactly and cleanly prepared by a poly(n)-ancilla QAC0 circuit. Previous known poly(n)-ancilla circuits for arbitrary such states are only known via additional access to either FANOUT or QRAM (indexing) gates [Ros21b, GGJ26b], neither of which are known to be in QAC0. Equivalently, prior constructions of arbitrary n-qubit states in QAC0 require doubly exponential size and we obtain an exponential factor improvement.
Related
- Every architecture of six two-qubit gates is locally universal on three qubits
- Regret Lower Bound for Online Learning of Quantum States with Logarithmic Loss, with Applications to Quantum State Tomography and Confidence Sequences for Matrix Means
- Resource Theory of Aquaternionicity: Every Pure State Is a Replicable Resource for Exact Simulation of Arbitrary Quantum Operations
- From hyperplanes to hyperellipsoids: a pedagogical bridge from linear classifiers to single-qubit mixed-state classifiers
- The Robustness of QAC0
BibTeX
@misc{gretta2026qac0,
title = {{QAC0 Can Prepare Every Logarithmic-Qubit State}},
author = {Lucas Gretta and Meghal Gupta and Malvika Raj Joshi},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.17408},
eprint = {2609.17408},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.17408},
}
RIS
TY - UNPB
TI - QAC0 Can Prepare Every Logarithmic-Qubit State
AU - Lucas Gretta
AU - Meghal Gupta
AU - Malvika Raj Joshi
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2609.17408
UR - https://arxiv.org/abs/2609.17408
AB - QAC^0 is the class of constant-depth poly(n)-ancilla circuits obtained by extending QNC^0, the class of local circuits, to include nonlocal interactions via arbitrary width Toffoli gates. It is believed to be weaker than its counterpart, QNC^0_f, obtained by including arbitrary-width FANOUT gates instead (QAC^0 ⊆ QNC^0_f [Moo99]). In this note, we show that every O(log n)-qubit state can be exactly and cleanly prepared by a poly(n)-ancilla QAC^0 circuit. Previous known poly(n)-ancilla circuits for arbitrary such states are only known via additional access to either FANOUT or QRAM (indexing) gates [Ros21b, GGJ26b], neither of which are known to be in QAC^0. Equivalently, prior constructions of arbitrary n-qubit states in QAC^0 require doubly exponential size and we obtain an exponential factor improvement.
ER -