  Determining the minimum number of states required by a finite automaton to
separate a given pair of different words is an important problem. In this
paper, we consider this problem for quantum automata (QFAs). We show that
2-state QFAs can separate any pair of words in nondeterministic acceptance mode
and conjecture that they can separate any pair also with zero-error. Then, we
focus on (a more general problem) separating a pair of two disjoint finite set
of words. We show that QFAs can separate them efficiently in nondeterministic
acceptance mode, i.e. the number of states is two to the power of the size of
the small set. Additionally, we examine affine finite automata (AfAs) and show
that two states are enough to separate any pair with zero-error. Moreover, AfAs
can separate any pair of disjoint finite sets of words with one-sided bounded
error efficiently like QFAs in nondeterministic mode.
