Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Generalizations of the distributed Deutsch-Jozsa promise problem   In the {\em distributed Deutsch-Jozsa promise problem}, two parties are to
determine whether their respective strings $x,y\in\{0,1\}^n$ are at the {\em
Hamming distance} $H(x,y)=0$ or $H(x,y)=\frac{n}{2}$. Buhrman et al. (STOC' 98)
proved that the exact {\em quantum communication complexity} of this problem is
${\bf O}(\log {n})$ while the {\em deterministic communication complexity} is
${\bf \Omega}(n)$. This was the first impressive (exponential) gap between
quantum and classical communication complexity.
  In this paper, we generalize the above distributed Deutsch-Jozsa promise
problem to determine, for any fixed $\frac{n}{2}\leq k\leq n$, whether
$H(x,y)=0$ or $H(x,y)= k$, and show that an exponential gap between exact
quantum and deterministic communication complexity still holds if $k$ is an
even such that $\frac{1}{2}n\leq k<(1-\lambda) n$, where $0<
\lambda<\frac{1}{2}$ is given. We also deal with a promise version of the
well-known {\em disjointness} problem and show also that for this promise
problem there exists an exponential gap between quantum (and also
probabilistic) communication complexity and deterministic communication
complexity of the promise version of such a disjointness problem. Finally, some
applications to quantum, probabilistic and deterministic finite automata of the
results obtained are demonstrated.

0
The categories of this paper are: hep-ph
8
The categories of this paper are: hep-ex
7
The categories of this paper are: hep-th
36
The categories of this paper are: cmp-lg
33
The categories of this paper are: plasm-ph
21
The categories of this paper are: adap-org
35
The categories of this paper are: mtrl-th
24
The categories of this paper are: dg-ga
29
The categories of this paper are: funct-an
3
The categories of this paper are: physics
4
The categories of this paper are: cond-mat
15
The categories of this paper are: nucl-ex
14
The categories of this paper are: math-ph
32
The categories of this paper are: atom-ph
10
The categories of this paper are: q-bio
5
The categories of this paper are: gr-qc