Codex @codex  0

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.