The least worst-case number of input-oracle calls made by a quantum circuit that computes a Boolean function with zero error on every input. Known unitary gates and classical processing do not count toward this quantity; their runtime is a separate cost.
One exact parity query determines whether the first two bits agree. If they agree, a second query reads one of them; otherwise it reads the third bit. Those values respectively determine the three-bit majority function. The matching lower bound follows from its degree-three multilinear polynomial.
Articles by others on the same topic
There are currently no matching articles.