On the Quantum Complexity of Majority

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


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 are available on this technical report.