Imagine you have a recipe that calls for a pinch of salt — not exactly a pinch, but somewhere between 0.9 and 1.1 pinches. You've been cooking this way for years because everyone assumed precision didn't matter. This paper shows you can hit exactly one pinch, every time, using a clever trick: make multiple copies of the dish in parallel and use the redundancy to calibrate perfectly. That's the core mechanism — exact amplitude amplification in the many-copies setting — and it has real consequences for what shallow quantum circuits can compute. The committed claim: QAC⁰ (constant-depth quantum circuits with unbounded fan-in Toffoli gates and arbitrary single-qubit gates) is robust in two precise senses. First, the bounded error typically allowed when QAC⁰ computes Boolean functions is unnecessary — exact computation suffices to capture the same power, including the ability to simulate TC⁰ (threshold circuits). Second, the seemingly extravagant gate set can be stripped down to just generalized Toffoli, S, and Hadamard gates without losing computational power. Both results say the same thing from different angles: QAC⁰'s strength is structural, not an artifact of loose definitions. The first result builds on Grier, Morris, and Wu's prior work establishing that QAC⁰ can compute functions outside AC⁰[p] for every fixed prime p — a landmark separation in circuit complexity. That earlier result relied on a 'parallel W-test' whose inherent error seemed baked in. The new contribution is a novel application of exact amplitude amplification that works in the many-copies context: given polynomially many copies of the classical input, you can boost the W-test to zero error. The consequence is EQAC⁰ (exact QAC⁰) exactly simulates TC⁰, and EQAC⁰ already computes total Boolean functions outside AC⁰[p]. This is a genuine tightening: the error was always a dangling thread, and now it's cut. The second result addresses a different anxiety. QAC⁰'s definition allows arbitrary single-qubit unitaries at every layer — an infinite gate set. Is the power really coming from the quantum parallelism of constant depth plus fan-in, or is it hiding in some exotic rotation angle? The answer is reassuring: any QAC⁰ circuit can be approximately simulated by one using only generalized Toffoli, S, and Hadamard. Moreover, the translation is efficient — given a classical description of the original circuit, you can construct the restricted version in polynomial time. The gate set is a red herring; the depth and fan-in do the heavy lifting. For the integrity check: this is pure mathematical theory. The results are proved, not simulated or benchmarked. The validation regime is mathematical proof — the strongest possible for claims of this type. There are no benchmarks to cherry-pick, no hyperparameters to tune. The question is whether the proofs are correct, and the techniques (exact amplitude amplification, Solovay-Kitaev-style gate approximation) are well-established tools applied in a new context. The paper's lineage is transparent — it directly extends Grier, Morris, and Wu's own prior work, and it sits squarely in the Razborov-era tradition of circuit complexity lower bounds. The milestone question for this subfield is concrete: can QAC⁰ be separated from TC⁰, or are they equal? This paper narrows the gap by showing exact QAC⁰ simulates TC⁰ with poly-many copies, but the converse — whether TC⁰ can simulate QAC⁰ — remains open. The next real unlock is either proving QAC⁰ = TC⁰ (which would say constant-depth quantum circuits with fan-in buy you exactly threshold gates and nothing more) or separating them (which would be a major new quantum advantage result). Either direction would be a landmark. The obvious experiment not run: extending beyond constant depth. What happens at depth O(log n)? The techniques here are specific to the constant-depth regime where the parallel copies trick works cleanly. Going deeper likely breaks the many-copies amplification strategy. The honest read is (a) — the tools don't generalize, not that the authors are holding back. The other missing piece is a constructive separation: the paper shows EQAC⁰ computes functions outside AC⁰[p], but doesn't exhibit an explicit function in QAC⁰ that provably cannot be computed in TC⁰. That's the harder direction, and it's likely an open problem for the field, not just for this team.
