Polynomial Method and Approximate Degree

By [F1], $p$ and each polynomial $r$ below are finite real polynomials; [F2] and [F9] make $p,p^{\mathrm{\prime }}$ continuous and attain their extrema on $[-1,1]$. For any such $r$, $S_r(\theta ):=\sin \theta r(\cos \theta )$ is continuous by [F6], [F9], and [F10], and is $2\pi$-periodic by [F15]; hence [F9] gives a maximum of $\mathrm{\mid }{S}_r\mathrm{\mid }$ on $[0,2\pi ]$. If $d=0$ or $p=0$, then $p^{\mathrm{\prime }}=0$ and $h=0$; assume $d\ge 1$. For $j=1,\dots ,d$, put ${\theta }_j=(2j-1)\pi \mathrm{/}(2d)$ and $x_j=\cos {\theta }_j$. By [F4], $T_d(x_j)=\cos (d{\theta }_j)=0$. Monotonicity and reflection in [F5] show $x_1>\cdots >x_d$ in $(-1,1)$ and $x_d=-x_1$. Also [F5] gives $\sin {\theta }_j>0$. Since $d{\theta }_j=(j-1)\pi +\pi \mathrm{/}2$, repeated use of the shift-by-$\pi$ identity in [F5], with finite induction [F13], gives $\sin (d{\theta }_j)=(-1{)}^{j-1}$. The chain rule [F6] applied to [F4] now gives $T_d^{\mathrm{\prime }}(x_j)=d\sin (d{\theta }_j)\mathrm{/}\sin {\theta }_j=d(-1{)}^{j-1}\mathrm{/}\sin {\theta }_j\mathrm{\ne }0$.

Fix any polynomial $r$ supported in degrees at most $d-1$. For $x\in [-x_1,x_1]$, choose $\theta \in [0,\pi ]$ with $x=\cos \theta$. Monotonicity and reflection in [F5] imply $\pi \mathrm{/}(2d)\le \theta \le \pi -\pi \mathrm{/}(2d)$, so $\sin \theta \ge \sin (\pi \mathrm{/}(2d))$. For every positive integer $n$, $\mathrm{\mid }\sin (n\varphi )\mathrm{\mid }\le n\mathrm{\mid }\sin \varphi \mathrm{\mid }$: equality holds for $n=1$; the sine addition formula [F8] and $\mathrm{\mid }\sin \mathrm{\mid },\mathrm{\mid }\cos \mathrm{\mid }\le 1$ from [F5] give $\mathrm{\mid }\sin ((n+1)\varphi )\mathrm{\mid }\le \mathrm{\mid }\sin (n\varphi )\mathrm{\mid }+\mathrm{\mid }\sin \varphi \mathrm{\mid }$, so induction [F13] proves the claim. At $\varphi =\pi \mathrm{/}(2d)$ this yields $1=\mathrm{\mid }\sin (d\varphi )\mathrm{\mid }\le d\sin \varphi$, hence $\sin (\pi \mathrm{/}(2d))\ge 1\mathrm{/}d$. Therefore $\mathrm{\mid }r(x)\mathrm{\mid }\le d\mathrm{\mid }\sin \theta r(\cos \theta )\mathrm{\mid }\le d{\max }_{\eta \in [0,2\pi ]}\mathrm{\mid }{S}_r(\eta )\mathrm{\mid }$ throughout this central interval.

By the factor theorem [F7] and $T_d(x_j)=0$ from step 1.1, each quotient $T_d(X)\mathrm{/}(X-x_j)$ is a polynomial of degree $d-1$, so the Lagrange polynomials $L_j(X):=T_d(X)\mathrm{/}((X-x_j)T_d^{\mathrm{\prime }}(x_j))$ have degree at most $d-1$. At $x_i$ with $i\mathrm{\ne }j$, $L_j(x_i)=0$; at $x_j$, factorization $T_d(X)=(X-x_j)s_j(X)$ and product rule [F11] give $s_j(x_j)=T_d^{\mathrm{\prime }}(x_j)$, so $L_j(x_j)=1$. Thus every $r$ as in step 2.1 satisfies $r(X)={\sum }_{j=1}^{d}r(x_j)L_j(X)$, since the difference has degree at most $d-1$ and $d$ distinct roots, hence vanishes by [F7]. Repeated factorization by [F7] gives $T_d(X)=c{\prod }_j(X-x_j)$ with $c\mathrm{\ne }0$ (degree $d$ by [F3]); repeated product rule gives $T_d^{\mathrm{\prime }}(X)=c{\sum }_j{\prod }_{k\mathrm{\ne }j}(X-x_k)$. Therefore the polynomial ${\sum }_j{T}_d(X)\mathrm{/}(X-x_j)-T_d^{\mathrm{\prime }}(X)$ vanishes for every $X$ away from the nodes, an infinite set, so it is zero by the root bound [F7]. Substituting $1\mathrm{/}{T}_d^{\mathrm{\prime }}(x_j)=(-1{)}^{j-1}\sin {\theta }_j\mathrm{/}d$ from step 1.1 gives $r(X)=\frac{1}{d}{\sum }_{j=1}^d(-1{)}^{j-1}\sin {\theta }_{j}r(x_j)\frac{T_d(X)}{X-x_j}$.

