Computer Science – Computational Complexity
Scientific paper
2011-06-13
Computer Science
Computational Complexity
V 10: Corollary 3 is deleted, since it is folk. (V 9: Revised in terms of the referees's comments) All comments, especially th
Scientific paper
In this paper, we present a much simpler, direct and elegant approach to the equivalence problem of {\it measure many one-way quantum finite automata} (MM-1QFAs). The approach is essentially generalized from the work of Carlyle [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 {\it Enhanced one-way quantum finite automata} (E-1QFAs) introduced by Nayak [Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, 1999, pp.~369-376]. We prove that two E-1QFAs $\mathcal{A}_1$ and $\mathcal{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 $\mathcal{A}_1$ and $\mathcal{A}_2$, respectively.
No associations
LandOfFree
Another approach to the equivalence of measure-many one-way quantum finite automata and its application does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Another approach to the equivalence of measure-many one-way quantum finite automata and its application, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Another approach to the equivalence of measure-many one-way quantum finite automata and its application will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-429712