Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1203.0113

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

Tianrong Lin

Published Mar 1, 2012• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1203.0113

Related papers

On equivalence and emptiness problems of multi-letter (measure many) quantum finite automata

Tianrong Lin

In this paper, we study some decision problems both for {\it multi-letter quantum finite automata} and {\it measure many multi-letter quantum finite automata}. We first show that given a $k_1$-letter quantum finite automaton $\mathcal{A}_1$ and a $k_2$-letter quantum finite automaton $\mathcal{A}_2$ over the same input alphabet $\Sigma$, they are equivalent if and only if they are $(n_1^2+n_2^2-1)|\Sigma|^{k-1}+k$-equivalent where $n_i$, $i=1,2$, are the number of states 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)|\Sigma|^{k-1}+k$-equivalent where $n_i$, $i=1,2$, are the number of states in $\mathcal{A}_i$ respectively, and $k=\max\{k_1,k_2\}$. Next, we study the emptiness problem of those two kinds of quantum finite automata. We show that whether the language recognized by a $k$-letter quantum finite automaton with non-strict cut-point is empty is undecidable, but we leave open the emptiness of language reorganized by a $k$-letter quantum finite automaton with strict cutpoint. We also show that whether the languages recognized by a $k$-letter measure many quantum finite automaton with both nonstrict and strict cutpoints are undecidable. And the direct consequences of the above outcomes are summarized in the paper.

•Mar 1, 2012•0 citations

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.

arXiv:0812.1061•Dec 5, 2008•4 citations

Some results on equivalence of multi-letter quantum finite automata

Tianrong Lin

Two quantum finite automata are equivalent if for all input string $ω$ over the input alphabet the two automata accept $ω$ with equal probability. In [Theoret. Comput. Sci. 410 (2009) 3006-3017], it was shown that a $k_1$-letter QFA $\mathcal{A}_1$ and a $k_2$-letter QFA $\mathcal{A}_2$ over $Σ=\{σ\}$, are equivalent if and only if they are $(n_1+n_2)^4+k-1$-equivalent where $n_i$ is the number of states of $\mathcal{A}_i$, $i=1,2$, and $k=\max\{k_1,k_2\}$. In this letter, we improve the above upper-bound to $(n_1^2+n_2^2-1)+k$. This also answers an open problem of Qiu et al. [Acta Informatica 48 (2011) 271-290]. Further, we show that, in the case of $Σ=\{σ_1,...,σ_t\}$ with $2\leq t<\infty$, there exists an integer $z$ such that $\mathcal{A}_1$ and $\mathcal{A}_2$ are equivalent if and only if they satisfy $z$-equivalent.

arXiv:1106.5223•Jun 26, 2011•0 citations

Note on equivalence of cutpoint languages recognized by measure many quantum finite automata

Tianrong Lin

This note revisits the equivalence of languages recognized by measure many one way quantum finite automata with non/strict cutpoint. The main contributions are as follows: \begin{enumerate}[(1)] \item {We provide an additional proof of the undecidability of non/strict emptiness of measure many one way quantum finite automata;} \item {By the undecidability of non/strict emptiness of measure many one way quantum finite automata, we show that the equivalence of languages recognized by measure many one way quantum finite automata with non/strict cutpoint is undecidable, implying the undecidability of containment problem of measure many one way quantum finite automata} \end{enumerate}

•Aug 15, 2013•2 citations

Undecidability of MM-QFAs Language Equivalence Problem

Tianrong Lin

Let $L_{>λ}(\mathcal{A})$ and $L_{\geqλ}(\mathcal{A})$ be the languages recognized by {\em measure many 1-way quantum finite automata (MM-QFA)} (or,{\em enhanced 1-way quantum finite automata(EQFA)}) $\mathcal{A}$ with strict and non-strict cut-point $λ$, respectively. We consider the language equivalence problem and show the following 1. both strict and non-strict language equivalence are undecidable; 2. we provide an another proof of the undecidability of non-strict and strict emptiness of MM-QFA and EQFA, and then reducing the language equivalence problem to emptiness problem; 3. lastly, we obtain some other properties which can be derived from the above results.