Let $W:={\max }_{\eta \in [0,2\pi ]}\mathrm{\mid }{S}_r(\eta )\mathrm{\mid }$. At each node, $\sin {\theta }_j\mathrm{\mid }r(x_j)\mathrm{\mid }=\mathrm{\mid }{S}_r({\theta }_j)\mathrm{\mid }\le W$. For $x\in (x_1,1]$, all $x-x_j>0$, and the interpolation formula of step 3.1 gives $\mathrm{\mid }r(x)\mathrm{\mid }\le (W\mathrm{/}d)\mathrm{\mid }{T}_d(x)\mathrm{\mid }{\sum }_{j}1\mathrm{/}(x-x_j)=(W\mathrm{/}d)\mathrm{\mid }{T}_d^{\mathrm{\prime }}(x)\mathrm{\mid }$. For $x\in [-1,-x_1)$ all denominators are negative, so the summands $T_d(x)\mathrm{/}(x-x_j)$ have a common sign and their absolute values sum to $\mathrm{\mid }{T}_d^{\mathrm{\prime }}(x)\mathrm{\mid }$; the same interpolation and node bounds give $\mathrm{\mid }r(x)\mathrm{\mid }\le (W\mathrm{/}d)\mathrm{\mid }{T}_d^{\mathrm{\prime }}(x)\mathrm{\mid }$. For interior $x=\cos \theta$, $0<\theta <\pi$, differentiating [F4] by [F6] gives $\mathrm{\mid }{T}_d^{\mathrm{\prime }}(x)\mathrm{\mid }=d\mathrm{\mid }\sin (d\theta )\mathrm{\mid }\mathrm{/}\sin \theta \le d^2$ by the sine estimate of step 2.1. Continuity extends this bound to the outer endpoints; the central boundary nodes are covered by step 2.1. Hence $\mathrm{\mid }r(x)\mathrm{\mid }\le dW$ on the outer intervals. Combining this with step 2.1 proves $\mathrm{\parallel }r{\mathrm{\parallel }}_{[-1,1]}\le d{\max }_{\eta \in [0,2\pi ]}\mathrm{\mid }{S}_r(\eta )\mathrm{\mid }$ on all of $[-1,1]$.

