Quantum parity: localization and regular trajectories

Source and verification

This article explains family 274 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Shallow quantum circuits and parity

The parity of a bit string is $\mathrm{PARITY}(x)=x_1\oplus \cdots \oplus x_n$. Every input bit matters, but this alone does not prove that a quantum circuit needs substantial depth: one unbounded-arity gate can touch every input at once.

The model in this family has $N$ qubits, with Hilbert space $({\mathbb{C}}^2{)}^{\otimes N}$. It starts in $|x⟩|0{⟩}^{\otimes (N-n)}$. Allowed gates are arbitrary one-qubit unitaries and generalized Toffoli gates, which flip one target bit exactly when every control bit is one. Each layer has disjoint gate supports. At the end, one designated qubit is measured in the computational basis. The other qubits may contain arbitrary garbage; neither inputs nor ancillas need to be restored.

The class ${\mathsf{QAC}}^0$ fixes the depth and allows polynomially many total qubits. Gates may depend on the input length, including arbitrary complex entries, but not on the input string. There are no intermediate measurements, postselection operations, or primitive gates that copy one control into arbitrarily many targets simultaneously. Disjointness implies at most $dN$ nonempty gates in depth $d$.

Measured-output parity lower bound, as stated in the manuscripts

Fix a depth, a polynomial bound on total qubits, and $0<\epsilon \le 1/2$. For every sufficiently large input length, every allowed circuit has an input on which its parity success probability is strictly less than $1/2+\epsilon$.

The two manuscripts claim this conclusion by different structural arguments. (OpenAI, 2026) (OpenAI, 2026b) Taking $\epsilon =1/6$ gives the usual $2/3$ threshold. The result concerns every fixed positive worst-case advantage; it does not assert the same lower bound with arbitrarily many ancillas or growing depth.

🏷️ Product projections and mismatch counts

A product projection fixes a unit vector $v_j$ on each site of a subset $S$ and acts as identity elsewhere. It need not have rank one on the whole register. Its mismatch count is

$$M=\sum _{j\in S}(I-|v_j⟩⟨v_j|{)}_j.$$

The summands commute. In the product basis with local vectors $v_j,v_j^{\perp }$, an eigenvalue of $M$ counts the mismatching sites. Write $[M\ge r]$ for the corresponding spectral projection and $[M=0]$ for the product projection itself.

A Toffoli is a product-state reflection $I-2P$: take the projection onto $|1⟩$ on all controls and $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$ on its target. On the all-one control subspace, $I-2|-⟩⟨-|=X$, the bit flip. The analysis permits arbitrary product-state reflections, with disjoint supports within each reflection layer and arbitrary local-unitary layers between them. This enlarged model contains the original circuits and is closed under inversion at the same reflection depth.

Uniform product-projection localization

Fix reflection depth $d$ and exponents $0\le s<t$. Put $Q=U[D=0]U^{\ast }$. For all sufficiently large $N$, uniformly over circuits $U$ of that depth and mismatch counts $M,D$,

$$\begin{array}{c}\Vert [M\ge N^t]Q[M=0]\Vert \\ \le e^{-N^s}.\end{array}$$

The norm is the operator norm. Thus the uncounted register may be arbitrarily entangled internally. The threshold depends on $d,s,t$, not on the vectors specifying the tests. This is the first manuscript’s central structural claim. (OpenAI, 2026a) All projections used in the proof act without renormalizing vectors; they are analytic devices, not additional allowed circuit operations.

🏷️ The amplitude retained by a projection

The depth-zero case already explains an important mechanism. Local unitaries turn the tested projection into another product projection $Q$. On sites shared by $Q$ and the counted set, let $p_j=1-|⟨w_j,v_j⟩{|}^2$, where $w_j$ is the vector fixed by $Q$.

Applying $Q$ to the zero-mismatch sector loses squared amplitude ${\prod }_j(1-p_j)$. Conditional on that product component, the mismatch count has the law of $K$, a sum of independent Bernoulli variables with parameters $p_j$. Consequently,

$$\begin{array}{rl}& \Vert [M\ge r]Q[M=0]{\Vert }^2\\ & \le \prod _j(1-p_j)\mathrm{Pr}(K\ge r)\\ & \le 2^{-r}\prod _j(1-p_j)(1+p_j)\\ & \le 2^{-r}.\end{array}$$

