Determining the equivalence for one-way quantum finite automata

摘要

Two 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-lQFAs) introduced by Kondacs and Watrous. More specifically, we obtain that: Two CL-1QFAs A{sub}1 and A{sub}2 with control languages (regular languages) L{sub}1 and L{sub}2, respectively, are equivalent if and only if they are (c{sub}1n{sub}1{sup}2 + c{sub}2n{sub}2{sup}2 - l)-equivalent, where n{sub}1 and n{sub}2 are the numbers of states in A{sub}1 and A{sub}2, respectively, and c{sub}1 and c{sub}2 are the numbers of states in the minimal DFAs that recognize L{sub}1 and L{sub}2, respectively. Furthermore, if L{sub}1 and L{sub}2 are given in the form of DFAs, with m{sub}1 and m{sub}2 states, respectively, then there exists a polynomial-time algorithm running in time O((m{sub}1n{sub}1{sup}2 + m{sub}2n{sub}2{sup}2){sub}4) that takes as input A{sub}1 and A{sub}2 and determines whether they are equivalent. (As an application of item (i)): Two MM-lQFAs A{sub}1 and A{sub}2 with n{sub}1 and n{sub}2 states, respectively, are equivalent if and only if they are (3n{sub}1{sup}2 + 3n{sub}2{sup}2 - l)-equivalent. Furthermore, there is a polynomial-time algorithm running in time O((3n{sub}1{sup}2 +3n{sub}2{sup}2){sup}4) that takes as input A{sub}1 and A{sub}2 and determines whether A{sub}1 and A{sub}2 are equivalent.