= Solution
Boolean conjunction is multiplication on zero-one inputs. The <block conjunction of three-bit majorities> therefore has the <multilinear polynomial>
$$
P_n(x)=\prod_{i=1}^n\left(x_{3i-2}x_{3i-1}+x_{3i-2}x_{3i}+x_{3i-1}x_{3i}-2x_{3i-2}x_{3i-1}x_{3i}\right).
$$
The factors use disjoint variables, so their product remains a <multilinear polynomial>. Its monomial containing all $3n$ variables has coefficient $(-2)^n\ne0$; no term has higher degree. By uniqueness, the representing <multilinear polynomial> has degree exactly $3n$. Applying the <polynomial method for quantum query lower bounds> gives
$$
\boxed{Q_E(\operatorname{MAJ}_n)\ge\left\lceil\frac{3n}{2}\right\rceil.}
$$
This argument concerns <exact quantum query complexity>; the analogous claim for bounded error does not follow from exact polynomial degree.
Back to article page
