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

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.

For the three-bit majority function, the pair products count how many pairs of input bits are both one. Their sum is zero at Hamming weights zero and one, one at weight two, and three at weight three. Subtracting twice the triple product corrects the last value. HenceThis is a multilinear polynomial of degree three, and its top coefficient is nonzero. Uniqueness of the Boolean multilinear polynomial excludes a degree-two alternative. The polynomial method for quantum query lower bounds therefore yields $T\ge 3/2$, and the integer number of queries gives

First use the allowed one-query algorithm to learn $p=x_1\oplus x_2$ exactly. This restricted two-index Boolean quantum oracle is realized by relabelling indices $1,2$ in a single query to the original input. Measure its output and choose the second query classically.

If $p=0$, the first two bits agree and their common value is the majority, irrespective of $x_3$. Query $x_1$ and output it. If $p=1$, the first two bits cancel in the vote, so query $x_3$ and output it. ThusThe exact two-query majority algorithm uses one parity query and one ordinary bit query on every branch, and is correct on all eight inputs. Together with the lower bound this proves $Q_E(\mathrm{MAJ})=2$.

Boolean conjunction is multiplication on zero-one inputs. The block conjunction of three-bit majorities therefore has the multilinear polynomialThe factors use disjoint variables, so their product remains a multilinear polynomial. Its monomial containing all $3n$ variables has coefficient $(-2{)}^n\ne 0$; no term has higher degree. By uniqueness, the representing multilinear polynomial has degree exactly $3n$. Applying the polynomial method for quantum query lower bounds givesThis argument concerns exact quantum query complexity; the analogous claim for bounded error does not follow from exact polynomial degree.

For a Boolean function $f$, its block sensitivity at $x$ is the maximum number of pairwise disjoint nonempty index sets $B_j$ such that flipping all bits in each $B_j$ individually changes $f(x)$. Maximize over $x$ to obtain $\mathrm{bs}(f)$.

Choose $x=(110)(110)\cdots (110)$, so every three-bit block has majority one and the conjunction is one. In each block, flipping either of its two one bits alone changes that block's majority to zero and therefore changes the conjunction to zero. These $2n$ singleton index sets are all disjoint, soThe supplied bounded-error quantum query complexity lower bound now givesHere $Q_2$ denotes a fixed two-sided error bound below $1/2$, such as $1/3$.

In fact the block sensitivity is exactly $2n$. At a one-input, selecting two one bits from each triple gives a size-$2n$ certificate: any block flip changing the output must touch it, so disjoint sensitive sets number at most $2n$. At a zero-input, one failing triple contains at least two zero bits; fixing those two zeros certifies zero, so at most two disjoint sensitive sets can change the output. The lower-bound witness above attains $2n$. The certificate complexity of a Boolean function supplies these upper bounds, though only the witness is needed for the requested result.