= Block conjunction of three-bit majorities
{title2=$\operatorname{MAJ}_n(x)=\bigwedge_{i=1}^n\operatorname{MAJ}(b_i)$}
Its $n$ disjoint triples give a product of degree-three <multilinear polynomials>, with all-variable coefficient $(-2)^n$. Hence its degree is $3n$ and its <exact quantum query complexity> is at least $\lceil3n/2\rceil$. At the input consisting of repeated $110$ triples, each of the $2n$ one bits is a disjoint sensitive singleton. Thus <block sensitivity> is at least $2n$, implying a bounded-error <quantum query complexity> lower bound $\Omega(\sqrt n)$.
Back to article page