The middle inequality is Markov applied to $2^K$. Normalizing immediately after projection would discard the factor that makes the estimate work. With $r=N^t$, the resulting exponential decay beats $e^{-N^s}$ whenever $s<t$.

🏷️ Removing a layer and controlling polynomial cost

Suppose the full localization theorem is known at depth $d-1$. If a product projection $A$ involves only $k$ qubits, at most $k$ disjoint reflections in the first layer touch it. The others commute past it and cancel. Expanding each remaining reflection on both sides yields terms of the form $P_{L}A{P}_R$, with total absolute coefficient sum at most $9^k$.

After conjugation by the remaining depth-$d-1$ circuit, each term is an ordered product of three conjugated product projections. They need not commute. Insert successively larger mismatch cutoffs between the factors. A transition to the final high-count sector must cross one cutoff; preceding-depth localization bounds that crossing. To start from a low-count sector rather than count zero, decompose it into its possible mismatch patterns. There are at most $\exp (O(N^{\alpha }\log N))$ patterns below $N^{\alpha }$, absorbed by a decay exponent strictly larger than $\alpha$. This proves the small-support version at depth $d$, including the $9^k$ expansion cost.

To reach projections of arbitrary support, write $A=[D=0]$ and approximate it by a polynomial $p(D)={\sum }_k{c}_k{D}^k$. Degree alone is insufficient: expanding $D^k$ produces up to $N^k$ product projections. The required coefficient budget is $W_N(p)={\sum }_k|c_k|N^k$.

For fixed $0<a<b$ and $u>(a+b)/2$, the manuscript constructs a polynomial with

$$\begin{array}{c}p(0)=1,\mathrm{deg}p\le N^u,\\ W_N(p)\le e^{N^u},\\ |p(j)|\le e^{-N^a}\\ (1\le j\le \lceil N^b\rceil ).\end{array}$$

The construction multiplies exact roots at the first $r=\lceil N^a\rceil$ positive integers by a normalized Chebyshev polynomial, suppressing the remaining interval through $m=\lceil N^b\rceil$. Its degree is $O(\sqrt{mr}\log m)$, while its logarithmic coefficient cost is $O(N^{(a+b)/2}(\log N{)}^2)$. Both fit below $N^u$. Values between zero and the first positive integer are irrelevant because a mismatch count has integer spectrum.

🏷️ A finite induction using the inverse circuit

The polynomial can be large above its approximation interval. The manuscript controls that part by a finite scale induction, rather than assuming global approximation.

Set $P=[M=0]$, $H=[M\ge N^t]$, $C=UD{U}^{\ast }$ and $Q=[C=0]$. Squaring the desired norm and replacing only the leftmost $Q$ gives

$$\begin{array}{rl}\Vert HQP{\Vert }^2& =\Vert HQPQH\Vert \\ & \le \Vert Hp(C)P\Vert \\ & +\Vert (Q-p(C))PQ\Vert .\end{array}$$

The small-support estimate controls the first term after polynomial expansion. Split the second at $C=N^b$. Below the split, the approximation error is $e^{-N^a}$. Above it, put $R=U^{\ast }[M=0]U$; the factor that remains is

$$\begin{array}{rl}& \Vert [C\ge N^b]PQ\Vert \\ & =\Vert [D\ge N^b]R[D=0]\Vert .\end{array}$$

This is another instance of localization, with the counts exchanged and the circuit inverted. It can be used once localization at exponent pair $(t,b)$ has already been proved. For $s<t<b<2t-s$, choose $s<a<2t-b$ and $(a+b)/2<u<w<t$. The resulting estimate is

$$\begin{array}{rl}\Vert HQP{\Vert }^2\le & e^{N^u-N^w}+e^{-N^a}\\ & +(1+e^{N^u})e^{-N^t}.\end{array}$$

The strict gaps make this at most $e^{-2N^s}$ eventually. Operator order is essential: $P$ was never commuted through $Q$ or $C$.

To supply the stronger-scale premise without circularity, start from $s_0=s,t_0=t\le 1$, put $g=t-s$ and $\eta =g^2/100$, and define $s_{i+1}=t_i$, $t_{i+1}=2t_i-s_i-3\eta$. For at least $\lceil 2/g\rceil$ steps the gaps stay above $g/2$, so some $t_J>1$. At that endpoint the high-count projection is zero, since $M\le NI$. Work backward along this finite chain. Each backward implication also uses the already proved depth-$d-1$ theorem. Only finitely many exponent tuples occur for each target pair, so uniform thresholds are preserved.

