Polynomial Method and Approximate Degree — Examples

The matrices in [F3] and [F4] satisfy $H^{\ast }H=I$ and $X^{\ast }X=I$ by direct multiplication; the CNOT action in [F3] permutes the four computational-basis vectors, so it is unitary. Starting at $\mathrm{\mid }00,0⟩$, apply $X$ to the second address bit, then $H$ to the first and CNOT from the first to the second. The basis actions in [F3]–[F4] give $\frac{1}{\sqrt{2}}(\mathrm{\mid }01,0⟩+\mathrm{\mid }10,0⟩)=\frac{1}{\sqrt{2}}(\mathrm{\mid }{e}_1,0⟩+\mathrm{\mid }{e}_0,0⟩)$. These are fixed input-independent unitaries permitted by [F1].

One oracle call and [F2] transform this to $\frac{1}{\sqrt{2}}(\mathrm{\mid }{e}_1,x_1⟩+\mathrm{\mid }{e}_0,x_0⟩)$. Measuring the target and accepting exactly when it is $1$ has probability $\frac{1}{2}\mathrm{\mid }{x}_1{\mathrm{\mid }}^2+\frac{1}{2}\mathrm{\mid }{x}_0{\mathrm{\mid }}^2=(x_0+x_1)\mathrm{/}2$, because the orthogonal address basis states have no cross terms and each $x_i$ is a bit. This gives the stated acceptance polynomial.

On $00$ the acceptance probability is $0=f(00)$, and on $11$ it is $1=f(11)$, so the algorithm is exact on $D$ with one query. The polynomial $p$ has total degree one by [F7]. No constant polynomial can be exact on $D$ because a constant has the same value at $00$ and $11$, while $f$ differs there. Thus ${\stackrel{}{\mathrm{deg}}}_0(f;D)=1$ by [F5], and the one-query construction verifies $Q_0^{\mathrm{b}\mathrm{i}\mathrm{t}}(f;D)\le 1$ by [F6].

The Pauli $X$ in [F5] toggles a basis bit and is a fixed unitary because it permutes the two basis vectors. Start at the all-zero address, target, and two-bit output register. In the first round, apply $X$ to the first address bit to set the address to $e_0$, query and measure the target; since it began at zero, the outcome is deterministically $x_0$ by [F2]. If the outcome is $1$, apply $X$ to the first output bit and to the target; if it is $0$, leave both unchanged. This copies the result and resets the target. Apply $X$ to both address bits to change $e_0$ into $e_1$; repeat the query and measurement, copying the second outcome into the second output bit and resetting the target in the same way. Every outcome-controlled operation is a fixed unitary on its branch by [F1] and [F5]; the output is deterministically $(x_0,x_1)$. This finite tree uses exactly two queries. Accept on the fixed subset $\{00,01,10\}$, so the algorithm computes NAND.

The resulting acceptance polynomial is $p(X_0,X_1)=1-X_0{X}_1$: its values are $1,1,1,0$ at $00,01,10,11$, respectively, exactly the NAND acceptance law. In particular it lies in $[0,1]$ on the Boolean cube.

Averaging $p$ over the two coordinate permutations leaves its constant term $1$ fixed and sends $X_0{X}_1$ to itself. By [F4], the associated Hamming-weight polynomial is $q(t)=1-\left(\genfrac{}{}{0px}{}{t}{2}\right)=1-t(t-1)\mathrm{/}2$, since it takes values $1,1,0$ at weights $0,1,2$.

At the noninteger point $t=1\mathrm{/}2$, $q(1\mathrm{/}2)=1-((1\mathrm{/}2)(-1\mathrm{/}2))\mathrm{/}2=9\mathrm{/}8>1$. Thus the symmetrized polynomial is not constrained to remain in $[0,1]$ between integer Hamming weights, refuting the claim.