Improved Lower Bounds for QAC0

Avishay Tal; Francisca Vasconcelos; John Wright; Malvika Raj Joshi

REVIEW

Improved Lower Bounds for QAC0

Malvika Raj Joshi, Avishay Tal, Francisca Vasconcelos, John Wright

Quantum Physics · Submitted 16 Dec 2025

Pith's verdict: First depth-3 PARITY lower bound for QAC^0 with unlimited ancillae, plus a tight depth-2 influence bound; the main proofs are solid, but Lemma 4.10 has a real ancilla-initialization gap that needs fixing.

T0 · AI review

How this review was made: An AI referee (deepseek-v4-flash) read the paper on August 3, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 2 major objections · 4 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv ID2512.14643 (version 4)

Pith IDNN43PNFZ, Pith's permanent record of this paper and its review

CitationAvishay Tal, Francisca Vasconcelos, John Wright, Malvika Raj Joshi. "Improved Lower Bounds for QAC0." arXiv:2512.14643 (2025). https://pith.science/paper/NN43PNFZ

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

Short version: this is a serious advance on Moore's QAC^0/FAN-OUT question. The depth-3 PARITY bound with unlimited ancillae and the depth-2 O(log n) total-influence bound are genuinely new, and the proof strategy is the most promising I've seen in this area. The clean-up lemma, the entropy-based Fourier-tail argument, and the generalized-nekomata lower bound are all real contributions. The paper deserves a serious referee.

The proofs are mostly self-contained, reduce to Håstad's AC^0 bounds and Rosenthal's QAC^0 normal form, and I don't see fitted parameters or circular reasoning. The depth-2 influence argument is especially nice: the entropy-versus-min-entropy split for separable mixed states is clever, and the tightness via Tribes is a good touch.

The main soft spot is Lemma 4.10. The proof as written assumes every ancilla starts in |0>, using conditions like <θ^1_a|0> ≠ 0 and |<θ^1_a|1>| ≠ 1 to get both branches of the mixed-state argument with nonzero probability. But the Clean-Up Lemma (Lemma 4.1) explicitly creates circuits with ancillae starting in |μ>|1> (via the CNOT replacement) and classical |1> states (from fixed coordinates). The proof of Lemma 4.10 never generalizes to those states. Since this lemma is the only mechanism limiting the number of 'bad' layer-2 gates in Theorem 4.9, the size-independent depth-3 PARITY bound has a gap as written. The stress-test note got this right. I think it's patchable—the conditions should be restated in terms of the actual separable starting states, and for the specific CNOT gates the needed inner products are nonzero—but the authors need to write that out.

Minor concern: the approximate-to-exact reduction in Appendix A relies on unpublished work [GMW26] and has some hand-wavy constant/cloning steps. It's not load-bearing for the main lower bounds, so I'd treat it as a bonus, not a reason to reject.

Also worth flagging: the acknowledgments credit ChatGPT for a proof idea (Lemma 5.5). That's fine with me, but it may look odd to some referees.

Bottom line: accept for peer review, but ask for a revised Lemma 4.10 that handles non-|0> ancilla states explicitly. If that fix lands, this will be a significant paper. I'd bring it to a reading group and likely cite it.

Referee report

Major objections (2)

[§4.1 vs. §4.2–4.4] The Clean-Up Lemma 4.1 outputs a circuit whose ancillae are separable but not necessarily initialized to |0⟩: the CNOT replacement uses |μ⟩_1|1⟩_2, and the balanced restrictions place classical bits. However, Lemma 4.4, Corollary 4.5, Lemma 4.6, and Theorem 4.7 are all proved under the hypothesis 'ancillae start in |0⟩_A'. Thus the cleaned-up circuit to which Theorem 4.7 is applied in Corollary 4.8 does not satisfy the stated hypotheses. A PARITY-specific variant of the clean-up may repair this, but as written the depth-3 classical simulation has a gap.
[§4.5.1, Lemma 4.10] The proof of Lemma 4.10 is not valid even for |0⟩-initialized ancillae. The rank-2 argument requires both measurement outcomes to occur with nonzero probability after fixing x_i=z_i. If θ_i^1=|0⟩ and every ancilla outside S has θ_a^1=|0⟩, then fixing x_i=0 leaves only the 'all-θ' outcome: the mixed state has rank 1. The inference 'f non-trivial ⇒ at least one of the two vectors is not killed' then fails: choosing θ_S^2 orthogonal to that pure state makes f_{C,G}=x_i non-trivial while (i,0) kills it. Since layer-2 gates can be placed on several disjoint ancillae of the same layer-1 gate, more than two non-trivial gates can be killed, contradicting the lemma. Theorem 4.9 relies on Lemma 4.10 for the O(1) bound on bad layer-2 gates, so Theorem 1.2 is not established as written.

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

