Polynomial method for quantum query lower bounds ($\mathrm{deg}(f)\le 2Q_E(f)$)

After $T$ input-bit queries, every probability amplitude is a polynomial of degree at most $T$, because the bit-query matrix entries are affine in the input bits. An acceptance probability is a sum of squared absolute amplitudes and has polynomial degree at most $2T$. Multilinear reduction on the Boolean cube does not increase degree. Exact acceptance therefore implies $Q_E(f)\ge \lceil \mathrm{deg}(f)/2\rceil$. For bounded error the acceptance polynomial only approximates the Boolean function; its exact representing degree is not the relevant bound.