arXiv:quant-ph/0703087

Determining the equivalence for 1-way quantum finite automata

Lvzhou Li, Daowen Qiu

Published Mar 11, 2007• 1 citation

Abstract

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.

DOI: 10.48550/arxiv.quant-ph/0703087

Related papers

Decidability of the Equivalence of Multi-Letter Quantum Finite Automata

Daowen Qiu, Xiangfu Zou, Lvzhou Li +1 more

arXiv:0812.1061Dec 5, 20084 citations

One-way quantum finite automata together with classical states: Equivalence and Minimization

Daowen Qiu, Paulo Mateus, Xiangfu Zou +1 more

Sep 8, 20092 citations

On equivalence, languages equivalence and minimization of multi-letter and multi-letter measure-many quantum automata

Tianrong Lin

arXiv:1203.0113Mar 1, 20120 citations

One-way quantum finite automata together with classical states

Daowen Qiu, Paulo Mateus, Xiangfu Zou +1 more

arXiv:0909.1428Sep 8, 20094 citations

Quantum finite automata with control language

Carlo Mereghetti, Beatrice Palano

RAIRO - Theoretical Informatics and ApplicationsApr 1, 200627 citations

On the power of quantum finite state automata

A. Kondacs, John Watrous

Annual Symposium on Foundations of Computer ScienceNov 22, 2002348 citations

arXiv:quant-ph/0703087

Determining the equivalence for 1-way quantum finite automata

Lvzhou Li, Daowen Qiu

Published Mar 11, 2007• 1 citation

arXiv HTML PDF

Abstract

