Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: The Multiplicative Quantum Adversary   We present a new variant of the quantum adversary method. All adversary
methods give lower bounds on the quantum query complexity of a function by
bounding the change of a progress function caused by one query. All previous
variants upper-bound the_difference_ of the progress function, whereas our new
variant upper-bounds the_ratio_ and that is why we coin it the multiplicative
adversary. The new method generalizes to all functions the new quantum
lower-bound method by Ambainis [Amb05, ASW06] based on the analysis of
eigenspaces of the density matrix. We prove a strong direct product theorem for
all functions that have a multiplicative adversary lower bound.

8
The categories of this paper are: hep-ex
17
The categories of this paper are: q-fin
36
The categories of this paper are: cmp-lg
11
The categories of this paper are: hep-lat
29
The categories of this paper are: funct-an
32
The categories of this paper are: atom-ph
34
The categories of this paper are: chem-ph
1
The categories of this paper are: cs
35
The categories of this paper are: mtrl-th
25
The categories of this paper are: patt-sol
31
The categories of this paper are: ao-sci
7
The categories of this paper are: hep-th
10
The categories of this paper are: q-bio
28
The categories of this paper are: alg-geom
9
The categories of this paper are: nlin
16
The categories of this paper are: stat