Published by the Department of Computer Science, The University of Chicago.
October 31, 2012
We show that, for any d, all but a doubly exponentially small fraction of decision trees of depth at most d require OMEGA(d) quantum queries to be computed with bounded error. In other words, most efficient classical algorithms in the query complexity model do not admit a significant quantum speed-up. The proof is based on showing that, with high probability, the average sensitivity of a random decision tree is high.
Submitted September 26, 2012, revised October 29 2012, published October 31, 2012.