For continuous $g$ on $[-1,1]$ write $\mathrm{\parallel }g\mathrm{\parallel }:={\max }_{[-1,1]}\mathrm{\mid }g\mathrm{\mid }$; for continuous $2\pi$-periodic $S$ write $\mathrm{\parallel }S{\mathrm{\parallel }}_{\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{g}}:={\max }_{[0,2\pi ]}\mathrm{\mid }S\mathrm{\mid }$. Let $S$ be a real trigonometric polynomial of degree at most $d$, meaning a finite real linear combination of $1,\cos (k\theta ),\sin (k\theta )$ for $1\le k\le d$. Its sine and cosine terms and their derivatives are continuous by [F6] and [F10], and are $2\pi$-periodic by [F15], so all maxima just defined, including that of $\mathrm{\mid }{S}^{\mathrm{\prime }}\mathrm{\mid }$, exist by [F9]. For fixed $\alpha$, $F_{\alpha }(\theta ):=(S(\alpha +\theta )-S(\alpha -\theta ))\mathrm{/}2$ is a linear combination of $\sin (k\theta )$: the constant term cancels, each cosine term contributes $-\sin (k\alpha )\sin (k\theta )$, and each sine term contributes $\cos (k\alpha )\sin (k\theta )$ by the addition formulas [F8] and parity [F14]. By [F4], $\sin (k\theta )=\sin \theta U_{k-1}(\cos \theta )$, so $F_{\alpha }(\theta )=\sin \theta r(\cos \theta )$ for a polynomial $r$ supported in degrees at most $d-1$ by [F3]. By the chain rule [F6], differentiating the centered difference at $0$ gives $F_{\alpha }^{\mathrm{\prime }}(0)=(S^{\mathrm{\prime }}(\alpha )+S^{\mathrm{\prime }}(\alpha ))\mathrm{/}2=S^{\mathrm{\prime }}(\alpha )$. Differentiating the factorization using polynomial differentiability [F2], [F6], and [F11] gives $F_{\alpha }^{\mathrm{\prime }}(0)=r(1)$, because $\sin 0=0$ and $\cos 0=1$ by [F6]. Thus $S^{\mathrm{\prime }}(\alpha )=r(1)$. By steps 2.1 and 4.1, $\mathrm{\mid }r(1)\mathrm{\mid }\le \mathrm{\parallel }r\mathrm{\parallel }\le d\mathrm{\parallel }{F}_{\alpha }{\mathrm{\parallel }}_{\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{g}}$. Also $\mathrm{\parallel }{F}_{\alpha }{\mathrm{\parallel }}_{\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{g}}\le \mathrm{\parallel }S{\mathrm{\parallel }}_{\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{g}}$ by [F12], since $F_{\alpha }$ is the half-difference of two values of $S$. As this holds for every $\alpha$, $\mathrm{\parallel }{S}^{\mathrm{\prime }}{\mathrm{\parallel }}_{\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{g}}\le d\mathrm{\parallel }S{\mathrm{\parallel }}_{\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{g}}$.

Put $S(\theta ):=p(\cos \theta )$. Applying [F8] at $(u,v)$ and $(u,-v)$ and using [F14] gives $\cos u\cos v=(\cos (u+v)+\cos (u-v))\mathrm{/}2$. Induction now gives that each power ${\cos }^k\theta$ is a linear combination of $\cos (j\theta )$ for $0\le j\le k$: multiplying a term $\cos (j\theta )$ by $\cos \theta$ gives frequencies $j+1$ and $j-1$ when $j\ge 1$, while the constant term gives $\cos \theta$. Thus $S$ is a real trigonometric polynomial of degree at most $d$. Cosine decreases from $1$ to $-1$ on $[0,\pi ]$ by [F5] and its endpoint values [F6], [F5], so its range on $[0,2\pi ]$ is $[-1,1]$; with [F15] this gives $\mathrm{\parallel }S{\mathrm{\parallel }}_{\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{g}}=\mathrm{\parallel }p\mathrm{\parallel }$. The chain rule [F6] and polynomial differentiability [F2] give $S^{\mathrm{\prime }}(\theta )=-\sin \theta p^{\mathrm{\prime }}(\cos \theta )$, so step 5.1 gives ${\max }_{\theta \in [0,2\pi ]}\mathrm{\mid }\sin \theta p^{\mathrm{\prime }}(\cos \theta )\mathrm{\mid }\le d\mathrm{\parallel }p\mathrm{\parallel }$. Applying the inequality proved in steps 2.1 and 4.1 to $r=p^{\mathrm{\prime }}$, whose degree is at most $d-1$ by [F2], yields $\mathrm{\parallel }{p}^{\mathrm{\prime }}\mathrm{\parallel }\le d{\max }_{\theta \in [0,2\pi ]}\mathrm{\mid }\sin \theta p^{\mathrm{\prime }}(\cos \theta )\mathrm{\mid }\le d^2\mathrm{\parallel }p\mathrm{\parallel }$. Finally, let $M=\max p$ and $m=\min p$, attained by [F9], and apply this derivative bound to $p-(M+m)\mathrm{/}2$. Its range height is $h$ and its supremum norm is $h\mathrm{/}2$, while its derivative is $p^{\mathrm{\prime }}$. Thus $\max \mathrm{\mid }{p}^{\mathrm{\prime }}\mathrm{\mid }\le d^{2}h\mathrm{/}2$, as claimed.

By [F1]–[F3], both $q$ and $\mathrm{\mid }{q}^{\mathrm{\prime }}\mathrm{\mid }$ are continuous on the compact interval $[0,N]$. Thus there exist $u,v\in [0,N]$ with $q(u)=\max q=:M$, $q(v)=\min q=:m$, and $D=\max \mathrm{\mid }{q}^{\mathrm{\prime }}\mathrm{\mid }$. In particular $h=M-m\ge 0$ and $D\ge 0$.

