A T-query bit algorithm has an acceptance polynomial of degree at most 2T

For each terminal history $\mathrm{\ell }$, the accepting probability contribution is the finite sum of the diagonal entries of ${\sigma }_{\mathrm{\ell }}(x)$ over accepting output strings and all unmeasured basis labels. This is the output law of [F1], with the unnormalized branch operator of [F2]. Every summand has a complex polynomial representative of degree at most $2t(\mathrm{\ell })\le 2T$, so their finite sum $G(x)$ has degree at most $2T$ on the Boolean cube.

For each Boolean input $x$, the sum in step 1.1 is the real probability $P_A(x)$. Replace each coefficient of $G$ by its real part to obtain a real polynomial $p_0$; for Boolean $x$, $p_0(x)=\mathrm{Re}G(x)=P_A(x)$, and no supported monomial has degree greater than $2T$. Let $p$ be its multilinear reduction from [F5]. Each monomial is replaced by a squarefree monomial of no larger degree, so $p$ is real multilinear with the same support degree bound, including when it is zero or $N=0$. It agrees with $p_0$ on the Boolean cube and is therefore an acceptance polynomial by [F3].

If $A$ has error at most $ϵ\ge 0$ on $D$, then [F3] makes $p$ an $ϵ$-approximant, so ${\stackrel{}{\mathrm{deg}}}_{ϵ}(f;D)\le 2T$. For $0\le ϵ<1\mathrm{/}2$, this holds for every feasible $T$, in particular for the minimum query count [F4]. Since query counts are integers, the result is the displayed ceiling inequality.