{\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.

DOI: 10.48550/arxiv.quant-ph/0703087

Related papers

Decidability of the Equivalence of Multi-Letter Quantum Finite Automata

Daowen Qiu, Xiangfu Zou, Lvzhou Li +1 more

Multi-letter {\it quantum finite automata} (QFAs) were a quantum variant of classical {\it one-way multi-head finite automata} (J. Hromkovič, Acta Informatica 19 (1983) 377-384), and it has been shown that this new one-way QFAs (multi-letter QFAs) can accept with no error some regular languages $(a+b)^{*}b$ that are unacceptable by the previous one-way QFAs. In this paper, we study the decidability of the equivalence of multi-letter QFAs, and the main technical contributions are as follows: (1) We show that any two automata, a $k_{1}$ -letter QFA ${\cal A}_1$ and a $k_{2}$ -letter QFA ${\cal A}_2$ , over the same input alphabet $Σ$ are equivalent if and only if they are $(n^2m^{k-1}-m^{k-1}+k)$ -equivalent, where $m=|Σ|$ is the cardinality of $Σ$ , $k=\max(k_{1},k_{2})$ , and $n=n_{1}+n_{2}$ , with $n_{1}$ and $n_{2}$ being the numbers of states of ${\cal A}_{1}$ and ${\cal A}_{2}$ , respectively. When $k=1$ , we obtain the decidability of equivalence of measure-once QFAs in the literature. It is worth mentioning that our technical method is essentially different from that for the decidability of the case of single input alphabet (i.e., $m=1$ ). (2) However, if we determine the equivalence of multi-letter QFAs by checking all strings of length not more than $ n^2m^{k-1}-m^{k-1}+k$, then the worst time complexity is exponential, i.e., $O(n^6m^{n^2m^{k-1}-m^{k-1}+2k-1})$ . Therefore, we design a polynomial-time $O(m^{2k-1}n^{8}+km^kn^{6})$ algorithm for determining the equivalence of any two multi-letter QFAs. Here, the time complexity is concerning the number of states in the multi-letter QFAs, and $k$ is thought of as a constant.Multi-letter {\it quantum finite automata} (QFAs) were a quantum variant of classical {\it one-way multi-head finite automata} (J. Hromkovič, Acta Informatica 19 (1983) 377-384), and it has been shown that this new one-way QFAs (multi-letter QFAs) can accept with no error some regular languages $(a+b)^{*}b$ that are unacceptable by the previous one-way QFAs. In this paper, we study the decidability of the equivalence of multi-letter QFAs, and the main technical contributions are as follows: (1) We show that any two automata, a $k_{1}$-letter QFA ${\cal A}_1$ and a $k_{2}$-letter QFA ${\cal A}_2$, over the same input alphabet $Σ$ are equivalent if and only if they are $(n^2m^{k-1}-m^{k-1}+k)$-equivalent, where $m=|Σ|$ is the cardinality of $Σ$, $k=\max(k_{1},k_{2})$, and $n=n_{1}+n_{2}$, with $n_{1}$ and $n_{2}$ being the numbers of states of ${\cal A}_{1}$ and ${\cal A}_{2}$, respectively. When $k=1$, we obtain the decidability of equivalence of measure-once QFAs in the literature. It is worth mentioning that our technical method is essentially different from that for the decidability of the case of single input alphabet (i.e., $m=1$). (2) However, if we determine the equivalence of multi-letter QFAs by checking all strings of length not more than $ n^2m^{k-1}-m^{k-1}+k$, then the worst time complexity is exponential, i.e., $O(n^6m^{n^2m^{k-1}-m^{k-1}+2k-1})$. Therefore, we design a polynomial-time $O(m^{2k-1}n^{8}+km^kn^{6})$ algorithm for determining the equivalence of any two multi-letter QFAs. Here, the time complexity is concerning the number of states in the multi-letter QFAs, and $k$ is thought of as a constant.

arXiv:0812.1061Dec 5, 20084 citations

One-way quantum finite automata together with classical states: Equivalence and Minimization

Daowen Qiu, Paulo Mateus, Xiangfu Zou +1 more

One-way quantum finite automata (1QFA) proposed by Moore and Crutchfield and by Kondacs and Watrous accept only subsets of regular languages with bounded error. In this paper, we develop a new computing model of 1QFA, namely, one-way quantum finite automata together with classical states (1QFAC for short). In this model, a component of classical states is added, and the choice of unitary evolution of quantum states at each step is closely related to the current classical state. 1QFAC can accept all regular languages with no error, and in particular, 1QFAC can accept some languages with essentially less number of states than deterministic finite automata (DFA). The main technical results are as follows. (1) We prove that the set of languages accepted by 1QFAC with bounded error consists precisely of all regular languages. (2) We show that, for any prime number m ≥ 2, there exists a regular language L0(m) whose minimal DFA needs O(m) states and that can not be accepted by the 1QFA proposed by Moore and Crutchfield and by Kondacs and Watrous, but there exists 1QFAC accepting L0(m) with only constant classical states and O(log(m)) quantum basis states. Analogous results for multi-letter automata are also established. (3) By a bilinearization technique we prove that any two 1QFAC A1 and A2 are equivalent if and only if they are (k1n1) 2 + (k2n2) 2 − 1-equivalent, and there exists a polynomial-time O([(k1n1) 2 + (k2n2) 2]4) algorithm for determining their equivalence, where k1 and k2 are the numbers of classical states of A1 and A2, as well as n1 and n2 are the numbers of quantum basis states of A1 andA2, respectively. (4) We show that the minimization problem of 1QFAC is in EXPSPACE. As a corollary of this result, we obtain that the minimization problem of MO-1QFA is also in EXPSPACE. Finally, we draw some conclusions and point out open ∗Corresponding author. E-mail address: issqdw@mail.sysu.edu.cn (D. Qiu). †E-mail address: {paulo.mateus,amilcar.sernadas}@math.ist.utl.pt.One-way quantum finite automata (1QFA) proposed by Moore and Crutchfield and by Kondacs and Watrous accept only subsets of regular languages with bounded error. In this paper, we develop a new computing model of 1QFA, namely, one-way quantum finite automata together with classical states (1QFAC for short). In this model, a component of classical states is added, and the choice of unitary evolution of quantum states at each step is closely related to the current classical state. 1QFAC can accept all regular languages with no error, and in particular, 1QFAC can accept some languages with essentially less number of states than deterministic finite automata (DFA). The main technical results are as follows. (1) We prove that the set of languages accepted by 1QFAC with bounded error consists precisely of all regular languages. (2) We show that, for any prime number m ≥ 2, there exists a regular language L0(m) whose minimal DFA needs O(m) states and that can not be accepted by the 1QFA proposed by Moore and Crutchfield and by Kondacs and Watrous, but there exists 1QFAC accepting L0(m) with only constant classical states and O(log(m)) quantum basis states. Analogous results for multi-letter automata are also established. (3) By a bilinearization technique we prove that any two 1QFAC A1 and A2 are equivalent if and only if they are (k1n1) 2 + (k2n2) 2 − 1-equivalent, and there exists a polynomial-time O([(k1n1) 2 + (k2n2) 2]4) algorithm for determining their equivalence, where k1 and k2 are the numbers of classical states of A1 and A2, as well as n1 and n2 are the numbers of quantum basis states of A1 andA2, respectively. (4) We show that the minimization problem of 1QFAC is in EXPSPACE. As a corollary of this result, we obtain that the minimization problem of MO-1QFA is also in EXPSPACE. Finally, we draw some conclusions and point out open ∗Corresponding author. E-mail address: issqdw@mail.sysu.edu.cn (D. Qiu). †E-mail address: {paulo.mateus,amilcar.sernadas}@math.ist.utl.pt.

Sep 8, 20092 citations

On equivalence, languages equivalence and minimization of multi-letter and multi-letter measure-many quantum automata

Tianrong Lin

We first show that given a $k_1$ -letter quantum finite automata $\mathcal{A}_1$ and a $k_2$ -letter quantum finite automata $\mathcal{A}_2$ over the same input alphabet $Σ$ , they are equivalent if and only if they are $(n_1^2+n_2^2-1)|Σ|^{k-1}+k$ -equivalent where $n_1$ , $i=1,2$ , are the numbers of state in $\mathcal{A}_i$ respectively, and $k=\max\{k_1,k_2\}$ . By applying a method, due to the author, used to deal with the equivalence problem of {\it measure many one-way quantum finite automata}, we also show that a $k_1$ -letter measure many quantum finite automaton $\mathcal{A}_1$ and a $k_2$ -letter measure many quantum finite automaton $\mathcal{A}_2$ are equivalent if and only if they are $(n_1^2+n_2^2-1)|Σ|^{k-1}+k$ -equivalent where $n_i$ , $i=1,2$ , are the numbers of state in $\mathcal{A}_i$ respectively, and $k=\max\{k_1,k_2\}$ . Next, we study the language equivalence problem of those two kinds of quantum finite automata. We show that for $k$ -letter quantum finite automata, the non-strict cut-point language equivalence problem is undecidable, i.e., it is undecidable whether $L_{\geqλ}(\mathcal{A}_1)=L_{\geqλ}(\mathcal{A}_2)$ where $0<λ\leq 1$ and $\mathcal{A}_i$ are $k_i$ -letter quantum finite automata. Further, we show that both strict and non-strict cut-point language equivalence problem for $k$ -letter measure many quantum finite automata are undecidable. The direct consequences of the above outcomes are summarized in the paper. Finally, we comment on existing proofs about the minimization problem of one way quantum finite automata not only because we have been showing great interest in this kind of problem, which is very important in classical automata theory, but also due to that the problem itself, personally, is a challenge. This problem actually remains open.We first show that given a $k_1$-letter quantum finite automata $\mathcal{A}_1$ and a $k_2$-letter quantum finite automata $\mathcal{A}_2$ over the same input alphabet $Σ$, they are equivalent if and only if they are $(n_1^2+n_2^2-1)|Σ|^{k-1}+k$-equivalent where $n_1$, $i=1,2$, are the numbers of state in $\mathcal{A}_i$ respectively, and $k=\max\{k_1,k_2\}$. By applying a method, due to the author, used to deal with the equivalence problem of {\it measure many one-way quantum finite automata}, we also show that a $k_1$-letter measure many quantum finite automaton $\mathcal{A}_1$ and a $k_2$-letter measure many quantum finite automaton $\mathcal{A}_2$ are equivalent if and only if they are $(n_1^2+n_2^2-1)|Σ|^{k-1}+k$-equivalent where $n_i$, $i=1,2$, are the numbers of state in $\mathcal{A}_i$ respectively, and $k=\max\{k_1,k_2\}$. Next, we study the language equivalence problem of those two kinds of quantum finite automata. We show that for $k$-letter quantum finite automata, the non-strict cut-point language equivalence problem is undecidable, i.e., it is undecidable whether $L_{\geqλ}(\mathcal{A}_1)=L_{\geqλ}(\mathcal{A}_2)$ where $0<λ\leq 1$ and $\mathcal{A}_i$ are $k_i$-letter quantum finite automata. Further, we show that both strict and non-strict cut-point language equivalence problem for $k$-letter measure many quantum finite automata are undecidable. The direct consequences of the above outcomes are summarized in the paper. Finally, we comment on existing proofs about the minimization problem of one way quantum finite automata not only because we have been showing great interest in this kind of problem, which is very important in classical automata theory, but also due to that the problem itself, personally, is a challenge. This problem actually remains open.

arXiv:1203.0113Mar 1, 20120 citations

One-way quantum finite automata together with classical states

Daowen Qiu, Paulo Mateus, Xiangfu Zou +1 more

We show that there are quantum devices that accept all regular languages and that are exponentially more concise than deterministic finite automata (DFA). For this purpose, we introduce a new computing model of {\it one-way quantum finite automata} (1QFA), namely, {\it one-way quantum finite automata together with classical states} (1QFAC), which extends naturally both measure-only 1QFA and DFA and whose state complexity is upper-bounded by both. The original contributions of the paper are the following. First, we show that the set of languages accepted by 1QFAC with bounded error consists precisely of all regular languages. Second, we prove that 1QFAC are at most exponentially more concise than DFA. Third, we show that the previous bound is tight for families of regular languages that are not recognized by measure-once (RMO), measure-many (RMM) and multi-letter 1QFA. % More concretely we exhibit regular languages $L^0(m)$ for $m$ prime such that: (i) $L^0(m)$ cannot be recognized by measure-once, measure-many and multi-letter 1QFA; (ii) the minimal DFA that accepts $L^0(m)$ has $O(m)$ states; (iii) there is a 1QFAC with constant classical states and $O(\log(m))$ quantum basis that accepts $L^0(m)$ . Fourth, we give a polynomial-time algorithm for determining whether any two 1QFAC are equivalent. Finally, we show that state minimization of 1QFAC is decidable within EXPSPACE. We conclude the paper by posing some open problems.We show that there are quantum devices that accept all regular languages and that are exponentially more concise than deterministic finite automata (DFA). For this purpose, we introduce a new computing model of {\it one-way quantum finite automata} (1QFA), namely, {\it one-way quantum finite automata together with classical states} (1QFAC), which extends naturally both measure-only 1QFA and DFA and whose state complexity is upper-bounded by both. The original contributions of the paper are the following. First, we show that the set of languages accepted by 1QFAC with bounded error consists precisely of all regular languages. Second, we prove that 1QFAC are at most exponentially more concise than DFA. Third, we show that the previous bound is tight for families of regular languages that are not recognized by measure-once (RMO), measure-many (RMM) and multi-letter 1QFA. % More concretely we exhibit regular languages $L^0(m)$ for $m$ prime such that: (i) $L^0(m)$ cannot be recognized by measure-once, measure-many and multi-letter 1QFA; (ii) the minimal DFA that accepts $L^0(m)$ has $O(m)$ states; (iii) there is a 1QFAC with constant classical states and $O(\log(m))$ quantum basis that accepts $L^0(m)$. Fourth, we give a polynomial-time algorithm for determining whether any two 1QFAC are equivalent. Finally, we show that state minimization of 1QFAC is decidable within EXPSPACE. We conclude the paper by posing some open problems.

arXiv:0909.1428Sep 8, 20094 citations

Quantum finite automata with control language

Carlo Mereghetti, Beatrice Palano

Bertoni et al. introduced in Lect. Notes Comput. Sci. 2710 (2003) 1–20 a new model of 1-way quantum finite automaton (1qfa) called 1qfa with control language (1qfc). This model, whose recognizing power is exactly the class of regular languages, generalizes main models of 1qfa's proposed in the literature. Here, we investigate some properties of 1qfc's. In particular, we provide algorithms for constructing 1qfc's accepting the inverse homomorphic images and quotients of languages accepted by 1qfc's. Moreover, we give instances of binary regular languages on which 1qfc's are proved to be more succinct (i.e. , to have less states) than the corresponding classical (deterministic) automata.Bertoni et al. introduced in Lect. Notes Comput. Sci. 2710 (2003) 1–20 a new model of 1-way quantum finite automaton (1qfa) called 1qfa with control language (1qfc). This model, whose recognizing power is exactly the class of regular languages, generalizes main models of 1qfa's proposed in the literature. Here, we investigate some properties of 1qfc's. In particular, we provide algorithms for constructing 1qfc's accepting the inverse homomorphic images and quotients of languages accepted by 1qfc's. Moreover, we give instances of binary regular languages on which 1qfc's are proved to be more succinct (i.e. , to have less states) than the corresponding classical (deterministic) automata.

RAIRO - Theoretical Informatics and ApplicationsApr 1, 200627 citations

On the power of quantum finite state automata

A. Kondacs, John Watrous

In this paper, we introduce 1-way and 2-way quantum finite state automata (1qfa's and 2qfa's), which are the quantum analogues of deterministic, nondeterministic and probabilistic 1-way and 2-way finite state automata. We prove the following facts regarding 2qfa's. 1. For any /spl epsiv/>0, there is a 2qfa M which recognizes the non-regular language L={a/sup m/b/sup m/|m/spl ges/1} with (one-sided) error bounded by E, and which halts in linear time. Specifically, M accepts any string in L with probability 1 and rejects any string not in L with probability at least 1-/spl epsiv/. 2. For every regular language L, there is a reversible (and hence quantum) 2-way finite state automaton which recognizes L and which runs in linear time. In fact, it is possible to define 2qfar's which recognize the non-context-free language {a/sup m/b/sup m/c/sup m/|m/spl ges/1}, based on the same technique used for 1. Consequently, the class of languages recognized by linear time, bounded error 2qfa's properly includes the regular languages. Since it is known that 2-way deterministic, nondeterministic and polynomial expected time, bounded error probabilistic finite automata can recognize only regular languages, it follows that 2qfa's are strictly more powerful than these "classical" models. In the case of 1-way automata, the situation is reversed. We prove that the class of languages recognizable by bounded error 1qfa's is properly contained in the class of regular languages.In this paper, we introduce 1-way and 2-way quantum finite state automata (1qfa's and 2qfa's), which are the quantum analogues of deterministic, nondeterministic and probabilistic 1-way and 2-way finite state automata. We prove the following facts regarding 2qfa's. 1. For any /spl epsiv/>0, there is a 2qfa M which recognizes the non-regular language L={a/sup m/b/sup m/|m/spl ges/1} with (one-sided) error bounded by E, and which halts in linear time. Specifically, M accepts any string in L with probability 1 and rejects any string not in L with probability at least 1-/spl epsiv/. 2. For every regular language L, there is a reversible (and hence quantum) 2-way finite state automaton which recognizes L and which runs in linear time. In fact, it is possible to define 2qfar's which recognize the non-context-free language {a/sup m/b/sup m/c/sup m/|m/spl ges/1}, based on the same technique used for 1. Consequently, the class of languages recognized by linear time, bounded error 2qfa's properly includes the regular languages. Since it is known that 2-way deterministic, nondeterministic and polynomial expected time, bounded error probabilistic finite automata can recognize only regular languages, it follows that 2qfa's are strictly more powerful than these "classical" models. In the case of 1-way automata, the situation is reversed. We prove that the class of languages recognizable by bounded error 1qfa's is properly contained in the class of regular languages.

Annual Symposium on Foundations of Computer ScienceNov 22, 2002348 citations

{\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.

(a+b)^{*}b

that are unacceptable by the previous one-way QFAs. In this paper, we study the decidability of the equivalence of multi-letter QFAs, and the main technical contributions are as follows: (1) We show that any two automata, a

k_{1}

-letter QFA

{\cal A}_1

and a

k_{2}

-letter QFA

{\cal A}_2

, over the same input alphabet

Σ

are equivalent if and only if they are

(n^2m^{k-1}-m^{k-1}+k)

-equivalent, where

m=|Σ|

is the cardinality of

Σ

k=\max(k_{1},k_{2})

, and

n=n_{1}+n_{2}

, with

n_{1}

and

n_{2}

being the numbers of states of

{\cal A}_{1}

and

{\cal A}_{2}

, respectively. When

k=1

, we obtain the decidability of equivalence of measure-once QFAs in the literature. It is worth mentioning that our technical method is essentially different from that for the decidability of the case of single input alphabet (i.e.,

m=1

). (2) However, if we determine the equivalence of multi-letter QFAs by checking all strings of length not more than $ n^2m^{k-1}-m^{k-1}+k$, then the worst time complexity is exponential, i.e.,

O(n^6m^{n^2m^{k-1}-m^{k-1}+2k-1})

. Therefore, we design a polynomial-time

O(m^{2k-1}n^{8}+km^kn^{6})

algorithm for determining the equivalence of any two multi-letter QFAs. Here, the time complexity is concerning the number of states in the multi-letter QFAs, and

k

is thought of as a constant.

We first show that given a

k_1

-letter quantum finite automata

\mathcal{A}_1

and a

k_2

-letter quantum finite automata

\mathcal{A}_2

over the same input alphabet

Σ

, they are equivalent if and only if they are

(n_1^2+n_2^2-1)|Σ|^{k-1}+k

-equivalent where

n_1

i=1,2

, are the numbers of state in

\mathcal{A}_i

respectively, and

k=\max\{k_1,k_2\}

. By applying a method, due to the author, used to deal with the equivalence problem of {\it measure many one-way quantum finite automata}, we also show that a

k_1

-letter measure many quantum finite automaton

\mathcal{A}_1

and a

k_2

-letter measure many quantum finite automaton

\mathcal{A}_2

are equivalent if and only if they are

(n_1^2+n_2^2-1)|Σ|^{k-1}+k

-equivalent where

n_i

i=1,2

, are the numbers of state in

\mathcal{A}_i

respectively, and

k=\max\{k_1,k_2\}

. Next, we study the language equivalence problem of those two kinds of quantum finite automata. We show that for

k

-letter quantum finite automata, the non-strict cut-point language equivalence problem is undecidable, i.e., it is undecidable whether

L_{\geqλ}(\mathcal{A}_1)=L_{\geqλ}(\mathcal{A}_2)

where

0<λ\leq 1

and

\mathcal{A}_i

are

k_i

-letter quantum finite automata. Further, we show that both strict and non-strict cut-point language equivalence problem for

k

-letter measure many quantum finite automata are undecidable. The direct consequences of the above outcomes are summarized in the paper. Finally, we comment on existing proofs about the minimization problem of one way quantum finite automata not only because we have been showing great interest in this kind of problem, which is very important in classical automata theory, but also due to that the problem itself, personally, is a challenge. This problem actually remains open.

L^0(m)

for

m

prime such that: (i)

L^0(m)

cannot be recognized by measure-once, measure-many and multi-letter 1QFA; (ii) the minimal DFA that accepts

L^0(m)

has

O(m)

states; (iii) there is a 1QFAC with constant classical states and

O(\log(m))

quantum basis that accepts

L^0(m)

. Fourth, we give a polynomial-time algorithm for determining whether any two 1QFAC are equivalent. Finally, we show that state minimization of 1QFAC is decidable within EXPSPACE. We conclude the paper by posing some open problems.