Exponentially more concise quantum recognition of non-RMM regular languages

•We introduce one-way quantum finite automata together with classical states (1QFAC).•We prove that 1QFAC are at most exponentially more concise than DFA.•We give a polynomial-time algorithm for determining the equivalence of 1QFAC.•We show that the state minimization of 1QFAC is decidable within EXPSPACE.

We introduce a new computing model of one-way quantum finite automata (1QFA), namely, one-way quantum finite automata together with classical states (1QFAC). We show that the set of languages accepted by 1QFAC with bounded error consists precisely of all regular languages. In particular, we prove that 1QFAC are at most exponentially more concise than DFA by giving a lower bound, and we also show that this bound is tight for families of regular languages that are not recognized by measure-once (RMO), measure-many (RMM) and multi-letter 1QFA. Then, we give a polynomial-time algorithm for determining whether any two 1QFAC are equivalent. In addition, we show that the state minimization of 1QFAC is decidable within EXPSPACE.