🏷️ From localization to a parity contradiction

Let $W$ be the circuit, $O$ the output-zero projection, and $B=W^{\ast }OW$. Its diagonal $p_0(x)=⟨x,0|B|x,0⟩$ is the measured probability, regardless of final garbage.

For $h\in \{0,1{\}}^n$, define the Hadamard product vector ${\xi }_h={⨂}_j\frac{|0⟩+(-1{)}^{h_j}|1⟩}{\sqrt{2}}$. The vectors ${\xi }_h$ and ${\xi }_{\bar{h}}$ differ in all $n$ local factors. If $N\le n^c$, choose $0<s<t<1/c$; then $N^t<n$ eventually. Localization bounds every complementary entry of $B$ by $e^{-N^s}$.

Expanding in the computational basis and averaging over $h$ gives the exact character identity

$$\begin{array}{c}{\mathbb{E}}_h⟨{\xi }_{\bar{h}},0|B|{\xi }_h,0⟩\\ =2^{-n}\sum _x(-1{)}^{|x|}{p}_0(x).\end{array}$$

Indeed ${\mathbb{E}}_h(-1{)}^{h\cdot (x+y)}$ is zero unless $x=y$. Correctness with advantage $\epsilon$ makes the right side at least $\epsilon$: output zero has probability at least $1/2+\epsilon$ on even strings and at most $1/2-\epsilon$ on odd strings. The complementary-entry bound makes its absolute value tend to zero. This proves the claimed contradiction without requiring a coherent parity output. (OpenAI, 2026a)

🏷️ Regular trajectories and state-dependent pruning

The companion proves a different structural route. (OpenAI, 2026b) An operator has degree at most $\ell$ if it is a sum of terms each supported on at most $\ell$ qubits. Such an operator cannot change a product mismatch count by more than $\ell$.

A trajectory through a bounded number of layers on $m$ qubits is regular if, at every reflection layer, every collection $S$ of at most $m^b$ gates has tail amplitude at most $e^{-m^p}$ above mismatch count $m^h$, for every fixed $0\le b<h<1$ and $0<p<h$, eventually along the circuit sequence. The count combines the local factors specified by those gates. This is an asymptotic property, uniform over the chosen collection for each fixed exponent triple; it does not require a common threshold for all real triples.

Low-degree propagation approximates a transported perturbation along a regular reference trajectory, with an arbitrarily small fixed loss in its degree exponent. It is a state-dependent vector estimate, not an operator-norm approximation of the entire circuit. Two polynomial filters then transport tail estimates between two regular trajectories joined by a product projection. A backward induction over suffixes shows that inserting a product projection preserves regularity. Filtered vectors themselves are not assumed regular.

For a regular trajectory from a product input ${\psi }_0$, an important consequence at its endpoint $\psi$ is

$$\begin{array}{c}\Vert P_B\psi {\Vert }^2\Vert [H_B\ge m^h]\psi \Vert \le e^{-m^p}\\ (0<p<h<1).\end{array}$$

Here $B$ is any product test and $H_B$ its count. The multiplier is the projection probability, not its square root: projecting, reversing to the rank-one product input, and returning produces $\Vert P_B\psi {\Vert }^2\psi$ exactly.

The pruning rule now has no exponent choices. At each reflection layer, compute the exact state $\psi$ of the already pruned prefix and retain precisely gates with $q_g=\Vert P_g\psi {\Vert }^2\ge m^{-6}$. Leave one-qubit layers intact. For a deleted gate, $\Vert (I-2P_g-I)\psi \Vert <2m^{-3}$. At most $m$ gates occur in a layer; disjointness keeps this bound valid as other layer gates act. Telescoping over $t$ analytic layers gives

$$\Vert U{\psi }_0-W{\psi }_0\Vert \le 2t{m}^{-2}.$$

Why is the retained layer regular? The probability-tail estimate first bounds each retained gate’s mean mismatch by $m^{ϵ}$, for any fixed positive $ϵ$, eventually. A collection of at most $m^b$ gates therefore has mean at most $m^{b+ϵ}$. Markov places at least half the mass on patterns of weight at most $2m^{b+ϵ}$. Counting these patterns finds one of probability at least $e^{-m^{b+2ϵ}}$. Recenter the product test at that pattern and apply the probability-tail estimate again, with a decay exponent larger than $b+2ϵ$. Its tail dominates the reciprocal pattern probability. The outcomes need not be independent. This proves regularity from the already regular prefix, avoiding any assumption about the proposed next layer.

