Complexity of Promise Problems on Classical and Quantum Automata

We consider the promise problem TeX on a unary alphabet TeX studied by Gruska et al. in [21]. This problem is formally defined as the pair TeX , with \(0\le r_1\ne r_2 , TeX and TeX . There, it is shown that a measure-once one-way quantum automaton can solve exactly TeX with only TeX basis states, while any one-way deterministic finite automaton requires TeX states, TeX being the smallest integer such that TeX and TeX . Here, we introduce the promise problem TeX as an extension of TeX to general alphabets. Even for this problem, we show the same descriptional superiority of the quantum paradigm over one-way deterministic automata. Moreover, we prove that even by adding features to classical automata, namely nondeterminism, probabilism, two-way motion, we cannot obtain automata for TeX and TeX smaller than one-way deterministic.