On the Quantum Black-Box Complexity of Majority.
Thomas P. Hayes, Samuel Kutin, Dieter van Melkebeek.
Algorithmica 34 (2002) 480-501. (Special issue for selected papers on quantum information processing.)
Archived electronically on quant-ph (older versions available there).
Abstract: We describe a quantum black-box network computing the majority of N
bits with zero-sided error ε using only 2/3 N + O((N log (ε-1 log
N))1/2) queries: the algorithm returns the correct answer with
probability at least 1 - ε, and ``I don't know'' otherwise. Our
algorithm is given as a randomized "XOR decision tree" for which the
number of queries on any input is strongly concentrated around a value
of at most 2/3 N. We provide a nearly matching lower bound of 2/3 N -
O(N1/2) on the expected number of queries on a worst-case input in the
randomized XOR decision tree model with zero-sided error o(1). Any
classical randomized decision tree computing the majority on N bits
with zero-sided error 1/2 has cost N.