Chicago Journal of Theoretical Computer Science

Volume 2012

Article 8

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

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

Ashley Montanaro
Centre for Quantum Information and Foundations
Department of Applied Mathematics and Theoretical Physics
University of Cambridge, UK
am994 AT

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.

DOI: 10.4086/cjtcs.2012.008

[] Volume 2012, Article 7 [] Volume 2012, Article 9
[back] Volume 2012 [back] Published articles
[CJCTS home]