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.
