Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Quantum distinguishing complexity, zero-error algorithms, and
  statistical zero knowledge   We define a new query measure we call quantum distinguishing complexity,
denoted QD(f) for a Boolean function f. Unlike a quantum query algorithm, which
must output a state close to |0> on a 0-input and a state close to |1> on a
1-input, a "quantum distinguishing algorithm" can output any state, as long as
the output states for any 0-input and 1-input are distinguishable.
  Using this measure, we establish a new relationship in query complexity: For
all total functions f, Q_0(f)=O~(Q(f)^5), where Q_0(f) and Q(f) denote the
zero-error and bounded-error quantum query complexity of f respectively,
improving on the previously known sixth power relationship.
  We also define a query measure based on quantum statistical zero-knowledge
proofs, QSZK(f), which is at most Q(f). We show that QD(f) in fact lower bounds
QSZK(f) and not just Q(f). QD(f) also upper bounds the (positive-weights)
adversary bound, which yields the following relationships for all f: Q(f) >=
QSZK(f) >= QS(f) = Omega(Adv(f)). This sheds some light on why the adversary
bound proves suboptimal bounds for problems like Collision and Set Equality,
which have low QSZK complexity.
  Lastly, we show implications for lifting theorems in communication
complexity. We show that a general lifting theorem for either zero-error
quantum query complexity or for QSZK would imply a general lifting theorem for
bounded-error quantum query complexity.

14
The categories of this paper are: math-ph
2
The categories of this paper are: math
9
The categories of this paper are: nlin
24
The categories of this paper are: dg-ga
36
The categories of this paper are: cmp-lg
4
The categories of this paper are: cond-mat
6
The categories of this paper are: astro-ph
30
The categories of this paper are: q-alg
20
The categories of this paper are: acc-phys
34
The categories of this paper are: chem-ph
18
The categories of this paper are: econ
10
The categories of this paper are: q-bio
35
The categories of this paper are: mtrl-th
5
The categories of this paper are: gr-qc
31
The categories of this paper are: ao-sci
22
The categories of this paper are: chao-dyn