Dieter van Melkebeek(UW-Madison): On the Quantum Complexity of Majority

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 using only 2/3N + o(N) queries and with zero sided error, i.e., the algorithm returns the correct answer with very high probability, and reports "I don't know" otherwise. Any classical algorithm needs N queries achieve this.

Joint work with T. Hayes and S. Kutin.