On the Quantum Black-Box Complexity of Majority

Thomas Hayes, Samuel Kutin, Dieter van Melkebeek

We describe a quantum black-box network computing the majority of N bits with zero-sided error eps using only 2N/3 + O(sqrt{N (log log N + log 1/eps)}) queries: the algorithm retur…