Abstract. We describe a quantum black-box network computing the majority of N bits with zero-sided error ɛ using only
queries: the algorithm returns the correct answer with probability at least 1 - ɛ , 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/3N . We provide a nearly matching lower bound of
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 .
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Hayes, ., Kutin, . & van Melkebeek, . The Quantum Black-Box Complexity of Majority . Algorithmica 34, 480–501 (2002). https://doi.org/10.1007/s00453-002-0981-6
Issue Date:
DOI: https://doi.org/10.1007/s00453-002-0981-6