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:1106.5223

Some results on equivalence of multi-letter quantum finite automata

Tianrong Lin

Published Jun 26, 2011• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1106.5223

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.

arXiv:0812.1061•Dec 5, 2008•4 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.

arXiv:1203.0113•Mar 1, 2012•0 citations

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

Determining the equivalence for 1-way quantum finite automata

Lvzhou Li, Daowen Qiu

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.

arXiv:quant-ph/0703087•Mar 11, 2007•1 citation

A small 1-way quantum finite automaton

Arnolds Ķikusts

We study 1-way quantum finite automata (QFAs) and compare them with their classical counterparts. We show that 1-way QFAs can be very space efficient. We construct a 1-way QFAs that are quadratically smaller than any equivalent deterministic finite automata and give the correct answer with a large probability by recognizing the languages in a two letter alphabet "the number of the letters a and the number of the letters b are divisible by n".

arXiv:quant-ph/9810065•Oct 22, 1998•8 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.

•Sep 8, 2009•2 citations
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.
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.
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.
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 A1{\cal A}_1A1​ and A2{\cal A}_2A2​ with control languages (regular languages) L1{\cal L}_1L1​ and L2{\cal L}_2L2​, respectively, are equivalent if and only if they are (c1n12+c2n22−1)(c_1n_1^2+c_2n_2^2-1)(c1​n12​+c2​n22​−1)-equivalent. Furthermore, if L1{\cal L}_1L1​ and L2{\cal L}_2L2​ are given in the form of DFAs, with m1m_1m1​ and m2m_2m2​ states, respectively, then there exists a polynomial-time algorithm running in time O((m1n12+m2n22)4)O ((m_1n_1^2+m_2n_2^2)^4)O((m1​n12​+m2​n22​)4) that takes as input A1{\cal A}_1A1​ and A2{\cal A}_2A2​ and determines whether they are equivalent. \item[(ii)] Two MM-1QFAs A1{\cal A}_1A1​ and A2{\cal A}_2A2​ with n1n_1n1​ and n2n_2n2​ states, respectively, are equivalent if and only if they are (3n12+3n22−1)(3n_1^2+3n_2^2-1)(3n12​+3n22​−1)-equivalent. Furthermore, there is a polynomial-time algorithm running in time O((3n12+3n22)4)O ((3n_1^2+3n_2^2)^4)O((3n12​+3n22​)4) that takes as input A1{\cal A}_1A1​ and A2{\cal A}_2A2​ and determines whether A1{\cal A}_1A1​ and A2{\cal A}_2A2​ are equivalent.
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.