Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2512.14643 · ACM Symposium on Theory of Computing (STOC)

Improved Lower Bounds for QAC0

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

quant-phcs.CCSubmitted Dec 16, 2025• Announced Dec 17, 2025• 0 citations• Revised Jan 20, 2026 (v2)
v1 · Dec 16, 2025v2 · Jan 20, 2026v3 · Jun 29, 2026v4 · Aug 25, 2026
arXivHTMLPDF

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 $Ω(\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

Journal reference
STOC 2026: Proceedings of the 58th Annual ACM Symposium on Theory of Computing, 2199-2209
DOI
10.1145/3798129.3800922

Related papers

On the Computational Power of QAC0 with Barely Superlinear Ancillae

Anurag Anshu, Yangjing Dong, Fengning Ou +1 more

$\mathrm{QAC}^0$ is the family of constant-depth polynomial-size quantum circuits consisting of arbitrary single qubit unitaries and multi-qubit Toffoli gates. It was introduced by Moore [arXiv: 9903046] as a quantum counterpart of $\mathrm{AC}^0$, along with the conjecture that $\mathrm{QAC}^0$ circuits can not compute PARITY. In this work we make progress on this longstanding conjecture: we show that any depth-$d$ $\mathrm{QAC}^0$ circuit requires $n^{1+3^{-d}}$ ancillae to compute a function with approximate degree $Θ(n)$, which includes PARITY, MAJORITY and $\mathrm{MOD}_k$. We further establish superlinear lower bounds on quantum state synthesis and quantum channel synthesis. This is the first superlinear lower bound on the super-linear sized $\mathrm{QAC}^0$. Regarding PARITY, we show that any further improvement on the size of ancillae to $n^{1+\exp(-o(d))}$ would imply that PARITY $\not\in$ QAC0. These lower bounds are derived by giving low-degree approximations to $\mathrm{QAC}^0$ circuits. We show that a depth-$d$ $\mathrm{QAC}^0$ circuit with $a$ ancillae, when applied to low-degree operators, has a degree $(n+a)^{1-3^{-d}}$ polynomial approximation in the spectral norm. This implies that the class $\mathrm{QLC}^0$, corresponding to linear size $\mathrm{QAC}^0$ circuits, has approximate degree $o(n)$. This is a quantum generalization of the result that $\mathrm{LC}^0$ circuits have approximate degree $o(n)$ by Bun, Robin, and Thaler [SODA 2019]. Our result also implies that $\mathrm{QLC}^0\neq\mathrm{NC}^1$.

arXiv:2410.06499•ACM Symposium on Theory of Computing (STOC)•Jun 15, 2025•1 citation

Bounds on the QAC$^0$ Complexity of Approximating Parity

Gregory Rosenthal

QAC circuits are quantum circuits with one-qubit gates and Toffoli gates of arbitrary arity. QAC$^0$ circuits are QAC circuits of constant depth, and are quantum analogues of AC$^0$ circuits. We prove the following: $\bullet$ For all $d \ge 7$ and $\varepsilon>0$ there is a depth-$d$ QAC circuit of size $\exp(\mathrm{poly}(n^{1/d}) \log(n/\varepsilon))$ that approximates the $n$-qubit parity function to within error $\varepsilon$ on worst-case quantum inputs. Previously it was unknown whether QAC circuits of sublogarithmic depth could approximate parity regardless of size. $\bullet$ We introduce a class of "mostly classical" QAC circuits, including a major component of our circuit from the above upper bound, and prove a tight lower bound on the size of low-depth, mostly classical QAC circuits that approximate this component. $\bullet$ Arbitrary depth-$d$ QAC circuits require at least $Ω(n/d)$ multi-qubit gates to achieve a $1/2 + \exp(-o(n/d))$ approximation of parity. When $d = Θ(\log n)$ this nearly matches an easy $O(n)$ size upper bound for computing parity exactly. $\bullet$ QAC circuits with at most two layers of multi-qubit gates cannot achieve a $1/2 + \exp(-o(n))$ approximation of parity, even non-cleanly. Previously it was known only that such circuits could not cleanly compute parity exactly for sufficiently large $n$. The proofs use a new normal form for quantum circuits which may be of independent interest, and are based on reductions to the problem of constructing certain generalizations of the cat state which we name "nekomata" after an analogous cat yōkai.

arXiv:2008.07470•Leibniz international proceedings in informatics•Aug 17, 2020•3 citations

$\mathsf{QAC}^0$ Contains $\mathsf{TC}^0$ (with Many Copies of the Input)

Daniel Grier, Jackson Morris, Kewen Wu

$\mathsf{QAC}^0$ is the class of constant-depth polynomial-size quantum circuits constructed from arbitrary single-qubit gates and generalized Toffoli gates. It is arguably the smallest natural class of constant-depth quantum computation which has not been shown useful for computing any non-trivial Boolean function. Despite this, many attempts to port classical $\mathsf{AC}^0$ lower bounds to $\mathsf{QAC}^0$ have failed. We give one possible explanation of this: $\mathsf{QAC}^0$ circuits are significantly more powerful than their classical counterparts. We show the unconditional separation $\mathsf{QAC}^0\not\subset\mathsf{AC}^0[p]$ for decision problems, which also resolves for the first time whether $\mathsf{AC}^0$ could be more powerful than $\mathsf{QAC}^0$. Moreover, we prove that $\mathsf{QAC}^0$ circuits can compute a wide range of Boolean functions if given multiple copies of the input: $\mathsf{TC}^0 \subseteq \mathsf{QAC}^0 \circ \mathsf{NC}^0$. Along the way, we introduce an amplitude amplification technique that makes several approximate constant-depth constructions exact.

cs.CCCross-listedarXiv:2601.03243•Jan 7, 2026•0 citations

Bounds on the $\mathrm{QAC}^0$ Complexity of Approximating Parity

Gregory Rosenthal

$\mathrm{QAC}$ circuits are quantum circuits with one-qubit gates and Toffoli gates of arbitrary arity. $\mathrm{QAC}^0$ circuits are $\mathrm{QAC}$ circuits of constant depth, and are quantum analogues of $\mathrm{AC}^0$ circuits. We prove the following: $\bullet$ For all $d \ge 7$ and $\varepsilon>0$ there is a depth-$d$ $\mathrm{QAC}$ circuit of size $\exp(\mathrm{poly}(n^{1/d}) \log(n/\varepsilon))$ that approximates the $n$-qubit parity function to within error $\varepsilon$ on worst-case quantum inputs. Previously it was unknown whether $\mathrm{QAC}$ circuits of sublogarithmic depth could approximate parity regardless of size. $\bullet$ We introduce a class of $\mathrm{QAC}$ circuits, including a major component of our circuit from the above upper bound, and prove a tight lower bound on the size of low-depth, mostly classical $\mathrm{QAC}$ circuits that approximate this component. $\bullet$ Arbitrary depth-$d$ $\mathrm{QAC}$ circuits require at least $\Omega(n/d)$ multi-qubit gates to achieve a $1/2 + \exp(-o(n/d))$ approximation of parity. When $d = \Theta(\log n)$ this nearly matches an easy $O(n)$ size upper bound for computing parity exactly. $\bullet$ $\mathrm{QAC}$ circuits with at most two layers of multi-qubit gates cannot achieve a $1/2 + \exp(-o(n))$ approximation of parity, even non-cleanly. Previously it was known only that such circuits could not cleanly compute parity exactly for sufficiently large $n$. The proofs use a new normal form for quantum circuits which may be of independent interest, and are based on reductions to the problem of constructing certain generalizations of the cat state which we name nekomata after an analogous cat y\=okai.

•Aug 17, 2020•0 citations

The Robustness of QAC0

Daniel Grier, Jackson Morris, Kewen Wu

In this work we study the robustness of $\mathsf{QAC}^0$ with respect to error tolerance and modifications to its gate-set. First, we investigate whether the non-zero error typically allowed for $\mathsf{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 $\mathsf{QAC}^0$ can \textit{exactly} simulate $\mathsf{TC}^0$ with polynomially many copies of the classical input and that for every fixed prime $p$ exact $\mathsf{QAC}^0$, $\mathsf{EQAC}^0$, can compute total Boolean functions outside of $\mathsf{AC}^0[p]$. Second, we ask to what extent the computational power of $\mathsf{QAC}^0$ follows from the fact that arbitrary single-qubit gates may be used at any point in the circuit. We find that $\mathsf{QAC}^0$ is in fact robust to restrictions on which single-qubit gates are permitted: every $\mathsf{QAC}^0$ circuit can be approximately implemented by a $\mathsf{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.

quant-pharXiv:2610.02154•Oct 2, 2026•0 citations

Low-degree approximation of QAC$^0$ circuits

Ashley Montanaro, Changpeng Shao, Dominic Verdon

QAC$^0$ is the class of constant-depth quantum circuits with polynomially many ancillary qubits, where Toffoli gates on arbitrarily many qubits are allowed. In this work, we show that the parity function cannot be computed in QAC$^0$, resolving a long-standing open problem in quantum circuit complexity more than twenty years old. As a result, this proves ${\rm QAC}^0 \subsetneqq {\rm QAC}_{\rm wf}^0$. We also show that any QAC circuit of depth $d$ that approximately computes parity on $n$ bits requires $2^{\widetildeΩ(n^{1/d})}$ ancillary qubits, which is close to tight. This implies a similar lower bound on approximately preparing cat states using QAC circuits. Finally, we prove a quantum analog of the Linial-Mansour-Nisan theorem for QAC$^0$. This implies that, for any QAC$^0$ circuit $U$ with $a={\rm poly}(n)$ ancillary qubits, and for any $x\in\{0,1\}^n$, the correlation between $Q(x)$ and the parity function is bounded by ${1}/{2} + 2^{-\widetildeΩ(n^{1/d})}$, where $Q(x)$ denotes the output of measuring the output qubit of $U|x,0^a\rangle$. All the above consequences rely on the following technical result. If $U$ is a QAC$^0$ circuit with $a={\rm poly}(n)$ ancillary qubits, then there is a distribution $\mathcal{D}$ of bounded polynomials of degree polylog$(n)$ such that with high probability, a random polynomial from $\mathcal{D}$ approximates the function $\langle x,0^a| U^†Z_{n+1} U |x,0^a\rangle$ for a large fraction of $x\in \{0,1\}^n$. This result is analogous to the Razborov-Smolensky result on the approximation of AC$^0$ circuits by random low-degree polynomials.

arXiv:2411.00976•Nov 1, 2024•0 citations
In this work, we prove the strongest known lower bounds for QAC0^00, allowing polynomially many gates and ancillae. Our main results show that:
(1) Depth-3 QAC0^00 circuits cannot compute PARITY, and require Ω(exp⁡(n))Ω(\exp(\sqrt{n}))Ω(exp(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 QAC0^00 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 222 approximation bound stronger than the previous best bound of Rosenthal (2021). This also enables us to draw natural comparisons with classical AC0^00 circuits, which can compute PARITY exactly in depth 222 (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 222 QAC0^00 circuits, regardless of size, cannot exactly synthesize an nnn-target nekomata state (a state whose synthesis is directly related to the computation of PARITY). This complements the depth 222 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
QAC0\mathrm{QAC}^0QAC0 is the family of constant-depth polynomial-size quantum circuits consisting of arbitrary single qubit unitaries and multi-qubit Toffoli gates. It was introduced by Moore [arXiv: 9903046] as a quantum counterpart of AC0\mathrm{AC}^0AC0, along with the conjecture that QAC0\mathrm{QAC}^0QAC0 circuits can not compute PARITY. In this work we make progress on this longstanding conjecture: we show that any depth-ddd QAC0\mathrm{QAC}^0QAC0 circuit requires n1+3−dn^{1+3^{-d}}n1+3−d ancillae to compute a function with approximate degree Θ(n)Θ(n)Θ(n), which includes PARITY, MAJORITY and MODk\mathrm{MOD}_kMODk​. We further establish superlinear lower bounds on quantum state synthesis and quantum channel synthesis. This is the first superlinear lower bound on the super-linear sized QAC0\mathrm{QAC}^0QAC0. Regarding PARITY, we show that any further improvement on the size of ancillae to n1+exp⁡(−o(d))n^{1+\exp(-o(d))}n1+exp(−o(d)) would imply that PARITY ∉\not\in∈ QAC0. These lower bounds are derived by giving low-degree approximations to QAC0\mathrm{QAC}^0QAC0 circuits. We show that a depth-ddd QAC0\mathrm{QAC}^0QAC0 circuit with aaa ancillae, when applied to low-degree operators, has a degree (n+a)1−3−d(n+a)^{1-3^{-d}}(n+a)1−3−d polynomial approximation in the spectral norm. This implies that the class QLC0\mathrm{QLC}^0QLC0, corresponding to linear size QAC0\mathrm{QAC}^0QAC0 circuits, has approximate degree o(n)o(n)o(n). This is a quantum generalization of the result that LC0\mathrm{LC}^0LC0 circuits have approximate degree o(n)o(n)o(n) by Bun, Robin, and Thaler [SODA 2019]. Our result also implies that QLC0≠NC1\mathrm{QLC}^0\neq\mathrm{NC}^1QLC0=NC1.
Bounds on the QAC0^00 Complexity of Approximating Parity
QAC circuits are quantum circuits with one-qubit gates and Toffoli gates of arbitrary arity. QAC0^00 circuits are QAC circuits of constant depth, and are quantum analogues of AC0^00 circuits. We prove the following: ∙\bullet∙ For all d≥7d \ge 7d≥7 and ε>0\varepsilon>0ε>0 there is a depth-ddd QAC circuit of size exp⁡(poly(n1/d)log⁡(n/ε))\exp(\mathrm{poly}(n^{1/d}) \log(n/\varepsilon))exp(poly(n1/d)log(n/ε)) that approximates the nnn-qubit parity function to within error ε\varepsilonε on worst-case quantum inputs. Previously it was unknown whether QAC circuits of sublogarithmic depth could approximate parity regardless of size. ∙\bullet∙ We introduce a class of "mostly classical" QAC circuits, including a major component of our circuit from the above upper bound, and prove a tight lower bound on the size of low-depth, mostly classical QAC circuits that approximate this component. ∙\bullet∙ Arbitrary depth-ddd QAC circuits require at least Ω(n/d)Ω(n/d)Ω(n/d) multi-qubit gates to achieve a 1/2+exp⁡(−o(n/d))1/2 + \exp(-o(n/d))1/2+exp(−o(n/d)) approximation of parity. When d=Θ(log⁡n)d = Θ(\log n)d=Θ(logn) this nearly matches an easy O(n)O(n)O(n) size upper bound for computing parity exactly. ∙\bullet∙ QAC circuits with at most two layers of multi-qubit gates cannot achieve a 1/2+exp⁡(−o(n))1/2 + \exp(-o(n))1/2+exp(−o(n)) approximation of parity, even non-cleanly. Previously it was known only that such circuits could not cleanly compute parity exactly for sufficiently large nnn. The proofs use a new normal form for quantum circuits which may be of independent interest, and are based on reductions to the problem of constructing certain generalizations of the cat state which we name "nekomata" after an analogous cat yōkai.
QAC0\mathsf{QAC}^0QAC0 Contains TC0\mathsf{TC}^0TC0 (with Many Copies of the Input)
QAC0\mathsf{QAC}^0QAC0 is the class of constant-depth polynomial-size quantum circuits constructed from arbitrary single-qubit gates and generalized Toffoli gates. It is arguably the smallest natural class of constant-depth quantum computation which has not been shown useful for computing any non-trivial Boolean function. Despite this, many attempts to port classical AC0\mathsf{AC}^0AC0 lower bounds to QAC0\mathsf{QAC}^0QAC0 have failed. We give one possible explanation of this: QAC0\mathsf{QAC}^0QAC0 circuits are significantly more powerful than their classical counterparts. We show the unconditional separation QAC0⊄AC0[p]\mathsf{QAC}^0\not\subset\mathsf{AC}^0[p]QAC0⊂AC0[p] for decision problems, which also resolves for the first time whether AC0\mathsf{AC}^0AC0 could be more powerful than QAC0\mathsf{QAC}^0QAC0. Moreover, we prove that QAC0\mathsf{QAC}^0QAC0 circuits can compute a wide range of Boolean functions if given multiple copies of the input: TC0⊆QAC0∘NC0\mathsf{TC}^0 \subseteq \mathsf{QAC}^0 \circ \mathsf{NC}^0TC0⊆QAC0∘NC0. Along the way, we introduce an amplitude amplification technique that makes several approximate constant-depth constructions exact.
Bounds on the QAC0\mathrm{QAC}^0QAC0 Complexity of Approximating Parity
QAC\mathrm{QAC}QAC circuits are quantum circuits with one-qubit gates and Toffoli gates of arbitrary arity. QAC0\mathrm{QAC}^0QAC0 circuits are QAC\mathrm{QAC}QAC circuits of constant depth, and are quantum analogues of AC0\mathrm{AC}^0AC0 circuits. We prove the following: ∙\bullet∙ For all d≥7d \ge 7d≥7 and ε>0\varepsilon>0ε>0 there is a depth-ddd QAC\mathrm{QAC}QAC circuit of size exp⁡(poly(n1/d)log⁡(n/ε))\exp(\mathrm{poly}(n^{1/d}) \log(n/\varepsilon))exp(poly(n1/d)log(n/ε)) that approximates the nnn-qubit parity function to within error ε\varepsilonε on worst-case quantum inputs. Previously it was unknown whether QAC\mathrm{QAC}QAC circuits of sublogarithmic depth could approximate parity regardless of size. ∙\bullet∙ We introduce a class of QAC\mathrm{QAC}QAC circuits, including a major component of our circuit from the above upper bound, and prove a tight lower bound on the size of low-depth, mostly classical QAC\mathrm{QAC}QAC circuits that approximate this component. ∙\bullet∙ Arbitrary depth-ddd QAC\mathrm{QAC}QAC circuits require at least Ω(n/d)\Omega(n/d)Ω(n/d) multi-qubit gates to achieve a 1/2+exp⁡(−o(n/d))1/2 + \exp(-o(n/d))1/2+exp(−o(n/d)) approximation of parity. When d=Θ(log⁡n)d = \Theta(\log n)d=Θ(logn) this nearly matches an easy O(n)O(n)O(n) size upper bound for computing parity exactly. ∙\bullet∙ QAC\mathrm{QAC}QAC circuits with at most two layers of multi-qubit gates cannot achieve a 1/2+exp⁡(−o(n))1/2 + \exp(-o(n))1/2+exp(−o(n)) approximation of parity, even non-cleanly. Previously it was known only that such circuits could not cleanly compute parity exactly for sufficiently large nnn. The proofs use a new normal form for quantum circuits which may be of independent interest, and are based on reductions to the problem of constructing certain generalizations of the cat state which we name nekomata after an analogous cat y\=okai.
In this work we study the robustness of QAC0\mathsf{QAC}^0QAC0 with respect to error tolerance and modifications to its gate-set. First, we investigate whether the non-zero error typically allowed for QAC0\mathsf{QAC}^0QAC0 circuits computing Boolean functions is truly necessary. We show that the error inherent in the parallel WWW-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\mathsf{QAC}^0QAC0 can \textit{exactly} simulate TC0\mathsf{TC}^0TC0 with polynomially many copies of the classical input and that for every fixed prime ppp exact QAC0\mathsf{QAC}^0QAC0, EQAC0\mathsf{EQAC}^0EQAC0, can compute total Boolean functions outside of AC0[p]\mathsf{AC}^0[p]AC0[p]. Second, we ask to what extent the computational power of QAC0\mathsf{QAC}^0QAC0 follows from the fact that arbitrary single-qubit gates may be used at any point in the circuit. We find that QAC0\mathsf{QAC}^0QAC0 is in fact robust to restrictions on which single-qubit gates are permitted: every QAC0\mathsf{QAC}^0QAC0 circuit can be approximately implemented by a QAC0\mathsf{QAC}^0QAC0 circuit consisting of just generalized Toffoli, SSS, and Hadamard gates. Moreover, this approximating circuit can be constructed efficiently from a classical description of the original circuit.
Low-degree approximation of QAC0^00 circuits
QAC0^00 is the class of constant-depth quantum circuits with polynomially many ancillary qubits, where Toffoli gates on arbitrarily many qubits are allowed. In this work, we show that the parity function cannot be computed in QAC0^00, resolving a long-standing open problem in quantum circuit complexity more than twenty years old. As a result, this proves QAC0⫋QACwf0{\rm QAC}^0 \subsetneqq {\rm QAC}_{\rm wf}^0QAC0⫋QACwf0​. We also show that any QAC circuit of depth ddd that approximately computes parity on nnn bits requires 2Ω~(n1/d)2^{\widetildeΩ(n^{1/d})}2Ω(n1/d) ancillary qubits, which is close to tight. This implies a similar lower bound on approximately preparing cat states using QAC circuits. Finally, we prove a quantum analog of the Linial-Mansour-Nisan theorem for QAC0^00. This implies that, for any QAC0^00 circuit UUU with a=poly(n)a={\rm poly}(n)a=poly(n) ancillary qubits, and for any x∈{0,1}nx\in\{0,1\}^nx∈{0,1}n, the correlation between Q(x)Q(x)Q(x) and the parity function is bounded by 1/2+2−Ω~(n1/d){1}/{2} + 2^{-\widetildeΩ(n^{1/d})}1/2+2−Ω(n1/d), where Q(x)Q(x)Q(x) denotes the output of measuring the output qubit of U∣x,0a⟩U|x,0^a\rangleU∣x,0a⟩. All the above consequences rely on the following technical result. If UUU is a QAC0^00 circuit with a=poly(n)a={\rm poly}(n)a=poly(n) ancillary qubits, then there is a distribution D\mathcal{D}D of bounded polynomials of degree polylog(n)(n)(n) such that with high probability, a random polynomial from D\mathcal{D}D approximates the function ⟨x,0a∣U†Zn+1U∣x,0a⟩\langle x,0^a| U^†Z_{n+1} U |x,0^a\rangle⟨x,0a∣U†Zn+1​U∣x,0a⟩ for a large fraction of x∈{0,1}nx\in \{0,1\}^nx∈{0,1}n. This result is analogous to the Razborov-Smolensky result on the approximation of AC0^00 circuits by random low-degree polynomials.