The paper proves that depth-3 QAC^0 circuits cannot compute PARITY even with unlimited ancillae and gates, that depth-2 QAC^0 circuits have total influence only O(log n), and that depth-2 circuits cannot exactly synthesize generalized nekom

The reading

This paper establishes the strongest known fixed-depth lower bounds for QAC^0, the constant-depth quantum circuit class with unbounded fan-in gates and polynomial ancillae. Its main claim is that PARITY, the function that classical depth-2 circuits can compute with exponential size, cannot be computed exactly by any depth-3 QAC^0 circuit regardless of size. It also shows that depth-2 QAC^0 circuits have total influence only O(log n), making their correlation with PARITY exponentially small, and that no depth-2 circuit can exactly prepare a generalized nekomata state on more than four targets. The proof method is a classical AC^0 simulation of cleaned-up shallow quantum circuits via quantum restrictions and activation functions.

What carries the argument

The load-bearing object is the reflection-gate normal form G(S) = I - 2|theta><theta|_S for Toffoli-type gates, together with activation functions f_{C,Pi}(x) = [Pi C(x) != 0] that track whether a projector sees the state. The clean-up lemma converts any depth-d PARITY or MAJORITY circuit into one whose first layer depends on at most one input per gate, using superpositions of classical restrictions that keep the function invariant. Block diagonalization of the final gate then lets the output be expressed as a DNF/CNF over activation functions, giving an AC^0 simulation. For depth 2, the proof analyzes the mixed state entering the final gate via a matrix Fourier decomposition rho_x = sum_R (

Extended reading notes

Core claim

The central discovery is that shallow QAC^0 circuits, despite unbounded fan-in gates and unlimited ancillae, are classically tame: after a cleanup step that restricts inputs to a subspace while preserving PARITY or MAJORITY, every layer-1 gate touches at most one input, and the final output can be simulated by a depth-3 classical AC^0 circuit of polynomial size. In depth 2, a second structural result bounds the total influence of the acceptance probability by O(log n) regardless of ancillae, via a matrix Fourier decomposition and entropy arguments. This yields correlation at most exp(-Omega(sqrt(n))) with PARITY, and a separate argument shows that no depth-2 circuit can exactly synthesize a

Load-bearing premise

The size-independent depth-3 PARITY bound rests on Lemma 4.10, which asserts that in a cleaned-up depth-2 circuit one global assignment of all input bits can be chosen so that fixing any one coordinate kills at most two non-trivial second-layer gates; if that lemma fails, the proof reduces to the weaker sub-exponential bound.

Editorial extensions

If this is right

If the main theorem is correct, depth-3 QAC^0 circuits cannot compute PARITY exactly on more than a constant number of inputs, even with unlimited ancillae, so the open question of whether quantum fan-out belongs to QAC^0 remains closed at this depth.
Depth-2 QAC^0 circuits cannot approximate PARITY or any high-influence Boolean function with non-negligible advantage; their acceptance functions are Fourier-concentrated with total influence O(log n).
MAJORITY requires at least exp(Omega(sqrt(n))) gates in depth-3 QAC^0, so polynomial-size depth-3 QAC^0 circuits cannot compute MAJORITY.
Depth-2 QAC^0 circuits cannot exactly prepare generalized nekomata states on n > 4 targets, ruling out the exact analog of the known approximate construction at the same depth.
Approximating PARITY with 1/polylog(n) advantage in QAC^0 is as hard as computing it exactly, so extending the depth-3 exact lower bound to higher depths would also rule out approximate PARITY circuits.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The AC^0 simulation of shallow quantum circuits suggests a QAC^0 analogue of the switching lemma: if the monotonicity obstruction at depth 3 can be bypassed, similar size-independent lower bounds may hold for depths beyond 3.
The O(log n) total influence bound is tight up to constants, as the Tribes function is depth-2 QAC^0 with influence Theta(log n); a natural testable extension is whether the Fourier tail bound can be sharpened to match classical AC^0-style exp(-Omega(k^{1/(d-1)})) tails at higher depths.
Because approximate PARITY with inverse-polylogarithmic advantage reduces exactly to PARITY, a single explicit depth-4 construction computing PARITY would refute the paper's conjecture; checking recursive small-depth constructions may be the fastest route to a counterexample.

Original 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

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 8,413 input tokens.

What the abstract itself states, as probabilities: claims first 0.07 · states limitation 0.52 · human participants 0.01 · controlled comparison 0.21 · randomized assignment 0.01 · states quantitative result 0.98 · compares with prior results 0.98 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v4. Results and the main claim are underlined; show every role.

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

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	In this work, we prove the strongest known lower bounds for QAC$^0$, allowing polynomially many gates and ancillae.	contribution 0.90	0.96	0.64	asserted 1.00
s1	Our main results show that: (1) Depth-3 QAC$^0$ circuits cannot compute PARITY, and require $\Omega(\exp(\sqrt{n}))$ gates to compute MAJORITY.	result 0.99	0.95	0.72	asserted 1.00
s2	(2) Depth-2 circuits cannot approximate high-influence Boolean functions (e.g., PARITY) with non-negligible advantage, regardless of size.	result 1.00	0.90	0.30	asserted 1.00
s3	We develop new classical simulation techniques for QAC$^0$ to obtain our depth-3 bounds.	method 0.92	0.95	0.03	asserted 1.00
s4	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).	contribution 0.67	0.89	0.10	asserted 1.00
s5	This also enables us to draw natural comparisons with classical AC$^0$ circuits, which can compute PARITY exactly in depth $2$ (exp size).	interpretation 0.81	0.26	0.04	asserted 0.96
s6	Our techniques further suggest that, for boolean total functions, constant-depth quantum circuits do not necessarily provide more power than their classical counterparts.	interpretation 0.99	0.67	0.17	hedged possibility 1.00
s7	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).	result 1.00	0.93	0.12	asserted 1.00
s8	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).	background 0.59	0.10	0.05	asserted 1.00
s9	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.	result 0.72	0.81	0.12	asserted 0.90
s10	Thus, extending our techniques to higher depths would also rule out approximate circuits for PARITY and related problems	future work 0.51	0.50	0.10	hedged possibility 0.69

