= Solution
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. Hence
$$
\boxed{\operatorname{MAJ}(x)=x_1x_2+x_1x_3+x_2x_3-2x_1x_2x_3.}
$$
This 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\ge3/2$, and the integer number of queries gives
$$
\boxed{Q_E(\operatorname{MAJ})\ge2.}
$$
Back to article page
