Past exam of the mathematics course of the University of Cambridge / 2012 / iii / Paper 67 / 2 / a / Solution

Use the bit-query Boolean quantum oracle $O_x|i,b,z⟩=|i,b\oplus x_i,z⟩$, 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 isOne 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 givesHere $\mathrm{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.