- Authors: T. Hayes, S. Kutin, and D. van Melkebeek.
- Reference:
*Algorithmica*, 34: 480-501, 2002. Special issue for selected papers on quantum information processing. - Earlier version:
- T. Hayes, S. Kutin, and D. van Melkebeek. On the Quantum Complexity of Majority. quant-ph/0109101, 2001.

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

dieter@cs.wisc.edu