1209.4781 (Ashley Montanaro)

Almost all decision trees do not allow significant quantum speed-up    [PDF]

Ashley Montanaro

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.

View original: http://arxiv.org/abs/1209.4781