Bounded-error parity query lower bound

Put $z_i=(-1{)}^{x_i}\in \{-1,1\}$. On a basis query address $i$, the matrix entries of the XOR target flip are either $(1+z_i)\mathrm{/}2$ or $(1-z_i)\mathrm{/}2$; the input address and all other bits are unchanged. Thus one oracle call raises the degree of every amplitude polynomial in $z_1,\dots ,z_n$ by at most one. The inter-query unitaries are input-independent by [F2] and take fixed linear combinations of amplitudes. Induction over the $q$ queries shows each final amplitude is a multilinear polynomial of degree at most $q$, replacing any $z_i^2$ by $1$ without increasing degree.

The signed output expectation $p(z)=\mathrm{Pr}[y=0]-\mathrm{Pr}[y=1]$ is a sum of squared moduli of final amplitudes with fixed signs, so it is a real multilinear polynomial of degree at most $2q$. If $\chi (z)={\prod }_{i=1}^n{z}_i=(-1{)}^{\mathrm{parity}(x)}$, the error bound gives $\chi (z)p(z)\ge 1\mathrm{/}3$ pointwise. Therefore the uniform average of $\chi p$ is positive.

If $2q<n$, every monomial of $p$ is $z_S={\prod }_{i\in S}{z}_i$ for a proper subset $S⊊[n]$. Under independent uniform signs, $\mathbb{E}[\chi z_S]=\mathbb{E}[{\prod }_{i\mathrm{\notin }S}{z}_i]=0$, since at least one independent sign appears to the first power and has mean zero. Linearity gives $\mathbb{E}[\chi p]=0$, contradicting step 2.1. Hence $2q\ge n$.