The University of Michigan Combinatorics Seminar
Fall 2001
December 7, 4:10-5:00, 3866 East Hall

On the Quantum Complexity of Majority

Dieter van Melkebeek

University of Wisconsin


How do you tell how a committee of three people will vote on an issue? The obvious approach is to ask each individual what vote he or she is planning to cast. If the first two committee members agree, you can skip the third one, but, if they disagree, you need to talk to all three members.

Suppose, however, that you can perform quantum tranformations on the committee members. In the quantum setting, you can find out in a single query whether the first two members agree or disagree. If they agree, you can disregard the third member and ask one of the first two for his vote. If the first two disagree, you know their votes will cancel, so it suffices to ask the third member for his vote. Either way, you will learn the answer in only two queries.

We will discuss generalizations of this procedure to arbitrarily many voters. We consider both deterministic and randomized algorithms. Our main result yields a quantum algorithm for deciding the majority of N bits with zero-sided error epsilon using only 2N/3 + O(sqrt{N log (log N / epsilon)}) queries: the algorithm returns the correct answer with probability at least 1 - epsilon, and reports ``I don't know'' otherwise. The 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 2N/3. We provide a nearly matching lower bound of 2N/3 - O(sqrt{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.

This is joint work with T. Hayes and S. Kutin.