Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Improved quantum test for linearity of a Boolean function   Let a Boolean function be available as a black-box (oracle) and one likes to
devise an algorithm to test whether it has certain property or it is
$\epsilon$-far from having that property. The efficiency of the algorithm is
judged by the number of calls to the oracle so that one can decide, with high
probability, between these two alternatives. The best known quantum algorithm
for testing whether a function is linear or $\epsilon$-far $(0 < \epsilon <
\frac{1}{2})$ from linear functions requires $O(\epsilon^{-\frac{2}{3}})$ many
calls [Hillery and Andersson, Physical Review A 84, 062329 (2011)]. We show
that this can be improved to $O(\epsilon^{-\frac{1}{2}})$ by using the
Deutsch-Jozsa and the Grover Algorithms.

5
The categories of this paper are: gr-qc
14
The categories of this paper are: math-ph
24
The categories of this paper are: dg-ga
36
The categories of this paper are: cmp-lg
21
The categories of this paper are: adap-org
27
The categories of this paper are: comp-gas
26
The categories of this paper are: bayes-an
6
The categories of this paper are: astro-ph
37
The categories of this paper are: supr-con
0
The categories of this paper are: hep-ph
16
The categories of this paper are: stat
22
The categories of this paper are: chao-dyn
25
The categories of this paper are: patt-sol
32
The categories of this paper are: atom-ph
8
The categories of this paper are: hep-ex
10
The categories of this paper are: q-bio