Determining the equivalence for one-way quantum finite automata

AbstractTwo quantum finite automata are equivalent if for any input string x the two automata accept x 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 A1 and A2 with control languages (regular languages) L1 and L2, respectively, are equivalent if and only if they are (c1n12+c2n22−1)-equivalent, where n1 and n2 are the numbers of states in A1 and A2, respectively, and c1 and c2 are the numbers of states in the minimal DFAs that recognize L1 and L2, respectively. Furthermore, if L1 and L2 are given in the form of DFAs, with m1 and m2 states, respectively, then there exists a polynomial-time algorithm running in time O((m1n12+m2n22)4) that takes as input A1 and A2 and determines whether they are equivalent.(ii)(As an application of item (i)): Two MM-1QFAs A1 and A2 with n1 and n2 states, respectively, are equivalent if and only if they are (3n12+3n22−1)-equivalent. Furthermore, there is a polynomial-time algorithm running in time O((3n12+3n22)4) that takes as input A1 and A2 and determines whether A1 and A2 are equivalent