What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v4

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

Figures

**Figure 1.** QAC0 circuit computing f(x). The circuit takes in a n-qubit classical input corresponding to the string x ∈ {0, 1} n. Each ancilla starts in a fixed state |0⟩. At the end of the circuit, the state on a designated output register contains the answer |f(x)⟩. Each qubit can belong to at most one gate per layer and there are no locality based constraints on multi-qubit gates, thus, the illustrated circuit has depth 4. where | ⃗θ⟩S is a separable state across all of S. Note that this gate is simply a reflection about the state | ⃗θ⟩S and is a unitary with eigenvalues ±1. We use the vect

**Figure 2.** Clean-up of a gate G with more than 3 input qubits. The restriction fixes the state of |xi⟩ |xj ⟩ to |φ⟩ i,j in a way that deactivates the gate G. Then, the restriction to |φ⟩ i,j is equivalent to applying a CNOT gate on the separable initial ancillae state |µ⟩ |1⟩. 4.2 AC0 Simulation of Projectors After Layer One After the clean-up in Lemma 4.1, the state after the first layer of the circuit is separable across all input qubits, and has the following form, C(x) = |ψ0⟩B0 ⊗  O i∈[n] |ψi(xi)⟩Bi   (21) where |ψi(xi)⟩Bi is a state on qubits Bi in layer-1 gate containing inpu

Figures reproduced from arXiv:2512.14643 by the authors.

References

How the literature uses it

4 arXiv papers cite this in 9 sentences

Each citing sentence is taken from the citing paper's LaTeX source and typed by Pith's classifier. A label appears at probability 0.8 or more (0.95 for support), a contest at 0.7 or more; the quoted words are the citing authors'. How each label was checked · JSON

Papers citing it · 5 sentences without a confident label

Uses its method or tool 1 paper

These lower bounds are based on an input-restriction approach, inspired by 's well-known random restriction method [ref] , and the recent work by Joshi, Tal, Vasconcelos, and Wright [ref] .

On the Computational Power of Geometrically Local QAC circuits · Introduction · 0.95

Cites it as background 3 papers

Even just the past few years have seen impressive developments in understanding the limitations of these models through the lens of pseudorandom generators [ref] (see also the survey [ref] ), extractors [ref] , and quantum analogs [ref] .[This is only a minute fraction of contemporary work, and we encourage the interested reader to consult references within those cited.]

Hard-to-Sample Distributions from Robust Extractors · Introduction · 0.89
Since its introduction, $$ has been studied extensively [ref] .

On the Computational Power of Geometrically Local QAC circuits · Introduction · 0.99
Since the gate can straightforwardly be used to compute the GHZ/CAT state, most of the literature on versus has focused on synthesis of GHZ states and its variants [ref] .

Constant-Depth Unitary Preparation of Dicke States · Introduction · 0.92

What it cites · 5 sentences without a confident label

Compares with 1 paper

We note that [ref] already provide a tighter bound, in terms of $n$, for in depth-$2$.

Tight bounds on depth-2 QAC-circuits computing parity · Quantum Analog of Restrictions · 0.95

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.