arXiv:1308.3301•Aug 15, 2013•1 citation

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.

•Sep 8, 2009•2 citations
We first show that given a k1k_1k1​-letter quantum finite automata A1\mathcal{A}_1A1​ and a k2k_2k2​-letter quantum finite automata A2\mathcal{A}_2A2​ over the same input alphabet ΣΣΣ, they are equivalent if and only if they are (n12+n22−1)∣Σ∣k−1+k(n_1^2+n_2^2-1)|Σ|^{k-1}+k(n12​+n22​−1)∣Σ∣k−1+k-equivalent where n1n_1n1​, i=1,2i=1,2i=1,2, are the numbers of state in Ai\mathcal{A}_iAi​ respectively, and k=max⁡{k1,k2}k=\max\{k_1,k_2\}k=max{k1​,k2​}. 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 k1k_1k1​-letter measure many quantum finite automaton A1\mathcal{A}_1A1​ and a k2k_2k2​-letter measure many quantum finite automaton A2\mathcal{A}_2A2​ are equivalent if and only if they are (n12+n22−1)∣Σ∣k−1+k(n_1^2+n_2^2-1)|Σ|^{k-1}+k(n12​+n22​−1)∣Σ∣k−1+k-equivalent where nin_ini​, i=1,2i=1,2i=1,2, are the numbers of state in Ai\mathcal{A}_iAi​ respectively, and k=max⁡{k1,k2}k=\max\{k_1,k_2\}k=max{k1​,k2​}. Next, we study the language equivalence problem of those two kinds of quantum finite automata. We show that for kkk-letter quantum finite automata, the non-strict cut-point language equivalence problem is undecidable, i.e., it is undecidable whether L≥λ(A1)=L≥λ(A2)L_{\geqλ}(\mathcal{A}_1)=L_{\geqλ}(\mathcal{A}_2)L≥λ​(A1​)=L≥λ​(A2​) where 0<λ≤10<λ\leq 10<λ≤1 and Ai\mathcal{A}_iAi​ are kik_iki​-letter quantum finite automata. Further, we show that both strict and non-strict cut-point language equivalence problem for kkk-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.
In this paper, we study some decision problems both for {\it multi-letter quantum finite automata} and {\it measure many multi-letter quantum finite automata}. We first show that given a k1k_1k1​-letter quantum finite automaton A1\mathcal{A}_1A1​ and a k2k_2k2​-letter quantum finite automaton A2\mathcal{A}_2A2​ over the same input alphabet Σ\SigmaΣ, they are equivalent if and only if they are (n12+n22−1)∣Σ∣k−1+k(n_1^2+n_2^2-1)|\Sigma|^{k-1}+k(n12​+n22​−1)∣Σ∣k−1+k-equivalent where nin_ini​, i=1,2i=1,2i=1,2, are the number of states in Ai\mathcal{A}_iAi​ respectively, and k=max⁡{k1,k2}k=\max\{k_1,k_2\}k=max{k1​,k2​}. 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 k1k_1k1​-letter measure many quantum finite automaton A1\mathcal{A}_1A1​ and a k2k_2k2​-letter measure many quantum finite automaton A2\mathcal{A}_2A2​ are equivalent if and only if they are (n12+n22−1)∣Σ∣k−1+k(n_1^2+n_2^2-1)|\Sigma|^{k-1}+k(n12​+n22​−1)∣Σ∣k−1+k-equivalent where nin_ini​, i=1,2i=1,2i=1,2, are the number of states in Ai\mathcal{A}_iAi​ respectively, and k=max⁡{k1,k2}k=\max\{k_1,k_2\}k=max{k1​,k2​}. Next, we study the emptiness problem of those two kinds of quantum finite automata. We show that whether the language recognized by a kkk-letter quantum finite automaton with non-strict cut-point is empty is undecidable, but we leave open the emptiness of language reorganized by a kkk-letter quantum finite automaton with strict cutpoint. We also show that whether the languages recognized by a kkk-letter measure many quantum finite automaton with both nonstrict and strict cutpoints are undecidable. And the direct consequences of the above outcomes are summarized in the paper.
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(a+b)^{*}b(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 k1k_{1}k1​-letter QFA A1{\cal A}_1A1​ and a k2k_{2}k2​-letter QFA A2{\cal A}_2A2​, over the same input alphabet ΣΣΣ are equivalent if and only if they are (n2mk−1−mk−1+k)(n^2m^{k-1}-m^{k-1}+k)(n2mk−1−mk−1+k)-equivalent, where m=∣Σ∣m=|Σ|m=∣Σ∣ is the cardinality of ΣΣΣ, k=max⁡(k1,k2)k=\max(k_{1},k_{2})k=max(k1​,k2​), and n=n1+n2n=n_{1}+n_{2}n=n1​+n2​, with n1n_{1}n1​ and n2n_{2}n2​ being the numbers of states of A1{\cal A}_{1}A1​ and A2{\cal A}_{2}A2​, respectively. When k=1k=1k=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=1m=1m=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(n6mn2mk−1−mk−1+2k−1)O(n^6m^{n^2m^{k-1}-m^{k-1}+2k-1})O(n6mn2mk−1−mk−1+2k−1). Therefore, we design a polynomial-time O(m2k−1n8+kmkn6)O(m^{2k-1}n^{8}+km^kn^{6})O(m2k−1n8+kmkn6) 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 kkk is thought of as a constant.
Two quantum finite automata are equivalent if for all input string ωωω over the input alphabet the two automata accept ωωω with equal probability. In [Theoret. Comput. Sci. 410 (2009) 3006-3017], it was shown that a k1k_1k1​-letter QFA A1\mathcal{A}_1A1​ and a k2k_2k2​-letter QFA A2\mathcal{A}_2A2​ over Σ={σ}Σ=\{σ\}Σ={σ}, are equivalent if and only if they are (n1+n2)4+k−1(n_1+n_2)^4+k-1(n1​+n2​)4+k−1-equivalent where nin_ini​ is the number of states of Ai\mathcal{A}_iAi​, i=1,2i=1,2i=1,2, and k=max⁡{k1,k2}k=\max\{k_1,k_2\}k=max{k1​,k2​}. In this letter, we improve the above upper-bound to (n12+n22−1)+k(n_1^2+n_2^2-1)+k(n12​+n22​−1)+k. This also answers an open problem of Qiu et al. [Acta Informatica 48 (2011) 271-290]. Further, we show that, in the case of Σ={σ1,...,σt}Σ=\{σ_1,...,σ_t\}Σ={σ1​,...,σt​} with 2≤t<∞2\leq t<\infty2≤t<∞, there exists an integer zzz such that A1\mathcal{A}_1A1​ and A2\mathcal{A}_2A2​ are equivalent if and only if they satisfy zzz-equivalent.
This note revisits the equivalence of languages recognized by measure many one way quantum finite automata with non/strict cutpoint. The main contributions are as follows: \begin{enumerate}[(1)] \item {We provide an additional proof of the undecidability of non/strict emptiness of measure many one way quantum finite automata;} \item {By the undecidability of non/strict emptiness of measure many one way quantum finite automata, we show that the equivalence of languages recognized by measure many one way quantum finite automata with non/strict cutpoint is undecidable, implying the undecidability of containment problem of measure many one way quantum finite automata} \end{enumerate}
Let L>λ(A)L_{>λ}(\mathcal{A})L>λ​(A) and L≥λ(A)L_{\geqλ}(\mathcal{A})L≥λ​(A) be the languages recognized by {\em measure many 1-way quantum finite automata (MM-QFA)} (or,{\em enhanced 1-way quantum finite automata(EQFA)}) A\mathcal{A}A with strict and non-strict cut-point λλλ, respectively. We consider the language equivalence problem and show the following 1. both strict and non-strict language equivalence are undecidable; 2. we provide an another proof of the undecidability of non-strict and strict emptiness of MM-QFA and EQFA, and then reducing the language equivalence problem to emptiness problem; 3. lastly, we obtain some other properties which can be derived from the above results.
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.