The quantum black-box complexity of majority

We describe a quantum black-box network computing the majority of N bits with zero-sided error the correct answer with probability epsilon using only 2/3 N + O (rootN log(epsilon(-1) log N)) queries: the algorithm returns at least 1 - epsilon, 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(rootN) 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.