For any $x\in [0,N]$, some grid integer $k\in \{0,\dots ,N\}$ satisfies $\mathrm{\mid }x-k\mathrm{\mid }\le 1\mathrm{/}2$ (choose a nearest integer, with an endpoint grid point at either boundary). Applying [F4] on the interval between $x$ and $k$ when they differ gives $\mathrm{\mid }q(x)-q(k)\mathrm{\mid }\le D\mathrm{\mid }x-k\mathrm{\mid }\le D\mathrm{/}2$; equality of the points gives the same inequality directly.

If $h\le 1$, then $\max \{0,h-1\}=0\le D$. It remains to consider $h>1$.

Apply step 1.2 at a maximizer $u$ and a minimizer $v$. The grid bounds give $M\le 1+D\mathrm{/}2$ and $m\ge -D\mathrm{/}2$, so $h=M-m\le 1+D$. Rearranging yields $D\ge h-1$.

The polynomial functions $q,q^{\mathrm{\prime }}$ are continuous and attain extrema on $[0,N]$ by [F3], so $h,D$ are defined. Put $p(u):=q(N(u+1)\mathrm{/}2)$ for $u\in [-1,1]$. It has no supported monomial above degree $d$ and the same range height $h$ as $q$ on $[0,N]$. By the chain rule in [F3], $p^{\mathrm{\prime }}(u)=(N\mathrm{/}2)q^{\mathrm{\prime }}(N(u+1)\mathrm{/}2)$, hence $\max \mathrm{\mid }{p}^{\mathrm{\prime }}\mathrm{\mid }=(N\mathrm{/}2)D$. Applying [F1] gives $(N\mathrm{/}2)D\le (d^2\mathrm{/}2)h$.

Since $N>0$, multiplying the inequality of step 1.1 by $2\mathrm{/}N$ yields $D\le d^{2}h\mathrm{/}N$. The grid-return estimate [F2] is compatible with this bound and gives the additional consequence $h\le 1+D$ that will be used in the OR lower-bound proof.

At the root, the branch weight is one and the state is the fixed all-zero basis-state projector, so every entry of ${\sigma }_{\mathrm{\varnothing }}$ is constant and has no supported monomial above degree zero.

Induction hypothesis: at a history $h$ with $t(h)$ queries, each entry of ${\sigma }_h(x)$ has no supported monomial of degree greater than $2t(h)$.

On a fixed unitary edge, multiplying the branch weight into the conditional-state update gives ${\sigma }_{h^{\mathrm{\prime }}}=U{\sigma }_h{U}^{†}$, a fixed linear map on entries, so the support degree does not increase and the query count remains $t(h)$. At instrument outcome $a$ of a positive-weight history, if $q_a>0$, then ${\sigma }_{ha}=w_h{q}_a({\mathcal{I}}_a({\rho }_h)\mathrm{/}{q}_a)={\mathcal{I}}_a({\sigma }_h)$. If $q_a=0$, [F6] makes ${\mathcal{I}}_a({\rho }_h)$ nonnegative with trace zero; its nonnegative eigenvalues sum to zero, so the operator is zero and ${\sigma }_{ha}=0={\mathcal{I}}_a({\sigma }_h)$. A zero-weight parent also maps to zero by linearity. Since all non-oracle maps are fixed independently of $x$ by [F1], every such instrument branch is a fixed linear map on entries and preserves the support degree bound in [step 1.2].

At an oracle node, the matrix entries of $U_{g_x}$ in the computational basis are constants, $x_i$, or $1-x_i$: a one-hot address $e_i$ toggles the target exactly when $x_i=1$, and every other address leaves it unchanged. The same holds for $U_{g_x}^{†}$, which equals $U_{g_x}$ because an XOR query is an involution. Therefore each entry of $U_{g_x}{\sigma }_h{U}_{g_x}^{†}$ is a finite sum of products of one affine entry, one entry with support degree at most $2t(h)$ from [step 1.2], and one affine entry. By [F4]–[F5] its support degree is at most $2t(h)+2$, and the new history has $t(h)+1$ queries.

Induct on the finite execution-tree depth from [F1]. Step 1.1 proves the root case. At each successor edge, step 2.1 preserves the degree bound when the query count is unchanged, and step 2.2 raises its upper bound by exactly two when a query is added. Therefore every history $h$ satisfies the claimed support degree bound $2t(h)$; zero-weight histories satisfy it because all their entries are zero.

