Published by the Department of Computer Science, The University of Chicago.

Abstract

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.

• The article: PDF (178 Kbytes)
• Source material: ZIP (71 Kbytes)
• BibTeX entry for this article (267 bytes)

Submitted September 26, 2012, revised October 29 2012, published October 31, 2012.

© 2012 Ashley Montanaro
Licensed under a Creative Commons Attribution License

Volume 2012, Article 7

Volume 2012, Article 9

Volume 2012

Published articles