



@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}
}
