Determining the equivalence for 1-way quantum finite automata
| dc.creator | Li, Lvzhou | |
| dc.creator | Qiu, Daowen | |
| dc.date | 2007-03-11 | |
| dc.date | 2007-04-21 | |
| dc.date.accessioned | 2026-07-07T07:57:30Z | |
| dc.date.available | 2026-07-07T07:57:30Z | |
| dc.description | 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. | |
| dc.description | Comments are welcome | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0703087 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0703087 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/127669 | |
| dc.subject | Quantum Physics | |
| dc.title | Determining the equivalence for 1-way quantum finite automata | |
| dc.type | text |