The rule is an existence construction depending on an exact state; no efficient classical algorithm for computing the deletion decisions is claimed.

🏷️ Reference qubits retain the classical input labels

Pruning approximates one coherent input state, so it need not preserve worst-case success on individual strings. The companion instead attaches $n$ reference qubits and applies a disjoint CNOT copying layer to the input $|+{⟩}^{\otimes n}$ and zero references. The coherent output is $2^{-n/2}{\sum }_{x}U|x,0⟩|x{⟩}_R$.

Let $P_B$ select answer one and $Z_R$ multiply by $(-1{)}^{|x|}$ on the references. Correctness forces its expectation to be at most $-\epsilon$. Pruning changes that expectation by at most $4t{m}^{-2}$. Every copying gate survives, since its initial projection probability is $1/4$; later gates never touch the references.

For the pruned circuit $W$, conjugating $Z_R$ back through the copying layer gives $Z_I{Z}_R$. This turns all $n$ input $|+⟩$ factors into $|-⟩$, while keeping the other starting factors unchanged. The signed expectation is consequently an inner product of $W^{\ast }{P}_{B}W{\psi }_0$ with a vector having exactly $n$ mismatches from ${\psi }_0$. The regular-trajectory product-input tail bounds it by $e^{-m^p}$ when $m$ is polynomial in $n$ and the threshold exponent is sufficiently small. This contradicts the surviving negative expectation. (OpenAI, 2026b)

🏷️ Fourier and state-preparation consequences

The first manuscript also derives a scalar-output Fourier statement. For the expected measured sign $f(x)\in [-1,1]$, define $\hat{f}(S)={\mathbb{E}}_{x}f(x)(-1{)}^{{\sum }_{j\in S}{x}_j}$. Jensen and Bessel convert the same complementary-entry calculation into a bound on the absolute squared Fourier tail. For fixed depth, polynomial total-qubit bound, and $\delta >0$, the sum ${\sum }_{|S|\ge n^{\delta }}|\hat{f}(S){|}^2$ decays faster than every inverse power of $n$. No division by total Fourier mass is involved.

For a retained state prepared from all-zero inputs, with computational-basis probabilities $p_y$, define its felinity as $\mathcal{F}(\rho )=2{\sum }_y{p}_y{p}_{\bar{y}}$. Localization bounds $\sqrt{p_y{p}_{\bar{y}}}$ uniformly by a stretched exponential. Cauchy–Schwarz gives ${\sum }_y\sqrt{p_y{p}_{\bar{y}}}\le 1$, avoiding a factor $2^n$, and hence superpolynomial decay of felinity for shallow preparations whose total qubit count is polynomial in the retained target size $n$. This quantity measures complementary measurement probabilities; it is not an entanglement measure.

The manuscripts further state a Dicke-state obstruction: for fixed $0<\delta <1$ and $n^{\delta }\le k\le n/2$, the half-trace-norm distance from the normalized equal superposition of weight-$k$ strings exceeds $1/(80k)$ eventually. The first manuscript explains a block product-test construction that would otherwise turn a close approximation into inverse-polynomial felinity. Majority and broader symmetric-function consequences use additional cited reductions; they do not follow merely by replacing the parity sign in the elementary identity above. (OpenAI, 2026a) (OpenAI, 2026b)

🏷️ Key steps and proof outlines

Exact roots and a large denominator pay for polynomial growth

The localization paper’s filter has an explicit form. For positive integers $r,m$ with $m\ge 2r$, set

$$F(x)=\prod _{j=1}^r(1-x/j),$$

and let $T_{\ell }$ be the Chebyshev polynomial, characterized by $T_{\ell }(\cos \theta )=\cos (\ell \theta )$. Define

$$p(x)=F(x)\frac{T_{\ell }((m+r-2x)/(m-r))}{T_{\ell }((m+r)/(m-r))},\ell =\lceil 2\sqrt{mr}\log m\rceil .$$

Then $p(0)=1$, and $p$ vanishes at the first $r$ positive integers.

On $[r,m]$, the numerator’s Chebyshev factor has absolute value at most one, while $|F(x)|\le m^r$. Put $q=\sqrt{r/m}$ and $h=(1+q)/(1-q)$. The denominator equals $(h^{\ell }+h^{-\ell })/2$; since $\log h\ge 2q$, it is at least $m^{4r}/2$. Thus

