Physics – Quantum Physics
Scientific paper
2007-03-11
Physics
Quantum Physics
Comments are welcome
Scientific paper
In this paper, we focus on determining the equivalence for {\it 1-way quantum finite automata with control language} (CL-1QFAs) defined by Bertoni et al and {\it measure-many 1-way quantum finite automata} (MM-1QFAs) introduced by Kondacs and Watrous. More specifically, we obtain that: \begin{enumerate} \item[(i)] Two CL-1QFAs ${\cal A}_1$ and ${\cal A}_2$ with control languages (regular languages) ${\cal L}_1$ and ${\cal L}_2$, respectively, are equivalent if and only if they are $(c_1n_1^2+c_2n_2^2-1)$-equivalent. Furthermore, if ${\cal L}_1$ and ${\cal L}_2$ are given in the form of DFAs, with $m_1$ and $m_2$ states, respectively, then there exists a polynomial-time algorithm running in time $O ((m_1n_1^2+m_2n_2^2)^4)$ that takes as input ${\cal A}_1$ and ${\cal A}_2$ and determines whether they are equivalent. \item[(ii)] Two MM-1QFAs ${\cal A}_1$ and ${\cal A}_2$ with $n_1$ and $n_2$ states, respectively, are equivalent if and only if they are $(3n_1^2+3n_2^2-1)$-equivalent. Furthermore, there is a polynomial-time algorithm running in time $O ((3n_1^2+3n_2^2)^4)$ that takes as input ${\cal A}_1$ and ${\cal A}_2$ and determines whether ${\cal A}_1$ and ${\cal A}_2$ are equivalent.
Li Lvzhou
Qiu Daowen
No associations
LandOfFree
Determining the equivalence for 1-way quantum finite automata 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 Determining the equivalence for 1-way quantum finite automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Determining the equivalence for 1-way quantum finite automata will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-45769