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

The Emptiness Problem for Quantum Finite Automata with Classical States

Jyun-Ao Lin, Patrick Totzke, Yun Chen Tsai, Di-De Yen

Published Aug 29, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2608.29319

Related papers

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•81 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

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

Two-way nondeterministic finite automata with quantum and classical states and their limits

Jingnan Xie, Ching-Sheng Lin, Harry B. Hunt

Two-way finite automata with quantum and classical states (2QCFA’s), introduced by Ambainis and Watrous, extend deterministic two-way finite automata with a constant-size quantum register and provide a natural hybrid model of computation. In this paper, we introduce two-way nondeterministic finite automata with quantum and classical states (2QCNFA’s), extending this framework to the nondeterministic setting. We show that 2QCNFA’s are closed under union, intersection, and marked concatenation, and that they can recognize certain comparison languages whose status for 2QCFA’s remains open. We further initiate the study of decision problems for this model by proving that 2QCNFA’s can recognize the set of invalid computations of a deterministic Turing machine, which implies that the universality problem is undecidable. In addition, we investigate descriptional complexity, showing that there is no approximation algorithm for minimization between 2QCNFA’s and classical models such as DFA’s and context-free grammars, and that the corresponding trade-offs are non-recursive.

Information and Computation•Jun 25, 2026•0 citations

Bounded Quantum Regular Language Generator

YoungMin Kwon, Gul Agha

We develop a quantum algorithm to verify the correctness of systems modeled by nondeterministic finite-state automata-a problem that is computationally intractable on conventional computers. Specifically, our algorithm solves the language containment problem in three steps. First, we translate a nondeterministic finite-state automaton into a quantum finite state automaton (QFA) circuit. Second, the QFA is embedded into a larger circuit which generates a superposed set of all bounded strings that are marked to indicate whether they are accepted or not. Finally, we amplify the amplitudes of accepted strings so that they are measured more frequently. The last step may be done either by using Grover's algorithm, or by using FnR, a custom algorithm that we have developed for the cases where Grover's algorithm is not effective. Our work represents the first proposal to apply quantum computing to the problem of verifying conventional systems; our approach would facilitate software verification, program analysis, protocol design, and verification of circuits, among other applications.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•2 citations

On the class of languages recognizable by 1-way quantum finite automata

Andris Ambainis, Arnolds Ķikusts, Māris Valdats

It is an open problem to characterize the class of languages recognized by quantum finite automata (QFA). We examine some necessary and some sufficient conditions for a (regular) language to be recognizable by a QFA. For a subclass of regular languages we get a condition which is necessary and sufficient. Also, we prove that the class of languages recognizable by a QFA is not closed under union or any other binary Boolean operation where both arguments are significant.

arXiv:quant-ph/0009004•Sep 1, 2000•10 citations
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.
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.
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.
Two-way finite automata with quantum and classical states (2QCFA’s), introduced by Ambainis and Watrous, extend deterministic two-way finite automata with a constant-size quantum register and provide a natural hybrid model of computation. In this paper, we introduce two-way nondeterministic finite automata with quantum and classical states (2QCNFA’s), extending this framework to the nondeterministic setting. We show that 2QCNFA’s are closed under union, intersection, and marked concatenation, and that they can recognize certain comparison languages whose status for 2QCFA’s remains open. We further initiate the study of decision problems for this model by proving that 2QCNFA’s can recognize the set of invalid computations of a deterministic Turing machine, which implies that the universality problem is undecidable. In addition, we investigate descriptional complexity, showing that there is no approximation algorithm for minimization between 2QCNFA’s and classical models such as DFA’s and context-free grammars, and that the corresponding trade-offs are non-recursive.
We develop a quantum algorithm to verify the correctness of systems modeled by nondeterministic finite-state automata-a problem that is computationally intractable on conventional computers. Specifically, our algorithm solves the language containment problem in three steps. First, we translate a nondeterministic finite-state automaton into a quantum finite state automaton (QFA) circuit. Second, the QFA is embedded into a larger circuit which generates a superposed set of all bounded strings that are marked to indicate whether they are accepted or not. Finally, we amplify the amplitudes of accepted strings so that they are measured more frequently. The last step may be done either by using Grover's algorithm, or by using FnR, a custom algorithm that we have developed for the cases where Grover's algorithm is not effective. Our work represents the first proposal to apply quantum computing to the problem of verifying conventional systems; our approach would facilitate software verification, program analysis, protocol design, and verification of circuits, among other applications.