= Solution
Use the bit-query <Boolean quantum oracle> $O_x|i,b,z\rangle=|i,b\mathbin\oplus x_i,z\rangle$, where $z$ denotes workspace. Initially every <probability amplitude> is independent of $x$, hence is a constant <polynomial>. An input-independent <unitary gate> only forms linear combinations of <probability amplitudes>, so it does not increase their <polynomial degree>.
If $a_{i,b,z}(x)$ is an amplitude before a query, its new value is
$$
a'_{i,b,z}(x)=(1-x_i)a_{i,b,z}(x)+x_i a_{i,b\oplus1,z}(x).
$$
One query increases <polynomial degree> by at most one. Inductively, after $T$ queries each amplitude has <polynomial degree> at most $T$. The acceptance <probability> is a sum of squared absolute values of the accepting amplitudes, so it is a real <polynomial> of degree at most $2T$. Intermediate <quantum measurements> and classical adaptation can be retained coherently, or handled by summing unnormalized branch probabilities; either approach yields the same degree bound.
An exact algorithm has acceptance <probability> precisely $f(x)$ at every Boolean input. The <multilinear reduction on the Boolean cube> replaces positive powers of each $x_i$ by $x_i$, preserving these values without increasing <polynomial degree>. Therefore the <polynomial method for quantum query lower bounds> gives
$$
\boxed{\deg(f)\le2T,\qquad Q_E(f)\ge\left\lceil\frac{\deg(f)}2\right\rceil.}
$$
Here $\deg(f)$ is the degree of the unique <multilinear polynomial> representing the <Boolean function>, and $Q_E$ is its <exact quantum query complexity>. Uniqueness follows, for example, by evaluating successively on the indicator vectors of subsets: the value on a subset determines its coefficient once all smaller-subset coefficients are known.
Back to article page
