@article {1510,
title = {Super-Polynomial Quantum Speed-ups for Boolean Evaluation Trees with Hidden Structure},
journal = {ITCS {\textquoteright}12 Proceedings of the 3rd Innovations in Theoretical Computer Science Conference},
year = {2012},
month = {2012/01/08},
pages = {249-265},
abstract = { We give a quantum algorithm for evaluating a class of boolean formulas (such
as NAND trees and 3-majority trees) on a restricted set of inputs. Due to the
structure of the allowed inputs, our algorithm can evaluate a depth $n$ tree
using $O(n^{2+\log\omega})$ queries, where $\omega$ is independent of $n$ and
depends only on the type of subformulas within the tree. We also prove a
classical lower bound of $n^{\Omega(\log\log n)}$ queries, thus showing a
(small) super-polynomial speed-up.
},
isbn = {978-1-4503-1115-1},
doi = {10.1145/2090236.2090258},
url = {http://arxiv.org/abs/1101.0796v3},
author = {Bohua Zhan and Shelby Kimmel and Avinatan Hassidim}
}