Determining the equivalence for one-way quantum finite automata

Abstract: Two quantum finite automata are equivalent if for any input string the two automata accept with equal probability. In this paper, we first focus on determining the equivalence for one-way quantum finite automata with control language (CL-1QFAs) defined by Bertoni et al., and then, as an application, we address the equivalence problem for measure-many one-way quantum finite automata (MM-1QFAs) introduced by Kondacs and Watrous. More specifically, we obtain that: [(i)] Two CL-1QFAs and with control languages (regular languages) and , respectively, are equivalent if and only if they are -equivalent, where and are the numbers of states in and , respectively, and and are the numbers of states in the minimal DFAs that recognize and , respectively. Furthermore, if and are given in the form of DFAs, with and states, respectively, then there exists a polynomial-time algorithm running in time that takes as input and and determines whether they are equivalent. [(ii)] (As an application of item (i)): Two MM-1QFAs and with and states, respectively, are equivalent if and only if they are -equivalent. Furthermore, there is a polynomial-time algorithm running in time that takes as input and and determines whether and are equivalent. [Copyright &y& Elsevier]