Block conjunction of three-bit majorities
ID: block-conjunction-of-three-bit-majorities
Its disjoint triples give a product of degree-three multilinear polynomials, with all-variable coefficient . Hence its degree is and its exact quantum query complexity is at least . At the input consisting of repeated triples, each of the one bits is a disjoint sensitive singleton. Thus block sensitivity is at least , implying a bounded-error quantum query complexity lower bound .
New to topics? Read the docs here!