On the Quantum Complexity of Majority

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.

Joint work with T. Hayes and S. Kutin.