  Equality and disjointness are two of the most studied problems in
communication complexity. They have been studied for both classical and also
quantum communication and for various models and modes of communication.
Buhrman et al. [Buh98] proved that the exact quantum communication complexity
for a promise version of the equality problem is ${\bf O}(\log {n})$ while the
classical deterministic communication complexity is $n+1$ for two-way
communication, which was the first impressively large (exponential) gap between
quantum and classical (deterministic and probabilistic) communication
complexity. If an error is tolerated, both quantum and probabilistic
communication complexities for equality are ${\bf O}(\log {n})$. However, even
if an error is tolerated, the gaps between quantum (probabilistic) and
deterministic complexity are not larger than quadratic for the disjointness
problem. It is therefore interesting to ask whether there are some promise
versions of the disjointness problem for which bigger gaps can be shown. We
give a positive answer to such a question. Namely, we prove that there exists
an exponential gap between quantum (even probabilistic) communication
complexity and classical deterministic communication complexity of some
specific versions of the disjointness problem.
  Klauck [Kla00] proved, for any language, that the state complexity of exact
quantum/classical finite automata, which is a general model of one-way quantum
finite automata, is not less than the state complexity of an equivalent one-way
deterministic finite automata (1DFA). In this paper we show, using a
communication complexity result, that situation may be different for some
promise problems. Namely, we show for certain promise problem that the gap
between the state complexity of exact one-way quantum finite automata and 1DFA
can be exponential.
