Studies On The Equivalence Problem Of Quantum Finite Automata

Quantum computing is a research field at the current frontiers of computing, which halfway between mathematics, physics and computer science. Quantum fi-nite automata can be viewed as the simplest theoretical models based on quantum mechanism. The aim of studing quantum finite automata is to explore the power of quantum computation and the characterizations of quantum computation fully. Thus far, variant quantum finite automata have been proposed. Studying of such quantum finite automata pay an indispensable role in further understanding quan-tum computation. In the theory of classical computation, determining the equiva-lence of finite automata is a foundational and important issue. In essentialness, it is concerned with the classification of finite automata. Base on this point of view, the classification of various kinds of quantum finite automata takes on the same position. Concerning these,we make the following contribution.●Starting from the standard word function of MM-1QFAs, we construct a new word function which equivalent to the standard one, then we show that two MM-1QFAs over the same input alphabet are equivalent if and only if they are n12+n22-1-equivalent, where n1 and n2 are the numbers of states of the two MM-1QFAs, respectively;●We then investigated the equivalence issue of multi-letter quantum finite au-tomata (multi-letter QFA). To be specific, in the case that the input alphabet has one element, i.e.,∑={σ}, we show that two multi-letter QFAs are equiv-alent if and only if they are (n1+n2)2+κ-1-equivalent; Then, we show that there exists an integer z such that two multi-letter QFAs are equivalent if and only if they are z-equivalent.