Another approach to the equivalence of measure-many one-way quantum finite automata and its application

作者：Lin, Tianrong^*

来源：Journal of Computer and System Sciences, 2012, 78(3): 807-821.

DOI：10.1016/j.jcss.2012.01.004

• Quantum finite automata
• Measure-many one-way quantum finite automata
• Enhanced one-way quantum finite automata
• Equivalence

In this paper, we present a much simpler, direct and elegant approach to the equivalence problem of measure many one-way quantum finite automata (MM-1QFA5). The approach is essentially generalized from the work of Carlyle [J.W. Carlyle, Reduced forms for stochastic sequential machines. J. Math. Anal. Appl. 7 (1963) 167-175]. Namely, we reduce the equivalence problem of MM-1QFAs to that of two (initial) vectors. As an application of the approach, we utilize it to address the equivalence problem of enhanced one-way quantum finite automata (E-1QFAs) introduced by Nayak [A. Nayak, Optimal lower bounds for quantum automata and random access codes, in: Proceedings of the 40th IEEE Symposium on Foundations of Computer Science (FOCS), 1999, pp. 369-376]. We prove that two E-1QFA5 A(1) and A(2) over Sigma are equivalence if and only if they are n(1)(2) + n(2)(2) - 1-equivalent where n(1) and n(2) are the numbers of states in A(1) and A(2), respectively. As an important consequence, we obtain that it is decidable whether or not L(A(1)) = L(A(2)) where L(A) subset of Sigma* denotes the set recognizable by MM-1QFA A (or by E-1QFA A) with cutpoint (or with non-strict cutpoint). This also extends a theorem of Eilenberg.

• 出版日期2012-5
• 单位福建师范大学; 福建工程学院