= Polynomial method for quantum query lower bounds
{title2=$\deg(f)\le2Q_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\deg(f)/2\rceil$. For bounded error the acceptance polynomial only approximates the <Boolean function>; its exact representing degree is not the relevant bound.
Back to article page
