On the Quantum Black-Box Complexity of Majority

• Authors: T. Hayes, S. Kutin, and D. van Melkebeek.

• Reference: Algorithmica, 34: 480-501, 2002. Special issue for selected papers on quantum information processing.

• Earlier version:
  • T. Hayes, S. Kutin, and D. van Melkebeek. On the Quantum Complexity of Majority. quant-ph/0109101, 2001.

Abstract

We describe a quantum black-box network computing the majority of N bits with zero-sided error eps using only 2/3N + O((N log (eps^-1 log N))^½) queries: the algorithm returns the correct answer with probability at least 1 - eps, 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 2/3N - O(N^½) 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.