Determining the minimum number of states required by a deterministic finite automaton to separate a given pair of different words (to accept one word and to reject the other) is an important challenge. In this paper, we ask the same question for quantum finite automata (QFAs). We classify such pairs as easy and hard ones. We show that 2-state QFAs with real amplitudes can separate any easy pair with zero-error but cannot separate some hard pairs even in nondeterministic acceptance mode. When using complex amplitudes, 2-state QFAs can separate any pair in nondeterministic acceptance mode, and here we 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.

Additional Metadata
Persistent URL dx.doi.org/10.1007/978-3-319-40946-7_18
Journal Lecture Notes in Computer Science
Conference International Conference on Implementation and Application of Automata
Grant This work was funded by the European Commission 7th Framework Programme; grant id erc/615307 - Progress in quantum computing: Algorithms, communication, and applications (QPROGRESS)
Citation
Belovs, A, Montoya, J.A, & Yakaryılmaz, A. (2016). Looking for pairs that hard to separate: a quantum approach. In Lecture Notes in Computer Science (Vol. 9705, pp. 213–223). doi:10.1007/978-3-319-40946-7_18