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

Emptiness and equivalence of language on measure many quantum automata

Tianrong Lin

Published Aug 15, 2013• 0 citations
arXivHTMLPDF

Abstract

Let $L_{>\lambda}(\mathcal{A})$ and $L_{\geq\lambda}(\mathcal{A})$ be the languages recognized by {\em measure many 1-way quantum finite automata (MMQFA)} (or,{\em enhanced 1-way quantum finite automata(EQFA)}) $\mathcal{A}$ with strict, resp. non-strict cut-point $\lambda$. We consider the languages equivalence problem, showing that \begin{itemize} \item {both strict and non-strict languages equivalence are undecidable;} \item {to do this, we provide an additional proof of the undecidability of non-strict and strict emptiness of MMQFA(EQFA), and then reducing the languages equivalence problem to emptiness problem;} \item{Finally, some other Propositions derived from the above results are collected.} \end{itemize}

Related papers

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

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

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

The Emptiness Problem for Quantum Finite Automata with Classical States

Jyun-Ao Lin, Patrick Totzke, Yun Chen Tsai +1 more

Quantum Finite Automata with Classical states (QFACs) are nondeterministic finite automata over a finite alphabet of quantum operations. We study expressiveness of this model on finite words and the corresponding emptiness problem. We show that regular languages are incomparable with those definable by Quantum Finite Automata (QFAs) and that both are strictly subsumed by QFAC-definable languages. We show that the emptiness problem for a QFAC can be reduced to the emptiness of the language intersection of a QFA and a finite automaton. This intersection is known to be decidable for strict thresholds but undecidable for non-strict cases. Furthermore, we consider the problem for flat QFACs, a restriction where the underlying automata contain no nested loops, and relate it to the higher-dimensional orbit problem, a long-standing open challenge in dynamical systems. Finally, we propose a sound and semi-complete witness searching procedure to verify the non-emptiness of one-loop QFACs, which are sufficiently expressive to represent some prominent quantum algorithms, such as Grover's search and quantum random walks.

arXiv:2608.29319•Aug 29, 2026•0 citations

Decidable and Undecidable Problems about Quantum Automata

Vincent D. Blondel, Emmanuel Jeandel, Pascal Koiran +1 more

We study the following decision problem: is the language recognized by a quantum finite automaton empty or nonempty? We prove that this problem is decidable or undecidable depending on whether recognition is defined by strict or nonstrict thresholds. This result is in contrast with the corresponding situation for probabilistic finite automata, for which it is known that strict andnonstrict thresholds both lead to undecidable problems.

arXiv:quant-ph/0304082•SIAM Journal on Computing•Jan 1, 2005•76 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.

arXiv:0909.1428•Sep 8, 2009•4 citations
Let L>λ(A)L_{>\lambda}(\mathcal{A})L>λ​(A) and L≥λ(A)L_{\geq\lambda}(\mathcal{A})L≥λ​(A) be the languages recognized by {\em measure many 1-way quantum finite automata (MMQFA)} (or,{\em enhanced 1-way quantum finite automata(EQFA)}) A\mathcal{A}A with strict, resp. non-strict cut-point λ\lambdaλ. We consider the languages equivalence problem, showing that \begin{itemize} \item {both strict and non-strict languages equivalence are undecidable;} \item {to do this, we provide an additional proof of the undecidability of non-strict and strict emptiness of MMQFA(EQFA), and then reducing the languages equivalence problem to emptiness problem;} \item{Finally, some other Propositions derived from the above results are collected.} \end{itemize}
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}
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.
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.
Quantum Finite Automata with Classical states (QFACs) are nondeterministic finite automata over a finite alphabet of quantum operations. We study expressiveness of this model on finite words and the corresponding emptiness problem. We show that regular languages are incomparable with those definable by Quantum Finite Automata (QFAs) and that both are strictly subsumed by QFAC-definable languages. We show that the emptiness problem for a QFAC can be reduced to the emptiness of the language intersection of a QFA and a finite automaton. This intersection is known to be decidable for strict thresholds but undecidable for non-strict cases. Furthermore, we consider the problem for flat QFACs, a restriction where the underlying automata contain no nested loops, and relate it to the higher-dimensional orbit problem, a long-standing open challenge in dynamical systems. Finally, we propose a sound and semi-complete witness searching procedure to verify the non-emptiness of one-loop QFACs, which are sufficiently expressive to represent some prominent quantum algorithms, such as Grover's search and quantum random walks.
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 L0(m)L^0(m)L0(m) for mmm prime such that: (i) L0(m)L^0(m)L0(m) cannot be recognized by measure-once, measure-many and multi-letter 1QFA; (ii) the minimal DFA that accepts L0(m)L^0(m)L0(m) has O(m)O(m)O(m) states; (iii) there is a 1QFAC with constant classical states and O(log⁡(m))O(\log(m))O(log(m)) quantum basis that accepts L0(m)L^0(m)L0(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.