  In this note we investigate the relationship between worst-case quantum query
complexity and average-case classical query complexity. Specifically, we show
that if a quantum computer can evaluate a total Boolean function f with bounded
error using T queries in the worst case, then a deterministic classical
computer can evaluate f using O(T^5) queries in the average case, under a
uniform distribution of inputs. If f is monotone, we show furthermore that only
O(T^3) queries are needed. Previously, Beals et al. (1998) showed that if a
quantum computer can evaluate f with bounded error using T queries in the worst
case, then a deterministic classical computer can evaluate f using O(T^6)
queries in the worst case, or O(T^4) if f is monotone. The optimal bound is
conjectured to be O(T^2), but improving on O(T^6) remains an open problem.
Relating worst-case quantum complexity to average-case classical complexity may
suggest new ways to reduce the polynomial gap in the ordinary worst-case versus
worst-case setting.
