# TR-98-11

## On the Quantum Complexity of Majority

Hayes, Thomas; Kutin, Samuel; Van Melkebeek, Dieter. 11 December, 1998.

### Abstract

We describe a quantum black-box algorithm computing the majority of $N$ bits with zero-sided error
using only $2N/3 + O(\sqrt{N\log N})$ queries:
the algorithm returns the correct answer with overwhelming probability, and ``I don't know'' otherwise.
Our algorithm is given as a randomized ``XOR decision tree''
for which the expected number of queries on the worst-case
input is no more than $2N/3 + O(\log N)$. We provide a nearly matching lower bound of $2N/3 - O(\sqrt N)$
in the randomized XOR decision tree model.

### Original Document

The original document is available in Postscript (uploaded 8 June, 2001 by
Dustin Mitchell).

### Comments

Comments are available on this technical report.