Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Super-Polynomial Quantum Speed-ups for Boolean Evaluation Trees with
  Hidden Structure   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.

9
The categories of this paper are: nlin
31
The categories of this paper are: ao-sci
0
The categories of this paper are: hep-ph
15
The categories of this paper are: nucl-ex
20
The categories of this paper are: acc-phys
2
The categories of this paper are: math
1
The categories of this paper are: cs
19
The categories of this paper are: eess
33
The categories of this paper are: plasm-ph
27
The categories of this paper are: comp-gas
4
The categories of this paper are: cond-mat
5
The categories of this paper are: gr-qc
26
The categories of this paper are: bayes-an
24
The categories of this paper are: dg-ga
8
The categories of this paper are: hep-ex
34
The categories of this paper are: chem-ph