$$|p(x)|\le 2m^{-3r}(r\le x\le m).$$

The two parts of the construction have different jobs: the roots handle the small positive integers exactly, and the denominator suppresses the whole remaining interval.

Coefficient growth is checked separately. The weighted norm $W_N$ is submultiplicative. For the affine Chebyshev argument $z(x)$, write $\beta =W_N(z)\le 3+2N$. The recurrence $T_{j+1}=2z{T}_j-T_{j-1}$ gives

$$W_N(T_j(z))\le (2\beta +1{)}^j.$$

Together with $W_N(F)\le (1+N{)}^r$, this bounds the total expansion cost by

$$W_N(p)\le (1+N{)}^r(11(1+N){)}^{\ell }.$$

Taking $r\asymp N^a$, $m\asymp N^b$ produces the degree and logarithmic coefficient costs stated above. Tracking this second bound is indispensable when the polynomial is expanded into many local operator terms (OpenAI, 2026a).

Two filters are propagated along two different reference trajectories

For the companion’s transport lemma, let

$$\chi =V^{\ast }{P}_{B}V\psi$$

and assume that the trajectories of both unfiltered vectors $\psi$ and $\chi$ are regular. A nonnegative tail filter $T=T(H_A)$ detects a target band of initial mismatches while strongly suppressing low counts. A previously established bound above a larger threshold pays for its potentially large global norm and ensures $\Vert T\chi \Vert \le 2$.

Propagate $T$ along the regular reference trajectory of $\chi$. Low-degree propagation gives $VT\chi \approx EV\chi$, with controlled degree for $E$. Since $V\chi =P_{B}V\psi$ has zero final mismatch, the degree bound confines $EV\chi$ to a controlled final-count range. A zero filter $D=D(H_B)$ can therefore approximate $P_B$ accurately on $VT\chi$, even if $D$ is large elsewhere.

The scalar quantity

$$a_m=⟨\chi ,T\chi ⟩=⟨VT\chi ,P_{B}V\psi ⟩$$

is nonnegative. Move the self-adjoint approximation error $P_B-D$ to the first argument, where its range has just been controlled. Then propagate $D$ backward along the regular reference trajectory of $\psi$:

$$V^{\ast }DV\psi \approx G\psi .$$

Thus $a_m\approx ⟨T\chi ,G\psi ⟩$. The latter is small because $T$ suppresses low counts and the low-degree operator $G$ cannot move the small input high-count tail too far. Positivity of $T$ converts this scalar bound into the desired tail estimate for $\chi$.

The induction starts above the maximum possible mismatch count $m$, where the tail is exactly zero, and descends through finitely many thresholds. At no stage is either filtered vector assumed to have a regular trajectory. The two separate reference trajectories, the side on which each approximation is applied, and positivity of the tail filter are the key safeguards making the later projection-insertion and pruning arguments valid (OpenAI, 2026b).

🏷️ Connections and review scope

Hadamard conjugation interchanges coherent fanout and coherent parity. Thus an exact constant-depth polynomial-resource fanout implementation would contradict the measured-output theorem after adding two local layers and a zero target. This deduction retains the distinction between a primitive fanout gate and a circuit built from the permitted gates.

Bosonic entropy and communication studies information transmitted through a noisy channel. Here the restriction is instead computational depth and the disjoint support of simultaneous gates. Both families allow internal quantum correlations and make the operational output requirement part of the theorem.

The selected-source review follows the first manuscript’s localization, finite scale induction and parity argument, and the companion’s regularity, projection-insertion, pruning and reference-register closure. The companion’s full filter/transport proof and external reduction theorems remain inputs to this exposition. Finite circuit simulations would not verify a uniform asymptotic lower bound.

🏷️ Manuscripts and verification scope

• Product-projection localization and the QAC0 parity lower bound — pinned manuscript and companion source.
• Regular trajectories, pruning and quantum parity — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The scope page selects the measured-output parity consequence at every fixed depth and polynomial qubit bound, with zero-initialized ancillas and any fixed positive advantage, and includes product-projection localization. It explicitly does not treat regular-trajectory propagation and pruning as separate formalized statements. The additional Fourier, state-preparation and symmetric-function consequences are not inferred to share that coverage. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026a. Product-projection localization and the QAC⁰ parity lower bound.

🐻  OpenAI 2026b. Regular trajectories, pruning and quantum parity.