01009nas a2200157 4500008004100000020002200041245009100063210006900154260001500223300001200238520050600250100001600756700001900772700002300791856003700814 2012 eng d a978-1-4503-1115-100aSuper-Polynomial Quantum Speed-ups for Boolean Evaluation Trees with Hidden Structure0 aSuperPolynomial Quantum Speedups for Boolean Evaluation Trees wi c2012/01/08 a249-2653 a 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.
1 aZhan, Bohua1 aKimmel, Shelby1 aHassidim, Avinatan uhttp://arxiv.org/abs/1101.0796v3