On the Quantum Complexity of Majority
Thomas P. Hayes, Samuel Kutin, Dieter van Melkebeek · 1998
We construct a quantum black-box algorithm that computes the majority of N bits exactly using N + 1 \\Gamma w(N ) queries, where w(N ) denotes the number of ones in the binary expansion of N . We establish a matching lower bound in a generalized classical decision tree model in which the equivalent of our quantum algorithm is optimal. We also provide an exact quantum algorithm that almost surely makes no more than N p 2 + O((N log N ) 2 3 ) queries. 1 Introduction Suppose we wish to compute the value f(X) of a Boolean function f : f0; 1g N ! f0; 1g where the input X is given to us as a black-box X : f0, : : : , N \\Gamma 1g ! f0; 1g. The cost of the computation will be the number of queries we make to the oracle X . In the classical case, this model of computation is known as a decision tree, and has been well-studied. More recently, a quantum mechanical version of this model has been considered. Several complexity measures are investigated in this setting: the number of queries...