Before any query, every basis amplitude is a coordinate of the fixed initial state, hence is a constant polynomial whose support has no degree above zero. Suppose at a prefix with $t$ queries every amplitude has a representative with no supported monomial of degree greater than $t$.

A fixed unitary $U$ sends an amplitude vector $({\alpha }_v(x){)}_v$ to ${\alpha }_u^{\mathrm{\prime }}(x)={\sum }_v{U}_{uv}{\alpha }_v(x)$. This is a finite complex linear combination by [F2]–[F3], so each new amplitude has no supported monomial of degree greater than $t$.

At a query, if the address is one-hot $e_i$, the target bit amplitude update is ${\alpha }_{e_i,b,w}^{\mathrm{\prime }}(x)=(1-x_i){\alpha }_{e_i,b,w}(x)+x_i{\alpha }_{e_i,b\oplus 1,w}(x)$; at a non-one-hot address the amplitude is unchanged. Each coefficient is affine in $x_i$, so the new amplitude has no supported monomial of degree greater than $t+1$. This includes $N=0$, when there are no one-hot addresses and the query leaves the target unchanged.

Traverse the finite circuit in its chronological order. A non-oracle layer preserves the support degree bound by step 2.1; each query raises that bound by at most one by step 2.2. Induction on the finite prefix length therefore gives no supported monomial above the query count at every prefix, and in particular none above $T$ at termination.

Replace $p$ by its multilinear reduction $\tilde{p}$ from [F2]. It agrees at every Boolean point and has no monomial of degree greater than $d$. Write $\tilde{p}(X)={\sum }_{S\subseteq [N],\mathrm{\mid }S\mathrm{\mid }\le d}{c}_S{X}_S$, where $X_S:={\prod }_{i\in S}{X}_i$ and $X_{\mathrm{\varnothing }}=1$.

Define $\bar{p}(x):=\frac{1}{N!}{\sum }_{\pi \in S_N}\tilde{p}(x_{\pi (0)},\dots ,x_{\pi (N-1)})$. For $x\in D$, each permuted point is in $D$ and has $f(\pi x)=f(x)$, so [F1] gives $\mathrm{\mid }\tilde{p}(\pi x)-f(x)\mathrm{\mid }\le ϵ$ for every $\pi$. Repeated [F5] and division by the positive average factor from [F4] give $\mathrm{\mid }\bar{p}(x)-f(x)\mathrm{\mid }\le \frac{1}{N!}{\sum }_{\pi \in S_N}\mathrm{\mid }\tilde{p}(\pi x)-f(x)\mathrm{\mid }\le ϵ$.

Fix a set $S$ of size $s$. Under the average over $S_N$, each subset $R$ of size $s$ occurs as the permuted image of $S$ exactly $s!(N-s)!$ times. Hence the average of $X_S$ is ${\left(\genfrac{}{}{0px}{}{N}{s}\right)}^{-1}{\sum }_{\mathrm{\mid }R\mathrm{\mid }=s}{X}_R$, a polynomial of degree at most $s$. Summing with coefficients $c_S$ shows that $\bar{p}$ has degree at most $d$ and is invariant under all coordinate permutations.

If $x$ has Hamming weight $t$, exactly $\left(\genfrac{}{}{0px}{}{t}{s}\right)$ of the squarefree monomials $x_R$ with $\mathrm{\mid }R\mathrm{\mid }=s$ equal $1$ (their index sets must lie inside the $t$ coordinates equal to $1$); all others equal $0$. Therefore the average of each degree-$s$ monomial at $x$ is $\left(\genfrac{}{}{0px}{}{t}{s}\right)\mathrm{/}\left(\genfrac{}{}{0px}{}{N}{s}\right)=(t{)}_s\mathrm{/}(N{)}_s$, where $(t{)}_s=t(t-1)\cdots (t-s+1)$ and $(t{)}_0=1$. The denominator $(N{)}_s$ is nonzero for $s\le N$ by [F4]. Thus $\bar{p}(x)=q(\mathrm{\mid }x\mathrm{\mid })$ for the univariate polynomial $q(t)={\sum }_S{c}_S(t{)}_{\mathrm{\mid }S\mathrm{\mid }}\mathrm{/}(N{)}_{\mathrm{\mid }S\mathrm{\mid }}$, with the $s=0$ term interpreted as $1$. Each summand has degree $\mathrm{\mid }S\mathrm{\mid }\le d$, so $\mathrm{deg}q\le d$. By step 2.1 it retains the approximation bound on $D$.