Average-case quantum query complexity

We compare classical and quantum query complexities of total Boolean functi ons. It is known that for worst-case complexity, the gap between quantum an d classical can be at most polynomial. We show that for average-case comple xity under the uniform distribution, quantum algorithms can be exponentiall y faster than classical algorithms. Under non-uniform distributions the gap can even be super-exponential. We also prove some general bounds for avera ge-case complexity and show that the average-case quantum complexity of MAJ ORITY under the uniform distribution is nearly quadratically better than th e classical complexity.