==== TABLE OF CONTENTS ====
Product-projection-localization-and-the-QAC0-parity-lower-bound//main.tex
Product-projection-localization-and-the-QAC0-parity-lower-bound//preamble.tex
Product-projection-localization-and-the-QAC0-parity-lower-bound//references.tex
Product-projection-localization-and-the-QAC0-parity-lower-bound//sections/bootstrap.tex
Product-projection-localization-and-the-QAC0-parity-lower-bound//sections/consequences.tex
Product-projection-localization-and-the-QAC0-parity-lower-bound//sections/depth_reduction.tex
Product-projection-localization-and-the-QAC0-parity-lower-bound//sections/introduction.tex
Product-projection-localization-and-the-QAC0-parity-lower-bound//sections/localization.tex
Product-projection-localization-and-the-QAC0-parity-lower-bound//sections/parity.tex
Product-projection-localization-and-the-QAC0-parity-lower-bound//sections/polynomial.tex
===========================
==== BEGIN Product-projection-localization-and-the-QAC0-parity-lower-bound//main.tex ====
\documentclass[11pt]{article}
\input{preamble}
\title{Product-projection localization and the\\
\texorpdfstring{$\QAC$}{QAC0} parity lower bound}
\author{OpenAI}
\date{September 24, 2026}
\begin{document}
\maketitle
\begin{abstract}
We prove that constant-depth quantum circuits with arbitrary one-qubit
and unbounded-arity Toffoli gates cannot compute parity with any fixed
positive worst-case advantage using polynomially many qubits. Ancillas
start in zero, only one output qubit is measured, and all final garbage
is unrestricted. This resolves Moore's parity conjecture in the
measured-output model.
\end{abstract}
\input{sections/introduction}
\input{sections/localization}
\input{sections/polynomial}
\input{sections/depth_reduction}
\input{sections/bootstrap}
\input{sections/parity}
\input{sections/consequences}
\input{references}
\end{document}
==== END Product-projection-localization-and-the-QAC0-parity-lower-bound//main.tex ====
==== BEGIN Product-projection-localization-and-the-QAC0-parity-lower-bound//preamble.tex ====
\input{glyphtounicode}
\input{glyphtounicode-cmex}
\pdfgentounicode=1
\pdfinfoomitdate=1
\pdftrailerid{}
\pdfsuppressptexinfo=15
\usepackage[T1]{fontenc}
\usepackage{lmodern,microtype}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage[margin=1.05in]{geometry}
\usepackage[dvipsnames]{xcolor}
\usepackage{hyperref}
\usepackage{xurl}
\usepackage{aliascnt}
\usepackage[nameinlink,capitalise,noabbrev]{cleveref}
\hypersetup{colorlinks=true,linkcolor=MidnightBlue,citecolor=MidnightBlue,
urlcolor=MidnightBlue,pdfauthor={OpenAI},
pdftitle={Product-projection localization and the QAC0 parity lower bound}}
\setlength{\emergencystretch}{2em}
\numberwithin{equation}{section}
\newtheorem{theorem}{Theorem}
\newaliascnt{lemma}{theorem}
\newtheorem{lemma}[lemma]{Lemma}
\aliascntresetthe{lemma}
\newaliascnt{proposition}{theorem}
\newtheorem{proposition}[proposition]{Proposition}
\aliascntresetthe{proposition}
\newaliascnt{corollary}{theorem}
\newtheorem{corollary}[corollary]{Corollary}
\aliascntresetthe{corollary}
\theoremstyle{definition}
\newaliascnt{definition}{theorem}
\newtheorem{definition}[definition]{Definition}
\aliascntresetthe{definition}
\theoremstyle{remark}
\newaliascnt{remark}{theorem}
\newtheorem{remark}[remark]{Remark}
\aliascntresetthe{remark}
\newcommand{\QAC}{\mathrm{QAC}^0}
\newcommand{\cU}{\mathcal U}
\newcommand{\cB}{\mathcal B}
\newcommand{\ket}[1]{\lvert #1\rangle}
\newcommand{\bra}[1]{\langle #1\rvert}
\newcommand{\proj}[1]{\ket{#1}\!\bra{#1}}
\newcommand{\norm}[1]{\left\lVert #1\right\rVert}
\newcommand{\E}{\mathbb E}
\DeclareMathOperator{\supp}{supp}
\DeclareMathOperator{\parity}{PARITY}
==== END Product-projection-localization-and-the-QAC0-parity-lower-bound//preamble.tex ====
==== BEGIN Product-projection-localization-and-the-QAC0-parity-lower-bound//references.tex ====
\begin{thebibliography}{FFGHZ06}
\bibitem[Ajt83]{Ajtai1983}
Mikl\'os Ajtai.
\newblock $\Sigma^1_1$-formulae on finite structures.
\newblock \emph{Annals of Pure and Applied Logic}, 24(1):1--48, 1983.
\newblock \href{https://doi.org/10.1016/0168-0072(83)90038-6}{doi:10.1016/0168-0072(83)90038-6}.
\bibitem[ADOY25]{ADOY2025}
Anurag Anshu, Yangjing Dong, Fengning Ou, and Penghui Yao.
\newblock On the Computational Power of $\mathsf{QAC}^{0}$ with Barely
Superlinear Ancillae.
\newblock In \emph{Proceedings of the 57th Annual ACM Symposium on Theory of
Computing (STOC 2025)}, pages 1476--1487, 2025.
\newblock \href{https://doi.org/10.1145/3717823.3718189}{doi:10.1145/3717823.3718189}.
Full version: \href{https://arxiv.org/abs/2410.06499v4}{arXiv:2410.06499v4},
21 December 2025.
\bibitem[AM23]{AnshuMetger2023}
Anurag Anshu and Tony Metger.
\newblock Concentration bounds for quantum states and limitations on the
QAOA from polynomial approximations.
\newblock \emph{Quantum}, 7:999, 2023.
\newblock \href{https://doi.org/10.22331/q-2023-05-11-999}{doi:10.22331/q-2023-05-11-999}.
\bibitem[Ber11]{Bera2011}
Debajyoti Bera.
\newblock A lower bound method for quantum circuits.
\newblock \emph{Information Processing Letters}, 111(15):723--726, 2011.
\newblock \href{https://doi.org/10.1016/j.ipl.2011.05.002}{doi:10.1016/j.ipl.2011.05.002}.
\bibitem[DOY25]{DOY2025LinearSize}
Yangjing Dong, Fengning Ou, and Penghui Yao.
\newblock \emph{Linear-Size QAC0 Channels: Learning, Testing and Hardness}.
\newblock 2025. \href{https://arxiv.org/abs/2510.00593v2}{arXiv:2510.00593v2},
8 November 2025.
\bibitem[FFGHZ06]{FangFennerGreenHomerZhang2006}
Maosen Fang, Stephen Fenner, Frederic Green, Steven Homer, and Yong Zhang.
\newblock Quantum lower bounds for fanout.
\newblock \emph{Quantum Information and Computation}, 6(1):46--57, 2006.
\newblock \href{https://doi.org/10.26421/QIC6.1-3}{doi:10.26421/QIC6.1-3}.
\bibitem[FGPT25]{FennerGrierPadeThierauf2025}
Stephen Fenner, Daniel Grier, Daniel Pad\'e, and Thomas Thierauf.
\newblock \emph{Tight Bounds on Depth-2 QAC-Circuits Computing Parity}.
\newblock 2025. \href{https://arxiv.org/abs/2504.06433v1}{arXiv:2504.06433v1},
8 April 2025.
\bibitem[FSS84]{FurstSaxeSipser1984}
Merrick Furst, James B. Saxe, and Michael Sipser.
\newblock Parity, circuits, and the polynomial-time hierarchy.
\newblock \emph{Mathematical Systems Theory}, 17:13--27, 1984.
\newblock \url{https://doi.org/10.1007/BF01744431}.
\bibitem[GHMP02]{GreenHomerMoorePollett2002}
Frederic Green, Steven Homer, Cristopher Moore, and Christopher Pollett.
\newblock Counting, fanout and the complexity of quantum ACC.
\newblock \emph{Quantum Information and Computation}, 2(1):35--65, 2002.
\newblock \href{https://doi.org/10.26421/QIC2.1-3}{doi:10.26421/QIC2.1-3}.
\bibitem[GGJ26a]{GGJ2026}
Lucas Gretta, Meghal Gupta, and Malvika Raj Joshi.
\newblock \emph{Parity $\notin\mathsf{QAC}^{0}$ $\Longleftrightarrow$
$\mathsf{QAC}^{0}$ is Fourier-Concentrated}.
\newblock 2026. \href{https://arxiv.org/abs/2604.02793v2}{arXiv:2604.02793v2},
25 August 2026.
\bibitem[GGJ26b]{GGJ2026StatePreparation}
Lucas Gretta, Meghal Gupta, and Malvika Raj Joshi.
\newblock \emph{$\mathsf{QAC}^{0}$ Can Prepare Every Logarithmic-Qubit State}.
\newblock 2026. \href{https://arxiv.org/abs/2609.17408v1}{arXiv:2609.17408v1},
15 September 2026.
\bibitem[H\aa s86]{Hastad1986}
Johan H\aa stad.
\newblock Almost optimal lower bounds for small depth circuits.
\newblock In \emph{Proceedings of the Eighteenth Annual ACM Symposium on
Theory of Computing}, pages 6--20, 1986.
\newblock \href{https://doi.org/10.1145/12130.12132}{doi:10.1145/12130.12132}.
\bibitem[H\v S05]{HoyerSpalek2005}
Peter H\o yer and Robert \v Spalek.
\newblock Quantum Fan-out is Powerful.
\newblock \emph{Theory of Computing}, 1(5):81--103, 2005.
\newblock \href{https://doi.org/10.4086/toc.2005.v001a005}{doi:10.4086/toc.2005.v001a005}.
\bibitem[JTVW26]{JTVW2026}
Malvika Raj Joshi, Avishay Tal, Francisca Vasconcelos, and John Wright.
\newblock Improved Lower Bounds for $\mathsf{QAC}^{0}$.
\newblock In \emph{Proceedings of the 58th Annual ACM Symposium on Theory of
Computing (STOC 2026)}, pages 2199--2209, 2026.
\newblock \href{https://doi.org/10.1145/3798129.3800922}{doi:10.1145/3798129.3800922}.
Full version: \href{https://arxiv.org/abs/2512.14643v4}{arXiv:2512.14643v4},
25 August 2026.
\bibitem[Kin26]{Kintali2026ShallowParity}
Shiva Kintali.
\newblock \emph{Parity in Shallow QAC Circuits: Correlation Decay and Exact
Lower Bounds}.
\newblock Preprint, September 5, 2026.
\newblock \url{https://shivakintali.github.io/papers/QAC.pdf}.
\bibitem[KAAV17]{KuwaharaAradAmicoVedral2017}
Tomotaka Kuwahara, Itai Arad, Luigi Amico, and Vlatko Vedral.
\newblock Local reversibility and entanglement structure of many-body ground states.
\newblock \emph{Quantum Science and Technology}, 2(1):015005, 2017.
\newblock \href{https://doi.org/10.1088/2058-9565/aa523d}{doi:10.1088/2058-9565/aa523d}.
Full version: \href{https://arxiv.org/abs/1502.05330v3}{arXiv:1502.05330v3}.
\bibitem[Moo99]{Moore1999}
Cristopher Moore.
\newblock \emph{Quantum Circuits: Fanout, Parity, and Counting}.
\newblock 1999. \href{https://arxiv.org/abs/quant-ph/9903046v3}{arXiv:quant-ph/9903046v3},
17 March 1999.
\bibitem[NPVY24]{NPVY2024}
Shivam Nadimpalli, Natalie Parham, Francisca Vasconcelos, and Henry Yuen.
\newblock On the Pauli Spectrum of $\mathsf{QAC}^{0}$.
\newblock In \emph{Proceedings of the 56th Annual ACM Symposium on Theory of
Computing (STOC 2024)}, pages 1498--1506, 2024.
\newblock \href{https://doi.org/10.1145/3618260.3649662}{doi:10.1145/3618260.3649662}.
Full version: \href{https://arxiv.org/abs/2311.09631v4}{arXiv:2311.09631v4},
17 July 2024.
\bibitem[O'D03]{ODonnell2003Noise}
Ryan O'Donnell.
\newblock \emph{Computational Applications of Noise Sensitivity}.
\newblock Ph.D. thesis, Massachusetts Institute of Technology, 2003.
\newblock \url{https://www.cs.cmu.edu/~odonnell/papers/thesis.pdf}.
\bibitem[Ope26]{OpenAI2026Trajectories}
OpenAI.
\newblock \emph{Regular trajectories, pruning and quantum parity}.
\newblock OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Regular-trajectories-pruning-and-quantum-parity-September-24-2026/paper.pdf}{OAI:Regular-trajectories-pruning-and-quantum-parity-September-24-2026}, 2026.
\bibitem[PFGT20]{PadeFennerGrierThierauf2020}
Daniel Pad\'e, Stephen Fenner, Daniel Grier, and Thomas Thierauf.
\newblock \emph{Depth-2 QAC Circuits Cannot Simulate Quantum Parity}.
\newblock 2020. \href{https://arxiv.org/abs/2005.12169v1}{arXiv:2005.12169v1},
25 May 2020.
\bibitem[Pat92]{Paturi1992}
Ramamohan Paturi.
\newblock On the degree of polynomials that approximate symmetric Boolean
functions (preliminary version).
\newblock In \emph{Proceedings of the Twenty-Fourth Annual ACM Symposium
on Theory of Computing (STOC 1992)}, pages 468--474, 1992.
\newblock \href{https://doi.org/10.1145/129712.129758}{doi:10.1145/129712.129758}.
\bibitem[Ros21]{Rosenthal2021}
Gregory Rosenthal.
\newblock Bounds on the $\mathsf{QAC}^{0}$ Complexity of Approximating Parity.
\newblock In \emph{12th Innovations in Theoretical Computer Science Conference
(ITCS 2021)}, volume 185 of \emph{Leibniz International Proceedings in
Informatics}, pages 32:1--32:20, 2021.
\newblock \href{https://doi.org/10.4230/LIPIcs.ITCS.2021.32}{doi:10.4230/LIPIcs.ITCS.2021.32}.
Full version: \href{https://arxiv.org/abs/2008.07470v3}{arXiv:2008.07470v3},
30 November 2020.
\bibitem[She09]{Sherstov2009}
Alexander A. Sherstov.
\newblock Approximate inclusion-exclusion for arbitrary symmetric functions.
\newblock \emph{Computational Complexity}, 18(2):219--247, 2009.
\newblock \href{https://web.cs.ucla.edu/~sherstov/pdf/incl-excl.pdf}{Author manuscript}.
\bibitem[XL26]{XuLi2026Fanout}
Boyan Xu and Lvzhou Li.
\newblock \emph{Fanout Complexity of Symmetric Boolean Functions in
$\mathsf{QAC}^0$}.
\newblock 2026. \href{https://arxiv.org/abs/2609.05153v1}{arXiv:2609.05153v1},
4 September 2026.
\bibitem[Yao85]{Yao1985}
Andrew Chi-Chih Yao.
\newblock Separating the polynomial-time hierarchy by oracles.
\newblock In \emph{Proceedings of the 26th Annual Symposium on Foundations
of Computer Science (FOCS 1985)}, pages 1--10, 1985.
\newblock \href{https://doi.org/10.1109/SFCS.1985.49}{doi:10.1109/SFCS.1985.49}.
\end{thebibliography}
==== END Product-projection-localization-and-the-QAC0-parity-lower-bound//references.tex ====
==== BEGIN Product-projection-localization-and-the-QAC0-parity-lower-bound//sections/bootstrap.tex ====
\section{The finite scale induction}
\label{sec:bootstrap}
The preceding depth gives localization for projections with small
support. We now extend that estimate to arbitrary product projections.
The extension uses the inverse circuit at a larger mismatch scale.
The main constraint is how far that scale can move: to prove
$\cB_d(s,t)$ from $\cB_d(t,b)$, we need
$t<b<2t-s$. This interval leaves room for a polynomial whose
approximation error decays faster than $e^{-N^s}$ while its degree
and the logarithm of its weighted coefficient norm remain below the
mismatch threshold $N^t$.
\begin{lemma}[One backward step]
\label{lem:backward}
Fix \(d\ge1\), and assume \(\cB_{d-1}(s,t)\) for every fixed
\(0\le s<t\). Let \(s,t,b\) be fixed real numbers with
\[
0\le s<t<b<2t-s.
\]
If \(\cB_d(t,b)\) holds, then \(\cB_d(s,t)\) holds.
\end{lemma}
\begin{proof}
Choose fixed auxiliary exponents
\[
s<a<2t-b,\qquad \frac{a+b}{2}<u<w<t.
\]
These choices are possible because $b<2t-s$. Since $b>t>a$,
they give exactly the inequalities required by the polynomial and
small-support estimates:
\begin{equation}
\label{eq:step-parameters}
0\le s<a<u<w<t<b,\qquad u>\frac{a+b}{2}.
\end{equation}
Fix \(U\in\cU_d(N)\) and counts \(M,D\), and put
\[
P=[M=0],\qquad H=[M\ge N^t],\qquad
C=UDU^\dagger,\qquad Q=[C=0]=U[D=0]U^\dagger.
\]
Let \(p(x)=\sum_kc_kx^k\) be the polynomial in
\Cref{lem:polynomial} for \(a,b,u\). We will first control
$Hp(C)P$ by small-support localization. Squaring the desired norm
will then place the remaining high-$C$ error on $PQ$, where the
larger-scale hypothesis applies after inversion.
Each count summand is a rank-one projection on one qubit.
Expanding \(D^k\) gives at most \(N^k\) ordered monomials, each a
product projection on at most \(k\) qubits: repeated indices collapse
by idempotence, while different indices commute.
For \(k\le\deg p\le N^u\), \Cref{lem:small-support} applies to
every such monomial with the same fixed exponents \(u,w,t\).
Since \(p(C)=Up(D)U^\dagger\), its coefficient bound gives
\begin{equation}
\label{eq:polynomial-transition}
\norm{Hp(C)P}
\le e^{-N^w}\sum_k|c_k|N^k
\le e^{N^u-N^w}.
\end{equation}
The constant term causes no difficulty: it is a multiple of \(I\),
and \(HP=0\). Also, \(\norm C\le N\) gives
\begin{equation}
\label{eq:polynomial-norm}
\norm{p(C)}\le\sum_k|c_k|N^k\le e^{N^u}.
\end{equation}
The polynomial need not approximate \(Q\) on all of \(\mathcal H_N\).
Squaring the desired norm makes the approximation error occur as
\((Q-p(C))PQ\), rather than \((Q-p(C))P\):
\begin{align}
\norm{HQP}^2
&=\norm{HQPQH}\notag\\
&\le \norm{Hp(C)PQH}+\norm{H(Q-p(C))PQH}\notag\\
&\le \norm{Hp(C)P}+\norm{(Q-p(C))PQ}.
\label{eq:square}
\end{align}
Only the leftmost \(Q\) was replaced in this decomposition. No commutation
of \(P\) with \(C\) or \(Q\) is involved.
Split the last error at the spectral threshold \(N^b\) of \(C\).
The spectral projections of \(C\) commute with \(Q\) and \(p(C)\).
On \([C<N^b]\), the error is zero at eigenvalue \(0\), since
\(p(0)=1\), and at most \(e^{-N^a}\) at every positive eigenvalue,
since these eigenvalues are integers. Hence
\begin{equation}
\label{eq:error-split}
\norm{(Q-p(C))PQ}
\le e^{-N^a}+(1+e^{N^u})\norm{[C\ge N^b]PQ}.
\end{equation}
The remaining factor is exactly the transition controlled by the
inverse circuit. Unitary conjugation gives
\begin{align}
\norm{[C\ge N^b]PQ}
&=\norm{[D\ge N^b]\,U^\dagger[M=0]U[D=0]}\notag\\
&\le e^{-N^t}.
\label{eq:inverse-tail}
\end{align}
Here \(\cB_d(t,b)\) applies with circuit \(U^\dagger\), mismatch
count \(D\), and projected count \(M\). Inverse closure
\eqref{eq:inverse} and the universal quantifiers in
\(\cB_d(t,b)\) are both used.
Combining \eqref{eq:polynomial-transition}, \eqref{eq:square},
\eqref{eq:error-split}, and \eqref{eq:inverse-tail} yields
\begin{equation}
\label{eq:step-bound}
\norm{HQP}^2
\le e^{N^u-N^w}+e^{-N^a}+(1+e^{N^u})e^{-N^t}.
\end{equation}
By \eqref{eq:step-parameters}, each term is eventually at most
\(\tfrac13e^{-2N^s}\). Indeed \(w>u\), \(t>u\), and
\(a,w,t>s\). This remains true for \(s=0\), when the comparison
quantity is a fixed positive constant. Taking the square root proves
\(\cB_d(s,t)\). All sufficient lower bounds on \(N\) depend only
on the fixed parameters and \(d\), so the conclusion is uniform.
\end{proof}
We now choose a finite chain of scales within this interval. Each step
will advance the mismatch exponent by almost the current gap $t-s$.
Keeping at least half of the initial gap for $O(1/(t-s))$ steps will
carry that exponent above one, where the tail projection vanishes.
A slack of order $(t-s)^2$ per step is small enough to preserve the gap.
\begin{proof}[Proof of \Cref{thm:localization}]
The case \(d=0\) is \Cref{lem:base}. Fix \(d\ge1\), and assume the
theorem at depth \(d-1\) for every fixed exponent pair.
It remains to prove \(\cB_d(s,t)\) for fixed \(0\le s<t\le1\);
the case \(t>1\) is immediate.
Put
\[
g=t-s,\qquad \eta=\frac{g^2}{100},\qquad
s_0=s,\quad t_0=t,
\]
and define
\begin{equation}
\label{eq:scale-recurrence}
s_{i+1}=t_i,\qquad t_{i+1}=2t_i-s_i-3\eta.
\end{equation}
Writing \(g_i=t_i-s_i\), we have
\[
g_i=g-3i\eta,\qquad t_{i+1}-t_i=g_{i+1}.
\]
Let \(K=\lceil2/g\rceil\). Since \(0<g\le1\),
\[
3K\eta\le \frac{3(2/g+1)g^2}{100}
\le0.09g<\frac g2.
\]
Thus \(g_i>g/2\) for \(i\le K\), and
\[
t_K=t+\sum_{i=1}^K g_i>t+Kg/2\ge t+1>1.
\]
Let \(J\le K\) be the first index for which \(t_J>1\).
This index and every exponent in the chain are independent of \(N\).
The assertion \(\cB_d(s_J,t_J)\) is trivial.
\begin{figure}[htbp]
\centering
\[
\underbrace{\cB_d(s_0,t_0)}_{\text{target}}
\ \Longleftarrow\
\cB_d(s_1,t_1)
\ \Longleftarrow\ \cdots\ \Longleftarrow\
\underbrace{\cB_d(s_J,t_J)}_{t_J>1:\ \text{trivial}} .
\]
\caption{The same-depth induction runs from right to left along a
finite chain; \(J\) is the first index with \(t_J>1\).
Each implication is \Cref{lem:backward} and also uses
the already established localization theorem at depth \(d-1\).
The inverse circuit is substituted only into the universal statement
at the next pair, after that statement has been proved.}
\label{fig:scales}
\end{figure}
Suppose now that $\cB_d(s_{i+1},t_{i+1})$ has been proved,
where $i<J$. The recurrence and the positive next gap give
\[
t_i<t_{i+1}=2t_i-s_i-3\eta<2t_i-s_i.
\]
Thus \Cref{lem:backward} applies with $b=t_{i+1}$. Its assumed
assertion is precisely
$\cB_d(t_i,t_{i+1})=\cB_d(s_{i+1},t_{i+1})$, so it proves
$\cB_d(s_i,t_i)$.
Working backward reaches the target pair, as in \Cref{fig:scales}.
There are only finitely many steps for each fixed \(d,s,t\).
Taking the maximum of their sufficient lower bounds on \(N\)
preserves uniformity over every circuit and pair of counts. Each step
uses only finitely many fixed exponent tuples from depth $d-1$; the
number of monomials and their varying supports are paid for by the
explicit coefficient estimates, not by further asymptotic thresholds.
Thus the induction does not require a threshold uniform over all real
exponent pairs. This completes the depth induction.
\end{proof}
==== END Product-projection-localization-and-the-QAC0-parity-lower-bound//sections/bootstrap.tex ====
==== BEGIN Product-projection-localization-and-the-QAC0-parity-lower-bound//sections/consequences.tex ====
\section{Consequences of localization and parity}
\label{sec:consequences}
The direct parity proof is complete. Localization next bounds
complementary-output probabilities, and a construction of Gretta, Gupta,
and Joshi~\cite{GGJ2026} gives a Dicke-state obstruction. We also derive
scalar-output Fourier concentration directly from localization.
This concentration rules out high average accuracy for majority,
while Xu and Li's reductions~\cite{XuLi2026Fanout} give worst-case
obstructions for symmetric functions. Throughout, discarded registers
remain unrestricted.
\subsection{State preparation}
\label{sec:state-preparation}
Gretta, Gupta, and Joshi~\cite{GGJ2026} connect complementary-output
probabilities and Dicke-state preparation to parity. Here localization
bounds the complementary probabilities directly; their block construction
then gives the Dicke-state consequence.
For an $n$-qubit density operator $\rho$, write
\[
p_y=\bra{y}\rho\ket{y},\qquad
\mathcal F_n(\rho)=2\sum_{y\in\{0,1\}^n}p_y p_{\bar y},
\]
where $\bar y$ is the bitwise complement of $y$.
This is the \emph{felinity} of $\rho$~\cite[Definition~2.1]{GGJ2026}.
Also write
\[
\ket{D_k^n}=\binom{n}{k}^{-1/2}\sum_{|y|=k}\ket{y},
\qquad
\operatorname{TD}(\rho,\sigma)=\tfrac12\norm{\rho-\sigma}_1
\]
for the weight-$k$ Dicke state and trace distance, respectively.
\begin{corollary}[State-preparation obstructions]
\label{cor:state-preparation}
Fix a nonnegative integer $d$, $c\ge1$, $a>0$, and $0<\delta<1$.
For all sufficiently large $n$, every $n$-qubit reduced state $\rho$
prepared from zero inputs by an allowed depth-at-most-$d$ circuit on
at most $n^c$ total qubits satisfies
\[
\mathcal F_n(\rho)<n^{-a}.
\]
Moreover, for every integer $k$ with $n^\delta\le k\le n/2$,
\[
\operatorname{TD}(\rho,\proj{D_k^n})>\frac1{80k}.
\]
The remaining qubits may be discarded in arbitrary final states.
\end{corollary}
\begin{proof}
Retain all $N$ preparation qubits, including those eventually discarded,
and write $\ket\psi=U\ket{0^N}$ and $Q=\proj\psi$. Thus $Q$ is the
conjugate by $U\in\cU_d(N)$ of a product projection. For an output string
$y$, let $P_y$ fix the $n$ output qubits to $y$ and act identically on the
remaining register, and let $M_y$ count mismatches from $y$ on the outputs.
Then $P_y=[M_y=0]$ and $\norm{P_y\psi}^2=p_y$. Fix $0<s<t<1/c$.
For sufficiently large $n$, $N^t<n$, so the complementary-string
projection satisfies $P_{\bar y}\le[M_y\ge N^t]$. Localization gives
\[
\sqrt{p_y p_{\bar y}}
=\norm{P_{\bar y}QP_y}\le e^{-N^s}
\qquad\text{for every }y.
\]
The threshold is uniform in $y$. Cauchy--Schwarz gives
$\sum_y\sqrt{p_y p_{\bar y}}\le1$, and hence
\[
\mathcal F_n(\rho)
\le2e^{-N^s}\sum_y\sqrt{p_y p_{\bar y}}
\le2e^{-N^s}<n^{-a}
\]
eventually. This argument uses the pure state on the complete register,
so it applies to every reduced output state $\rho$.
For the second assertion, we give the block construction underlying
\cite[Lemma~4.13 and Theorem~4.14]{GGJ2026}, including the estimates
needed at the stated trace distance. Put
\[
\ell=\lfloor k/\log k\rfloor,\qquad p=k/n,\qquad
\ket v=\sqrt{1-p}\ket0+\sqrt p\ket1.
\]
Partition the $n$ sites into $\ell$ blocks $B_j$ whose sizes $b_j$ differ
by at most one. Append one zero qubit $t_j$ per block, and on $B_jt_j$ apply
\[
(I-A_j)\otimes I+A_j\otimes X,
\qquad A_j=(\proj v)^{\otimes b_j}.
\]
Each gate equals $I-2A_j\otimes\proj{-}$, so all these gates form one
disjoint product-reflection layer, implemented by parallel one-qubit basis
changes, one Toffoli layer, and the inverse basis changes.
Let $\sigma_*$ be the resulting state of the $\ell$ new qubits when the
input is $\ket{D_k^n}$. Its all-one probability is
\[
r_1=|\langle v^{\otimes n}\mid D_k^n\rangle|^2
=\binom nk p^k(1-p)^{n-k}.
\]
For a binomial random variable $B$ with parameters $n,p$, the integer $k$
is a mode and $\operatorname{Var}(B)\le k$. Chebyshev's inequality gives
\[
(4\sqrt k+1)r_1\ge\Pr(|B-k|<2\sqrt k)\ge\frac34,
\qquad r_1\ge\left(\frac3{16}-o(1)\right)k^{-1/2},
\]
since the displayed interval contains at most $4\sqrt k+1$ integers.
This estimate is uniform in $n\ge2k$. The all-zero probability is
$r_0=\norm{\Pi\ket{D_k^n}}^2$, where $\Pi=\prod_j(I-A_j)$.
To bound it, use the unit vector
\[
\ket\nu=(\sqrt{1-p}\ket0-\sqrt p\ket1)^{\otimes n}.
\]
Since $b_j\ge n/\ell-1$, $p\le1/2$, and $k/\ell\ge\log k$,
\[
\langle\nu|A_j|\nu\rangle=(1-2p)^{2b_j}
\le e^{-4pb_j}\le e^2k^{-4}.
\]
The commuting projections satisfy $I-\Pi\le\sum_jA_j$, so
$\norm{(I-\Pi)\nu}\le e k^{-3/2}$. Moreover,
$|\langle\nu\mid D_k^n\rangle|=\sqrt{r_1}$, because every term of the
Dicke state has weight $k$. Therefore
\[
\sqrt{r_0}\ge\sqrt{r_1}-e k^{-3/2},\qquad
\mathcal F_\ell(\sigma_*)\ge4r_0r_1
\ge\frac{9/64-o(1)}k>\frac1{8k}.
\]
All errors here are uniform for $k\le n/2$ as $k\to\infty$.
The factor four counts both complementary strings in the definition
of felinity.
Apply the same block circuit to $\rho$, and call its new-qubit state
$\sigma$. Trace distance contracts under a unitary and partial trace.
Also, for any two states $\tau,\tau'$ with computational-basis
probabilities $q,q'$, the definition gives
\[
|\mathcal F_\ell(\tau)-\mathcal F_\ell(\tau')|
\le4\sum_y|q_y-q'_y|
\le8\operatorname{TD}(\tau,\tau').
\]
Thus $\operatorname{TD}(\rho,\proj{D_k^n})\le1/(80k)$ would imply
\[
\mathcal F_\ell(\sigma)>\frac1{8k}-\frac8{80k}
=\frac1{40k}.
\]
For large $k$, $\ell\ge\sqrt k$, while $k\ge n^\delta$ gives
$n\le\ell^{2/\delta}$. The preparation of $\sigma$ therefore has fixed
depth and polynomially many total qubits as a function of $\ell$.
But $\ell^2/k\to\infty$, so its felinity exceeds $\ell^{-2}$ eventually,
contrary to the first assertion applied with target size $\ell$ and
exponent $a=2$. Since $k\ge n^\delta\to\infty$, all thresholds can be
chosen uniformly over the allowed $k$.
\end{proof}
In particular, no such family can assign inverse-polynomial
probabilities to both a string and its complement: their two terms
contribute $4p_y p_{\bar y}$ to $\mathcal F_n(\rho)$.
The polynomial bound in \Cref{cor:state-preparation} is measured in the
number $n$ of target qubits. Gretta, Gupta, and
Joshi~\cite[Theorem~1.1]{GGJ2026StatePreparation} show that every $n$-qubit
pure state can be prepared exactly at constant depth with $2^{O(n)}$
ancillas, all returned to zero.
\subsection{Scalar-output Fourier concentration}
Gretta, Gupta, and Joshi~\cite[Conjecture~1 and Corollary~1.2]{GGJ2026}
formulate a qualitative Quantum-LMN statement and establish its
equivalence with the parity lower-bound question. Our localization
theorem gives this Fourier-concentration statement directly.
For an $n$-input circuit $C$ on $N$ total qubits with output qubit $t$,
define its expected measured sign and uniform-input Fourier coefficients by
\begin{align*}
f_C(x)&=\bra{x,0^{N-n}}C^\dagger Z_tC\ket{x,0^{N-n}}\in[-1,1],\\
\widehat f_C(S)&=2^{-n}\sum_{x\in\{0,1\}^n}
f_C(x)(-1)^{\sum_{i\in S}x_i}.
\end{align*}
Write $W_{\ge k}[f_C]=\sum_{|S|\ge k}|\widehat f_C(S)|^2$.
This is the absolute squared Fourier tail, not a fraction of the
total weight $\mathbb E_x f_C(x)^2\le1$.
\begin{corollary}[Qualitative scalar-output Quantum-LMN]
\label{cor:quantum-lmn}
For every fixed nonnegative integer $d$, there is a positive function
$\gamma_d$ on the positive integers, depending only on $d$, such that
$\gamma_d(k)/k^A\to\infty$ for every fixed $A>0$, and every allowed
depth-at-most-$d$ circuit $C$ on $n$ inputs and $N$ total qubits,
every designated output $t$, and every integer $1\le k\le n$ satisfy
\[
W_{\ge k}[f_C]\le\frac{N}{\gamma_d(k)}.
\]
In particular, fix $c\ge1$, $0<\delta\le1$, and $B>0$. For all
sufficiently large $n$, uniformly over these circuits with $N\le n^c$,
\[
W_{\ge\lceil n^\delta\rceil}[f_C]\le n^{-B}.
\]
The sufficient threshold depends only on $d,c,\delta,B$.
\end{corollary}
\begin{proof}
Fix a circuit $C$ and let $Q=C^\dagger O_0C$, where $O_0$ projects its
output qubit onto $\ket0$. For $h\in\{0,1\}^n$, let $\xi_h$ be the
Hadamard product vector from the proof of \Cref{thm:parity}, and let
$M_h$ count mismatches from its factors on the $n$ input qubits.
For $S\subseteq[n]$, write $\mathbf 1_S$ for its indicator string.
The character calculation in \eqref{eq:parity-average}, with
$\bar h$ replaced by $h\oplus\mathbf 1_S$, gives
\[
\widehat f_C(S)
=2\E_h\bra{\xi_{h\oplus\mathbf 1_S},0}Q\ket{\xi_h,0}
\qquad(S\ne\varnothing),
\]
since $f_C(x)=2\bra{x,0}Q\ket{x,0}-1$.
For fixed $h$, the vectors $\ket{\xi_{h\oplus\mathbf 1_S},0}$ are
orthonormal as $S$ varies, and their $M_h$ counts are exactly $|S|$.
Jensen's and Bessel's inequalities therefore yield
\begin{align}
W_{\ge k}[f_C]
&\le4\E_h\sum_{|S|\ge k}
\left|\bra{\xi_{h\oplus\mathbf 1_S},0}Q\ket{\xi_h,0}\right|^2
\notag\\
&\le4\sup_h\norm{[M_h\ge k]Q[M_h=0]}^2.
\label{eq:fourier-localization}
\end{align}
For any fixed $0<\sigma<\tau$, \Cref{thm:localization} bounds this
by $4e^{-2N^\sigma}$ whenever $N$ is sufficiently large and
$k\ge N^\tau$. The threshold depends only on $d,\sigma,\tau$.
It remains to obtain one function of $k$ valid for every circuit size.
For each positive integer $k$, define
\[
b_d(k)=\sup\frac{W_{\ge k}[f_C]}{N},
\]
where the supremum ranges over all allowed depth-at-most-$d$ circuits,
all designated outputs, and all input and total sizes $k\le n\le N$.
Parseval's identity gives $W_{\ge k}[f_C]\le\E_x f_C(x)^2\le1$,
so $0\le b_d(k)\le1/k$.
Fix $A\ge1$. If $N\ge k^A$, then $W_{\ge k}[f_C]/N\le k^{-A}$.
For the remaining sizes $k\le N<k^A$, choose fixed
$0<\sigma<\tau<1/A$. For sufficiently large $k$, we have
$N^\tau<k$, so \eqref{eq:fourier-localization} gives
\[
\frac{W_{\ge k}[f_C]}{N}\le\frac{4e^{-2k^\sigma}}{k}.
\]
These two bounds are uniform over the supremum. Since $A$ is arbitrary,
$b_d(k)=o(k^{-B})$ for every fixed $B>0$.
Thus the positive function
\[
\gamma_d(k)=\frac1{b_d(k)+e^{-k}}
\]
satisfies $\gamma_d(k)/k^B\to\infty$ for every $B>0$, and the definition
of $b_d$ gives $W_{\ge k}[f_C]\le N/\gamma_d(k)$.
Finally, choose $B'>(c+B)/\delta$ in this superpolynomial growth
property to obtain the asserted cutoff consequence.
\end{proof}
\subsection{Majority and symmetric functions}
The reductions of Xu and Li turn the parity lower bound into a
worst-case lower bound for majority and broader symmetric families.
For a symmetric \(f_n:\{0,1\}^n\to\{0,1\}\), let \(f_{n,i}\) be its
value on inputs of Hamming weight \(i\), and define its transition radius by
\[
\rho(f_n)=\max_{\substack{0\le i<n\\f_{n,i}\ne f_{n,i+1}}}
\min\{i+1,n-i\},
\]
with \(\rho(f_n)=0\) for a constant function. Write
\(\widetilde{\deg}_{1/3}(f_n)\) for the least total degree of a real
polynomial approximating \(f_n\) pointwise within \(1/3\).
For nonconstant symmetric functions, Paturi's characterization
\cite[Theorem~1]{Paturi1992} gives
\[
\widetilde{\deg}_{1/3}(f_n)=\Theta\!\left(\sqrt{n\rho(f_n)}\right).
\]
Thus the approximate-degree hypothesis below also forces a polynomially
large transition radius.
\begin{corollary}[Majority and symmetric functions]
\label{cor:symmetric-functions}
Let \((f_n)\) be a symmetric Boolean family satisfying either
\(\rho(f_n)\ge n^\delta\) for some fixed \(\delta>0\), or
\(\widetilde{\deg}_{1/3}(f_n)=\Omega(n^{1/2+\eta})\) for some fixed
\(\eta>0\), for all sufficiently large \(n\). For every fixed
\(\gamma>0\), no nonuniform family in the circuit model of
\Cref{thm:parity}, with fixed depth and polynomially many total qubits,
computes \(f_n\) with probability at least
\(1/2+1/(\log n)^\gamma\) on every input for all sufficiently large \(n\).
In particular, this excludes strict majority
\(\operatorname{MAJ}_n(x)=\mathbf 1\{|x|>n/2\}\), whose transition radius
is \(\lceil n/2\rceil\).
\end{corollary}
\begin{proof}
Xu and Li's Theorem~16 and Corollaries~2--3
\cite{XuLi2026Fanout} turn a family satisfying either hypothesis and the
stated success bound into an exact, clean implementation of fanout on
\(n\) targets, with constant entangling depth and polynomially many
ancillas. Their circuit convention~\cite[Section~2.3]{XuLi2026Fanout}
requires the measured output to be an initially zero ancilla; appending one fresh zero qubit and a CNOT from our designated
output preserves its measurement distribution, even with arbitrary
garbage. Their entangling depth \(D\) uses at most \(2D+1\) of our layers.
Thus the reduction stays within fixed depth and polynomial total qubits.
Hadamard conjugation on the fanout data wires gives the exact parity
unitary; a zero target and its final measurement contradict
\Cref{thm:parity}. Finite exceptional input lengths do not affect this
circuit-family contradiction.
\end{proof}
There is consequently a strict separation between the Boolean families
computed with worst-case success at least \(2/3\) in our model and in the
matched model obtained by adjoining unit-cost reversible unbounded-arity
threshold gates
\[
\ket{x,b}\longmapsto
\ket{x,b\mathbin{\oplus}\mathbf 1\{|x|\ge t\}},
\qquad t\in\{0,\ldots,n\},
\]
while retaining the same depth, disjoint-support, qubit, ancilla, and
output conventions. The enlarged model contains the original one and
computes strict majority exactly with one such gate at
\(t=\lfloor n/2\rfloor+1\), whereas
Corollary~\ref{cor:symmetric-functions} excludes even worst-case success \(2/3\)
for majority in the original model.
\subsection{High average accuracy for majority}
The preceding obstruction assumes an advantage on every input. The
high-average-accuracy consequence of Gretta, Gupta, and
Joshi~\cite[Corollary~4.6]{GGJ2026} also follows directly from our
Fourier-concentration bound: majority retains a polynomial Fourier tail
at a polynomially growing cutoff.
\begin{corollary}[High-average-accuracy majority obstruction]
\label{cor:majority-average}
For every fixed \(\delta>0\), no nonuniform family \((C_n)\) in the
circuit model of \Cref{thm:parity}, with fixed depth and polynomially
many total qubits, satisfies
\[
2^{-n}\sum_{x\in\{0,1\}^n}
f_{C_n}(x)(-1)^{\operatorname{MAJ}_n(x)}\ge1-n^{-\delta}
\]
for all sufficiently large \(n\). Here \(f_{C_n}(x)\in[-1,1]\) is
the expected measured sign: the probability of output zero minus the
probability of output one. Equivalently, no such family computes strict
majority with average success at least \(1-\tfrac12 n^{-\delta}\),
where the average is over uniform inputs and the output measurement.
\end{corollary}
\begin{proof}
Suppose such a family exists, restrict to odd $n$, and put
$g_n(x)=(-1)^{\operatorname{MAJ}_n(x)}$ and
$\delta_0=\min\{\delta,1/4\}$. Since $|f_{C_n}|\le1$ and $g_n^2=1$,
the asserted correlation gives
\[
\|f_{C_n}-g_n\|_2^2
\le 2\bigl(1-\mathbb E_x f_{C_n}(x)g_n(x)\bigr)
\le 2n^{-\delta_0},
\]
where the norm uses the uniform probability measure.
We use the following finite-size majority tail estimate:
for $\varepsilon\ge n^{-1/3}$ and sufficiently large odd $n$,
\[
W_{\ge k}[g_n]>\varepsilon
\quad\text{whenever $k$ is odd and }1\le k\le\frac1{7\varepsilon^2}.
\]
This is \cite[Theorem~3.5.6, p.~50]{ODonnell2003Noise}.
Set $\varepsilon=4n^{-\delta_0}$ and let $k_n$ be the largest odd
integer at most $n^{2\delta_0}/112$. These parameters satisfy the
estimate's hypotheses for all sufficiently large odd $n$.
Parseval's identity and the triangle inequality for the Fourier
coefficients at degrees at least $k_n$ now give
\[
\sqrt{W_{\ge k_n}[f_{C_n}]}
\ge \sqrt{W_{\ge k_n}[g_n]}-\|f_{C_n}-g_n\|_2
> (2-\sqrt2)n^{-\delta_0/2}.
\]
On the other hand, $k_n\ge\lceil n^{\delta_0}\rceil$ eventually.
Applying \Cref{cor:quantum-lmn} at the latter cutoff, with
$B=\delta_0+1$, yields
$W_{\ge k_n}[f_{C_n}]\le n^{-(\delta_0+1)}$, a contradiction.
\end{proof}
This conclusion does not assert a constant average-case gap or exclude
\(1-1/\operatorname{polylog}n\) correlation.
==== END Product-projection-localization-and-the-QAC0-parity-lower-bound//sections/consequences.tex ====
==== BEGIN Product-projection-localization-and-the-QAC0-parity-lower-bound//sections/depth_reduction.tex ====
\section{Depth reduction for small-support projections}
\label{sec:depth}
We begin the proof of \Cref{thm:localization} at depth zero. We then
show that the full localization statement at depth $d-1$ controls
projections of small support at depth $d$. All large-$N$ thresholds
in this section depend only on the displayed exponents and the depth,
not on the circuits, counts, or product projections.
\begin{lemma}[Depth zero]\label{lem:base}
For every fixed $0\le s<t$, the statement $\cB_0(s,t)$ holds.
\end{lemma}
\begin{proof}
If $U\in\cU_0(N)$, then $Q=U[D=0]U^\dagger$ is a product
projection. Let $S$ be the counted subset of $M$, let
$P=[M=0]$, and put $I_*=S\cap\supp Q$. Write $\ket{v_i}$
for the reference vectors of $M$ and $\ket{w_i}$ for the projected
vectors of $Q$ on $I_*$. Set
\[
p_i=1-|\langle w_i\mid v_i\rangle|^2\qquad(i\in I_*).
\]
Every vector in the range of $P$ has the fixed tensor factor
$\bigotimes_{i\in S}\ket{v_i}$ on $S$. Its factor on the
complement of $S$ is arbitrary and need not be a product state.
Applying $Q$ contributes the squared-amplitude factor
$\prod_{i\in I_*}(1-p_i)$ on $S$, and a contraction on its
complement. If this amplitude is nonzero, the resulting normalized
factor on $S$ is
\[
\bigotimes_{i\in I_*}\ket{w_i}\otimes
\bigotimes_{i\in S\setminus I_*}\ket{v_i},
\]
with factors placed in their original qubit order. In this product
vector, the mismatch count has the law of a sum $K$ of independent
Bernoulli variables with parameters $p_i$; coordinates in
$S\setminus I_*$ never contribute. Keeping the squared-amplitude
factor, we obtain, for every $r>0$,
\begin{align*}
\norm{[M\ge r]QP}^2
&\le \prod_{i\in I_*}(1-p_i)\,\Pr(K\ge r)\\
&\le 2^{-r}\prod_{i\in I_*}(1-p_i)(1+p_i)
\le 2^{-r}.
\end{align*}
The middle inequality is Markov's inequality applied to $2^K$.
The same bound is immediate if the amplitude vanishes. Taking
$r=N^t$ gives
$\norm{[M\ge N^t]QP}\le\exp(-\tfrac12(\log 2)N^t)$,
which is at most $\exp(-N^s)$ for all sufficiently large $N$.
\end{proof}
The depth-zero estimate incorporates both the chance of producing a
mismatch and the amplitude lost under projection. We next extend the
preceding-depth hypothesis from one mismatch pattern to all patterns
below a small threshold. This is the input needed to control successive
factors in the layer expansion.
\begin{lemma}[Propagation from low counts]\label{lem:propagation}
Fix $d\ge1$ and assume $\cB_{d-1}(s,t)$ for every fixed pair
$0\le s<t$. For fixed $\alpha,\sigma\ge0$ and
$\beta>\max\{\alpha,\sigma\}$, all sufficiently large $N$
satisfy
\begin{equation}\label{eq:low-count-propagation}
\norm{[M\ge N^\beta]B[M<N^\alpha]}
\le \exp(-N^\sigma)
\end{equation}
uniformly for every count $M$ and every
$B=VP_*V^\dagger$, where $V\in\cU_{d-1}(N)$ and $P_*$
is a product projection.
\end{lemma}
\begin{proof}
Let $S$ be the counted subset of $M$. For $F\subseteq S$,
define $M^F$ by replacing the reference vector on each coordinate
of $F$ with an orthogonal unit vector, leaving the other references
unchanged. The projection $[M^F=0]$ specifies precisely the
mismatch pattern $F$ for $M$, with identity on the complement
of $S$. Hence
\[
[M<N^\alpha]=\sum_{\substack{F\subseteq S\\ |F|<N^\alpha}}
[M^F=0].
\]
These counts are diagonal in the same product basis, and pointwise
in that basis $M^F\ge M-|F|I$. Choose fixed exponents
\[
\max\{\alpha,\sigma\}<\sigma'<\beta'<\beta.
\]
For all sufficiently large $N$, uniformly over the indicated $F$,
$N^\beta-|F|\ge N^{\beta'}$. Thus
\begin{align*}
\norm{[M\ge N^\beta]B[M^F=0]}
&\le\norm{[M^F\ge N^{\beta'}]B[M^F=0]}\\
&\le\exp(-N^{\sigma'}),
\end{align*}
where the last inequality is $\cB_{d-1}(\sigma',\beta')$.
There are at most $(1+N)^{\lceil N^\alpha\rceil+1}$ patterns.
The triangle inequality therefore bounds the left side of
\eqref{eq:low-count-propagation} by
\[
\exp\!\left((\lceil N^\alpha\rceil+1)\log(1+N)
-N^{\sigma'}\right)
\le\exp(-N^\sigma)
\]
for all sufficiently large $N$, since $\sigma'>\alpha,\sigma$.
\end{proof}
We can now remove one reflection layer when the tested projection has
small support. The expansion produces three ordered factors; the
low-count estimate just proved bounds the transitions between them.
\begin{lemma}[Small-support depth reduction]\label{lem:small-support}
Fix $d\ge1$ and assume $\cB_{d-1}(s,t)$ for every fixed pair
$0\le s<t$. For fixed $u,w\ge0$ and $t>\max\{u,w\}$,
all sufficiently large $N$ satisfy
\begin{equation}\label{eq:small-support}
\norm{[M\ge N^t]UAU^\dagger[M=0]}
\le\exp(-N^w)
\end{equation}
uniformly for every $U\in\cU_d(N)$, every count $M$, and
every product projection $A$ supported on at most $N^u$ qubits.
\end{lemma}
\begin{proof}
The claim is immediate when $t>1$, so suppose $t\le1$.
Write
\[
U=VR_1L_0,\qquad
V=(L_dR_d)\cdots(L_2R_2)L_1\in\cU_{d-1}(N),
\]
where $V=L_1$ if $d=1$, and put $A'=L_0AL_0^\dagger$.
This is a product projection with the same support as $A$,
of size $k\le N^u$. Gates of $R_1$ whose supports avoid
$\supp A'$ commute with $A'$ and cancel in $R_1A'R_1$.
Because the gates in $R_1$ have disjoint supports, at most
$k$ gates remain.
Expand each remaining reflection $I-2P_*$ on both sides of
$A'$. Each term is a scalar multiple of
$P_{\mathrm{left}}A'P_{\mathrm{right}}$, where the two side
factors are product projections: within either side, the selected
gate projections have disjoint supports. The sum of the absolute
scalar coefficients is at most
\begin{equation}\label{eq:reflection-coefficients}
(1+2)^{2k}=9^k.
\end{equation}
Conjugation by $V$ turns each such term into a product
$B_1B_2B_3$, with
\[
B_1=VP_{\mathrm{left}}V^\dagger,\qquad
B_2=VA'V^\dagger,\qquad
B_3=VP_{\mathrm{right}}V^\dagger.
\]
Each $B_j$ is therefore a contraction
to which \Cref{lem:propagation} applies. No commutation between
these three factors is asserted or needed.
Choose fixed exponents
\[
\max\{w,u\}<w'<\tau_1<\tau_2<t,
\]
and set
\[
P=[M=0],\quad H=[M\ge N^t],\quad
E_1=[M<N^{\tau_1}],\quad E_2=[M<N^{\tau_2}].
\]
Insert these cutoffs between the three factors, read from right to left.
The resulting terms isolate a jump to the first cutoff, a jump from
below the first to the second, and a jump from below the second to
the final high-count sector:
\begin{align*}
HB_1B_2B_3P
={}&HB_1B_2(I-E_1)B_3P\\
&+HB_1(I-E_2)B_2E_1B_3P\\
&+HB_1E_2B_2E_1B_3P.
\end{align*}
The first term has norm at most $\exp(-N^{w'})$ by
$\cB_{d-1}(w',\tau_1)$, applied to $(I-E_1)B_3P$.
For the second term, \Cref{lem:propagation} with
$(\alpha,\sigma,\beta)=(\tau_1,w',\tau_2)$ bounds
$(I-E_2)B_2E_1$ by the same quantity. For the third, that
lemma with $(\alpha,\sigma,\beta)=(\tau_2,w',t)$ bounds
$HB_1E_2$. All other factors are contractions. Therefore
\[
\norm{HB_1B_2B_3P}\le3\exp(-N^{w'}).
\]
Summing with \eqref{eq:reflection-coefficients} gives
\[
\norm{HUAU^\dagger P}
\le3\exp\!\left((\log9)N^u-N^{w'}\right)
\le\exp(-N^w)
\]
for all sufficiently large $N$. The strict gaps $w'>u,w$
absorb the entire expansion cost uniformly for $k\le N^u$.
\end{proof}
==== END Product-projection-localization-and-the-QAC0-parity-lower-bound//sections/depth_reduction.tex ====
==== BEGIN Product-projection-localization-and-the-QAC0-parity-lower-bound//sections/introduction.tex ====
\section{Introduction}
\label{sec:introduction}
Parity is a basic test of whether a shallow circuit can combine
information from all of its inputs. For a computational-basis string
$x=(x_1,\ldots,x_n)\in\{0,1\}^n$, its value is
$\parity(x)=x_1\oplus\cdots\oplus x_n$. We study circuits generated
by arbitrary one-qubit unitaries and Toffoli gates with any number of
controls and one target. Gates in each parallel layer have pairwise
disjoint supports. The depth is the number of such layers.
The circuit starts in $\ket{x}\otimes\ket0^{\otimes(N-n)}$ on $N$
total qubits. Its answer is the result of measuring one designated output
qubit in the computational basis; the remaining registers may be
discarded in arbitrary final states, and the input need not be preserved.
For $0<\varepsilon\le1/2$, computing parity with worst-case advantage
$\varepsilon$ means giving the correct answer with probability at least
$1/2+\varepsilon$ for every $x$. The class $\QAC$ uses constant depth
and polynomially many total qubits. This also bounds the gate count:
a disjoint layer on $N$ qubits has at most $N$ nonempty gates.
The gates may depend on $n$, but not on the input string.
We use unitary circuits, with no intermediate measurements,
postselection, or primitive unbounded-fanout gate.
\begin{theorem}[Parity lower bound]
\label{thm:parity}
Fix a nonnegative integer \(d\), a real number \(c\ge1\), and
\(0<\varepsilon\le1/2\). For all sufficiently large \(n\), no circuit
of depth at most \(d\) on \(n\) input qubits and at most \(n^c\) total
qubits, using arbitrary one-qubit unitaries and unbounded-arity Toffoli
gates, computes \(\parity(x)\) with probability at least
\(1/2+\varepsilon\) for every \(x\in\{0,1\}^n\).
Gates in each layer have disjoint supports, ancillas start in \(\ket0\),
and one output qubit is measured; the other qubits may be discarded.
\end{theorem}
Taking \(\varepsilon=1/6\) gives the usual success threshold \(2/3\).
Thus \Cref{thm:parity} resolves positively the conjecture
\(\parity\notin\QAC\), with bounded error, polynomially many ancillas,
and only a measured output required.
\subsection{History and significance}
In the classical class $\mathrm{AC}^0$, circuits use unbounded-fan-in
AND and OR gates and NOT gates, with unrestricted reuse of wires.
The superpolynomial constant-depth lower bounds for parity of Furst,
Saxe, and Sipser~\cite{FurstSaxeSipser1984} and, independently,
Ajtai~\cite{Ajtai1983}, were fundamental explicit circuit lower bounds.
Yao obtained exponential bounds~\cite{Yao1985}, and H\aa stad obtained
almost optimal exponential bounds through the switching
lemma~\cite{Hastad1986}. Quantum circuits introduce a different
constraint: the supports of gates in a parallel layer are disjoint,
so a wire cannot control arbitrarily many simultaneous gates.
Moore introduced the corresponding quantum circuit classes and related
coherent parity to unbounded fanout~\cite{Moore1999}. The latter is the
unitary sending $\ket{b,y_1,\ldots,y_k}$ to
$\ket{b,y_1\oplus b,\ldots,y_k\oplus b}$. The coherent parity
transformation sends the same input to
$\ket{b\oplus\parity(y),y_1,\ldots,y_k}$, where
$y=(y_1,\ldots,y_k)$. Hadamard conjugation interchanges these two
transformations. Moore's original
formulation required ancillary qubits to return to zero; our result
also treats the more permissive measured-output model.
Green, Homer, Moore, and Pollett developed the associated quantum
counting classes and modular-gate equivalences~\cite{GreenHomerMoorePollett2002}.
The constant-depth constructions of H\o yer and \v Spalek demonstrate
how much computational power a primitive fanout operation
provides~\cite{HoyerSpalek2005}.
Early lower bounds revealed the importance of the ancillary register.
Fang, Fenner, Green, Homer, and Zhang obtained a depth lower bound of
order $\log(n/(a+1))$ for exact, clean parity computation with $a$
ancillary qubits~\cite[Corollary 4.6]{FangFennerGreenHomerZhang2006};
Bera developed a different lower-bound method in the ancilla-free
setting~\cite{Bera2011}. Pad\'e, Fenner, Grier, and Thierauf ruled out
exact clean simulation at entangling depth two~\cite{PadeFennerGrierThierauf2020}.
Fenner, Grier, Pad\'e, and Thierauf subsequently removed the final-state
cleanliness requirement for exact single-output parity at that
depth~\cite[Theorem 6.1]{FennerGrierPadeThierauf2025}.
Here the quoted depth-two results count multiqubit layers, allowing
arbitrary one-qubit layers between them; we call this
\emph{entangling depth}. Rosenthal proved lower bounds for approximate
parity unitaries and related cat-like states, and gave constant-depth
approximation constructions with superpolynomial
resources~\cite{Rosenthal2021}. Approximate unitary implementation and
computation of a single measured classical bit have different output
requirements, so the distinction matters in comparing lower bounds.
More recent work developed spectral and Fourier methods for $\QAC$.
Nadimpalli, Parham, Vasconcelos, and Yuen used the Pauli spectrum to prove
ancilla-restricted lower bounds~\cite{NPVY2024}. Anshu, Dong, Ou, and Yao
ruled out a fixed positive parity advantage with
$\widetilde O(n^{1+3^{-d}})$ ancillas at every fixed entangling depth
$d\ge1$~\cite[Corollary 4.4 and Theorem 4.6]{ADOY2025}.
Dong, Ou, and Yao increased this ancilla range to
$\widetilde O(n^{1+2^{-d}})$~\cite[Corollary 3.3]{DOY2025LinearSize}.
Here $\widetilde O$ suppresses logarithmic factors. Both results use
spectral-norm approximation of conjugated observables.
Joshi, Tal, Vasconcelos, and Wright proved exact parity lower bounds at
entangling depth three and bounded parity correlation at entangling
depth two by $\exp(-\Omega(\sqrt n))$, without a size
restriction~\cite[Theorem 1.2 and Corollary 5.9]{JTVW2026}. Kintali's September 2026 preprint reports
correlation at most $\exp(-\Omega(n))$ at entangling depth three
and an exponential multiqubit gate lower bound for exact parity at
entangling depth four~\cite[Theorems 1--2]{Kintali2026ShallowParity}.
These results retain a resource restriction or a fixed upper bound on
entangling depth. Gretta, Gupta, and Joshi established an
equivalence between the general parity lower-bound question and Fourier
concentration~\cite{GGJ2026}, and Xu and Li extended related fanout
reductions to symmetric Boolean functions~\cite{XuLi2026Fanout}. Our theorem permits every fixed depth and
every fixed polynomial bound on the total number of qubits, with
arbitrary discarded garbage and any fixed positive worst-case advantage.
\subsection{The localization argument}
Unbounded gate arity is the first obstacle to a lower bound. A single
Toffoli gate can involve every input, so the number of wires in an
output's backward light cone gives no useful restriction. Our argument
instead bounds transitions from a fixed product condition to states
with many mismatches from that condition. We keep the amplitude lost
when imposing a projection, without normalizing the resulting state.
A \emph{product projection} fixes a chosen one-qubit vector on each qubit
of a subset and acts as the identity elsewhere. Fix reference unit
vectors $v_i$ on a subset $S\subseteq\{1,\ldots,N\}$. Their
\emph{mismatch count} is
\[
M=\sum_{i\in S}(I-\proj{v_i})_i;
\]
its eigenvalue counts the factors orthogonal to their reference vectors.
Write $[M=0]$ and $[M\ge r]$ for its zero and high-count spectral
projections. Given a shallow circuit $U$ and a product projection $A$,
our structural theorem bounds
\[
\norm{[M\ge N^t]UAU^\dagger[M=0]}\le e^{-N^s}
\qquad(0\le s<t)
\]
for every fixed depth and all sufficiently large $N$. The norm is the
operator norm, and the estimate is uniform in $U,A,M$. In particular,
the uncounted register can carry an arbitrary, internally entangled state.
\Cref{thm:localization} gives the precise statement in a reflection-gate
model containing the original circuits.
There are two inductions. The outer induction removes one circuit layer.
Every allowed Toffoli is a reflection $I-2P$ about a product projection.
If $A$ fixes only $k$ qubits, at most $k$ gates in a disjoint layer meet
its support. Expanding those reflections on the two sides of $A$
expresses the conjugate as a sum of products of three projections,
each conjugated by a circuit of one smaller depth. Intermediate mismatch
cutoffs bound these ordered products. This proves localization for
projections supported on few qubits (\Cref{sec:depth}).
The reflection expansion has a cost exponential in the support size,
so it does not directly control arbitrary product projections. To handle
such a projection, write it as $[D=0]$ for a second mismatch count $D$.
A polynomial $p(D)$ of low degree expands
into projections on few qubits. The construction in \Cref{sec:polynomial}
controls both its approximation error on a low-count interval and the
sum of its coefficients weighted by the cost of this expansion.
It need not be a good approximation at large counts. The second
induction controls precisely that remaining error.
Here the order of the operators is decisive. Put $P=[M=0]$,
$Q=U[D=0]U^\dagger$, and $H=[M\ge N^t]$. Squaring the transition
norm gives $\norm{HQP}^2=\norm{HQPQH}$. Replacing only the first
$Q$ by $p(UDU^\dagger)$ leaves an error acting on $PQ$. After
conjugation by $U^\dagger$, the high-count part of that error is another
localization problem, with the two counts exchanged and a larger
mismatch threshold. We prove the universal statement at that larger
threshold first. A finite chain of thresholds ends above the maximum
possible count $N$, where localization is automatic; working backward
proves the original statement (\Cref{sec:bootstrap}). The same-depth
inverse-circuit invocation is therefore part of a finite induction.
Finally, the output-zero probability is the diagonal of the conjugated
output projection. Its parity coefficient is the average of matrix
entries between complementary Hadamard product states. Those states
differ on all $n$ input qubits. The localization theorem makes every
such entry small when $N$ is polynomial in $n$, whereas a fixed
worst-case advantage forces their average to stay positive
(\Cref{sec:parity}). This final step places no restriction on the
unmeasured registers.
The polynomial ingredients have a substantial history. The combination
of Chebyshev approximation with exact roots at exceptional integer
points follows an established approximation-and-interpolation pattern
for symmetric predicates~\cite[Section 3.1]{Sherstov2009}.
Polynomial localization and concentration for quantum states appear in
work of Kuwahara, Arad, Amico, and
Vedral~\cite{KuwaharaAradAmicoVedral2017} and Anshu and
Metger~\cite{AnshuMetger2023}. The latter also track the total norm of
local terms. For $\QAC$, the spectral-norm approximation approach of
Anshu, Dong, Ou, and Yao~\cite{ADOY2025} is a particularly relevant
predecessor. We prove the required polynomial and coefficient estimates
here. The finite inverse-circuit induction supplies the additional scale
improvement: localization holds for every fixed exponent pair
$0\le s<t$, uniformly in both counts and the entire uncounted register.
The companion article \emph{Regular trajectories, pruning and quantum
parity}~\cite[Sections 4--7]{OpenAI2026Trajectories} gives an independent proof through
state-dependent propagation, projection insertion, and pruning.
Its structural estimates concern regular trajectories; the present
operator-norm theorem is proved without a trajectory hypothesis.
Both articles prove their own polynomial estimates and their own parity
conversion, so neither parity proof invokes the other.
\subsection{Consequences}
Localization and parity also constrain symmetric computation and state
preparation. We combine them with reductions of Xu and Li~\cite{XuLi2026Fanout}
and state constructions of Gretta, Gupta, and Joshi~\cite{GGJ2026}.
In particular, strict majority,
$\operatorname{MAJ}_n(x)=\mathbf 1\{|x|>n/2\}$, where $|x|$ is the
Hamming weight, cannot be computed in this circuit model with worst-case advantage $1/(\log n)^\gamma$
for any fixed $\gamma>0$ (\Cref{cor:symmetric-functions}). This separates
the model from the corresponding one with unbounded threshold gates.
The state-preparation consequences rule out inverse-polynomial
measurement probabilities for both a string and its bitwise complement,
and sufficiently accurate preparation of uniform superpositions of
strings of a fixed Hamming weight $k$ with $n^\delta\le k\le n/2$
for fixed $\delta>0$ (\Cref{cor:state-preparation}). For a single measured output, define
its expected sign as the probability of zero minus the probability of one.
Localization implies that its Fourier coefficients have total squared
weight that decays faster than every inverse power of $n$ on input
subsets of size at least $n^\delta$, for every fixed
$0<\delta\le1$ (\Cref{cor:quantum-lmn}). Finally, majority cannot be computed
with average success at least $1-\tfrac12 n^{-\delta}$ on uniformly
random inputs, for any fixed $\delta>0$ (\Cref{cor:majority-average}).
The precise quantifiers and proofs
appear after the parity proof in \Cref{sec:consequences}.
\paragraph{Organization.}
\Cref{sec:localization} states the localization theorem and fixes the
circuit model. \Cref{sec:polynomial} proves the polynomial approximation.
\Cref{sec:depth} reduces small-support projections to the preceding
depth, and \Cref{sec:bootstrap} completes the finite scale induction.
\Cref{sec:parity} derives \Cref{thm:parity}, and
\Cref{sec:consequences} proves the consequences just described.
==== END Product-projection-localization-and-the-QAC0-parity-lower-bound//sections/introduction.tex ====
==== BEGIN Product-projection-localization-and-the-QAC0-parity-lower-bound//sections/localization.tex ====
\section{Product projections and localization}
\label{sec:localization}
The parity proof will use localization for a single output projection.
We prove the stronger uniform statement for every product projection,
because its induction exchanges the projected and counted registers.
All operators act on \(\mathcal H_N=(\mathbb C^2)^{\otimes N}\), and
\(\norm{\cdot}\) denotes the operator norm. Identities on unmentioned
qubits are implicit. Spectral projections are written in brackets;
for example, \([M\ge r]\) is the projection onto the sum of eigenspaces
of a self-adjoint operator \(M\) with eigenvalues at least \(r\).
All logarithms are natural.
A \emph{count} is an operator
\begin{equation}
\label{eq:count}
M=\sum_{i\in S}\bigl(I-\proj{v_i}\bigr)_i,
\qquad S\subseteq\{1,\ldots,N\},\quad \norm{v_i}=1.
\end{equation}
The subscript indicates the qubit on which the summand acts.
The reference vector \(v_i\in\mathbb C^2\) can be chosen separately
at each qubit. The summands commute, and the spectrum of \(M\) is
contained in \(\{0,\ldots,|S|\}\).
A \emph{product projection} is a tensor product of rank-one one-qubit
projections on a subset, with identity on the complement. Its support
is the selected subset. The empty
product is \(I\). These are precisely the projections \([M=0]\).
In particular, a product projection need not have rank one on
\(\mathcal H_N\).
We use a slightly enlarged gate set of product-state reflections, as in
\cite[Section~2 and Proposition~2.1]{Rosenthal2021}.
Let \(\cU_d(N)\) be the set of
unitaries
\begin{equation}
\label{eq:normal-form}
U=(L_dR_d)\cdots(L_1R_1)L_0,
\end{equation}
where each \(L_j\) is a product of one-qubit unitaries and each \(R_j\)
is a layer of gates \(I-2A\) with disjoint supports, with \(A\) a product
projection on the gate's qubits. Identity layers are allowed.
The class \(\cU_0(N)\) consists of products of one-qubit unitaries.
This model contains the circuits of \Cref{thm:parity}. Indeed, if
\(C\) projects onto all controls being \(1\), a Toffoli gate equals
\[
(I-C)\otimes I+C\otimes X
=I-2C\otimes\proj{-},
\qquad \ket-=\frac{\ket0-\ket1}{\sqrt2}.
\]
Grouping the local gates in each parallel step gives
\eqref{eq:normal-form} with a number of reflection layers bounded by
the original depth. Discarded qubits can be retained as idle wires
without changing any later measurement probability. Here $d$ counts
reflection layers in the enlarged model; it is at most the number of
physical layers in the original circuit. The arbitrary local layers in
\eqref{eq:normal-form} are included in this definition, rather than
charged separately to $d$.
We will also use closure under inversion at the same depth. Each
\(R_j\) is self-adjoint, since it is a product of commuting
self-adjoint reflections. Thus
\begin{equation}
\label{eq:inverse}
U^\dagger=L_0^\dagger R_1L_1^\dagger\cdots R_dL_d^\dagger
\in\cU_d(N).
\end{equation}
This is the same normal form with the layer indices reversed: the new
local layers are $L_d^\dagger,\ldots,L_0^\dagger$, in temporal order,
and the new reflection layers are $R_d,\ldots,R_1$. No factors on
overlapping supports have been commuted.
\begin{theorem}[Localization of conjugated product projections]
\label{thm:localization}
Fix a nonnegative integer \(d\) and real numbers \(0\le s<t\).
For all sufficiently large \(N\), every \(U\in\cU_d(N)\) and every
pair of counts \(M,D\) on \(\mathcal H_N\) satisfy
\begin{equation}
\label{eq:localization}
\norm{[M\ge N^t]\,U[D=0]U^\dagger[M=0]}
\le \exp(-N^s).
\end{equation}
The sufficient lower bound on \(N\) depends only on \(d,s,t\), not
on the circuit, the counted subsets, or their reference vectors.
\end{theorem}
Write \(\cB_d(s,t)\) for the assertion of
\Cref{thm:localization} at the specified \(d,s,t\), including its
uniformity. If \(t>1\), it is immediate for \(N>1\), since
\([M\ge N^t]=0\). We prove the theorem by induction on \(d\), assuming
all fixed exponent pairs at the preceding depth.
The counts \(M,D\) are allowed to be different because the proof
will exchange their roles when applying \eqref{eq:inverse}.
The next two sections supply the approximation and depth-reduction
estimates. The proof of \Cref{thm:localization} is completed in
\Cref{sec:bootstrap}.
==== END Product-projection-localization-and-the-QAC0-parity-lower-bound//sections/localization.tex ====
==== BEGIN Product-projection-localization-and-the-QAC0-parity-lower-bound//sections/parity.tex ====
\section{From localization to parity}
\label{sec:parity}
We finish by relating the output probability to transitions between
product states. All localization estimates have already been proved;
no assumption about coherent or clean computation is needed here.
For the broader Fourier-concentration setting, see~\cite{GGJ2026};
the character-orthogonality identity needed here is proved directly.
\begin{proof}[Proof of \Cref{thm:parity}]
Suppose that a circuit as in the theorem exists on \(n\) input qubits
and \(N-n\) initially zero ancillas, with \(n\le N\le n^c\).
Retain any discarded qubits as idle wires and write \(W\) for the
resulting unitary. By \Cref{sec:localization}, \(W\in\cU_d(N)\)
after padding with identity layers.
Let \(O\) project the output qubit onto \(\ket0\), and put
\[
B=W^\dagger OW,\qquad
p_0(x)=\bra{x,0}B\ket{x,0}.
\]
The Born rule identifies \(p_0(x)\) with the probability of output
zero, irrespective of the final states of the other qubits.
Here and below the last zero denotes all initially zero ancillas.
For \(h\in\{0,1\}^n\), define
\[
\ket{\xi_h}
=\bigotimes_{j=1}^n
\frac{\ket0+(-1)^{h_j}\ket1}{\sqrt2},
\qquad
\bar h=(1-h_1,\ldots,1-h_n).
\]
Let \(M_h\) be the count on the input qubits whose reference vectors
are the factors of \(\xi_h\). The vectors
\(\ket{\xi_h,0}\) and \(\ket{\xi_{\bar h},0}\) have exact counts
zero and \(n\), respectively.
Choose fixed \(0<s<t<1/c\). For all sufficiently large \(n\),
\(N^t\le n^{ct}<n\). Since \(O\) is a product projection and
\(W^\dagger\in\cU_d(N)\), \Cref{thm:localization} gives
\begin{equation}
\label{eq:complementary-entry}
\left|\bra{\xi_{\bar h},0}B\ket{\xi_h,0}\right|
\le e^{-N^s}
\qquad\text{for every }h.
\end{equation}
Its uniformity in the count makes the same lower bound on \(N\)
valid for all \(h\).
Averaging these complementary matrix entries gives the parity Fourier
coefficient of $p_0$, namely $2^{-n}\sum_x(-1)^{|x|}p_0(x)$,
where $|x|=\sum_jx_j$. To see this, note that
\(\langle x\mid\xi_h\rangle=2^{-n/2}(-1)^{h\cdot x}\), where
the dot product is taken modulo two. Also,
\((-1)^{\bar h\cdot x}=(-1)^{|x|+h\cdot x}\).
Character orthogonality therefore gives
\begin{align}
\E_h\bra{\xi_{\bar h},0}B\ket{\xi_h,0}
&=2^{-n}\sum_{x,y}(-1)^{|x|}
\E_h(-1)^{h\cdot(x+y)}\bra{x,0}B\ket{y,0}\notag\\
&=2^{-n}\sum_x(-1)^{|x|}p_0(x).
\label{eq:parity-average}
\end{align}
The addition in \(x+y\) in the character is modulo two.
For even \(x\), the success guarantee gives
\(p_0(x)\ge1/2+\varepsilon\); for odd \(x\), it gives
\(p_0(x)\le1/2-\varepsilon\).
The even and odd classes have equal size, so the final expression
in \eqref{eq:parity-average} is at least \(\varepsilon\).
But \eqref{eq:complementary-entry} bounds its absolute value by
\(e^{-N^s}\), which tends to zero because \(N\ge n\).
This contradiction proves the theorem.
\end{proof}
The role of a polynomial qubit bound is solely the choice of
\(0<s<t<1/c\). The localization theorem itself is uniform on
\(N\) qubits and does not assume any relation between \(N\) and an
input length. The proof gives no claim of the same lower bound
when the ancillary register is allowed to be superpolynomial.
==== END Product-projection-localization-and-the-QAC0-parity-lower-bound//sections/parity.tex ====
==== BEGIN Product-projection-localization-and-the-QAC0-parity-lower-bound//sections/polynomial.tex ====
\section{A polynomial approximation with controlled coefficients}
\label{sec:polynomial}
We will approximate the zero spectral projection of a count by a polynomial.
Small approximation error alone is not enough: expanding the $k$th power of a
count produces up to $N^k$ product projections. For a polynomial
$f(x)=\sum_k c_kx^k$, define its weighted coefficient norm by
\[
W_N(f)=\sum_k|c_k|N^k.
\]
This bounds the sum of absolute coefficients in the later operator expansion.
The construction uses Chebyshev approximation together with exact roots
at the first integer points, a classical approximation-and-interpolation
pattern; see Sherstov~\cite[Section 3.1 and Lemma 3.9]{Sherstov2009}.
Controlling this sum is in the same general spirit as tracking
the total local norm of Anshu and Metger~\cite[Definition 2.3 and
Lemma 4.5]{AnshuMetger2023}. We supply the exact bounds needed here,
including intervals whose endpoint exceeds the maximum count $N$.
\begin{lemma}\label{lem:polynomial}
Fix real numbers $0<a<b$ and $u>(a+b)/2$. For every sufficiently large integer
$N$, there is a real polynomial $p$ such that
\begin{equation}\label{eq:polynomial-bounds}
\deg p\le N^u,
\qquad W_N(p)\le \exp(N^u),
\qquad p(0)=1,
\end{equation}
and
\begin{equation}\label{eq:polynomial-decay}
|p(x)|\le \exp(-N^a)
\qquad\text{for every integer }1\le x\le \lceil N^b\rceil.
\end{equation}
The threshold for $N$ depends only on $a,b,u$. No restriction $b\le1$ is
imposed.
\end{lemma}
\begin{proof}
Put
\[
r=\lceil N^a\rceil,
\qquad m=\lceil N^b\rceil,
\qquad \ell=\left\lceil 2\sqrt{mr}\log m\right\rceil.
\]
Since $a<b$, we have $m\ge2r$ once $N$ is sufficiently large. Define the
root polynomial
\[
F(x)=\prod_{j=1}^{r}\left(1-\frac{x}{j}\right).
\]
It is one at zero and vanishes at the first $r$ positive integers.
On $[r,m]$ we only use the crude bound $|F(x)|\le m^r$.
To overcome this growth, we multiply it by a
polynomial that is one at zero and small throughout $[r,m]$.
To construct that factor, define the
Chebyshev polynomials by
\[
T_0(x)=1,\qquad T_1(x)=x,\qquad
T_{j+1}(x)=2xT_j(x)-T_{j-1}(x).
\]
Induction in this recurrence, using the corresponding addition identities,
gives
\[
T_j(\cos\theta)=\cos(j\theta),
\qquad
T_j\!\left(\frac{h+h^{-1}}2\right)
=\frac{h^j+h^{-j}}2\quad(h>0).
\]
In particular, $|T_j(x)|\le1$ on $[-1,1]$. Set
\begin{equation}\label{eq:polynomial-construction}
p(x)=F(x)
\frac{T_\ell\!\left((m+r-2x)/(m-r)\right)}
{T_\ell\!\left((m+r)/(m-r)\right)}.
\end{equation}
The denominator is positive, and $p(0)=1$.
To bound the denominator, write $q=\sqrt{r/m}$ and
$h=(1+q)/(1-q)$. Then $0<q<1$ and
\[
\frac{h+h^{-1}}2=\frac{m+r}{m-r},
\qquad
\log h=2\int_0^q\frac{dy}{1-y^2}\ge2q.
\]
Consequently
\[
T_\ell\!\left(\frac{m+r}{m-r}\right)
\ge \frac12\exp\!\left(2\ell\sqrt{r/m}\right)
\ge \frac12 m^{4r}.
\]
This denominator is also at least $1$, by
$(h^\ell+h^{-\ell})/2\ge1$.
The polynomial vanishes at the integers $1,\ldots,r$. For $r\le x\le m$,
the affine Chebyshev argument in \Cref{eq:polynomial-construction} lies in
$[-1,1]$, and each factor $|1-x/j|$ is at most $m$. Thus
\[
|p(x)|\le 2m^{-3r}\qquad(r\le x\le m).
\]
Since $r\ge N^a$ and $\log m\longrightarrow\infty$, this is at most
$\exp(-N^a)$ for all sufficiently large $N$. Together with the exact roots,
this proves \Cref{eq:polynomial-decay}. No estimate is needed at noninteger
points between $0$ and $r$.
It remains to bound the degree and the coefficient cost.
The coefficient convolution formula gives
$W_N(fg)\le W_N(f)W_N(g)$. Hence the root product has weighted norm at most
\[
\prod_{j=1}^r(1+N/j)\le(1+N)^r.
\]
For $z(x)=(m+r-2x)/(m-r)$, we have
\[
\beta:=W_N(z)=\frac{m+r+2N}{m-r}\le3+2N.
\]
Here $m\ge2r$ controls the constant coefficient, while the positive integer
$m-r\ge1$ controls the linear coefficient. This bound remains valid when
$m>N$.
Let $A=2\beta+1$. The Chebyshev recurrence and induction give
$W_N(T_j(z))\le A^j$: the inductive step uses
\[
2\beta A^j+A^{j-1}\le A^{j+1},
\qquad A^2-2\beta A-1=2\beta\ge0.
\]
The initial cases follow from $W_N(T_0(z))=1$ and
$W_N(T_1(z))=\beta\le A$. Since $A\le7+4N\le11(1+N)$ and the denominator
in \Cref{eq:polynomial-construction} is at least $1$, we obtain
\[
W_N(p)\le(1+N)^r\bigl(11(1+N)\bigr)^\ell,
\qquad \deg p\le r+\ell.
\]
Finally, with $\gamma=(a+b)/2>a$, the rounded definitions imply
\[
r=O(N^a),\qquad
\ell=O(N^\gamma\log N),\qquad
\log W_N(p)=O\!\left(N^\gamma(\log N)^2\right).
\]
Both $r+\ell$ and $\log W_N(p)$ are $o(N^u)$ because $u>\gamma$.
All constants depend only on the fixed exponents, proving
\Cref{eq:polynomial-bounds} with the asserted uniform threshold.
\end{proof}
==== END Product-projection-localization-and-the-QAC0-parity-lower-bound//sections/polynomial.tex ====