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

Applied Sciences

Unary Quantum Finite State Automata with Control Language

Carlo Mereghetti, Beatrice Palano, Priscilla Raucci

Published Feb 12, 2024• 5 citations
Publisher

Abstract

We study quantum finite automata with control language (qfcs), a theoretical model for finite memory hybrid systems coupling a classical computational framework with a quantum component. We constructively show how to simulate measure-once, measure-many, reversible, and Latvian qfas by qfcs, emphasizing the size cost of such simulations. Next, we prove the decidability of testing the periodicity of the stochastic event induced by a given qfc. Thanks to our qfa simulations, we can extend such a decidability result to measure-once, measure-many, reversible, and Latvian qfas as well. Finally, we focus on comparing the size efficiency of quantum and classical finite state automata on unary regular language recognition. We show that unary regular languages can be recognized by isolated cut point qfcs for which the size is generally quadratically smaller than the size of equivalent dfas.

DOI
10.3390/app14041490

Related papers

Latvian Quantum Finite State Automata for Unary Languages

Carlo Mereghetti, Beatrice Palano, Priscilla Raucci

We design Latvian quantum finite state automata (LQFAs for short) recognizing unary regular languages with isolated cut point 1 2 .From an architectural point of view, we combine two LQFAs recognizing with isolated cut point, respectively, the finite part and the ultimately periodic part of any given unary regular language L. In both modules, we use a component addressed in the literature and here suitably adapted to the unary case, to discriminate strings on the basis of their length.The number of basis states and the isolation around the cut point of the resulting LQFA for L exponentially depends on the size of the minimal deterministic finite state automaton for L.

arXiv:2309.08720•Electronic Proceedings in Theoretical Computer Science•Sep 13, 2023•1 citation

Latvian Quantum Finite State Automata for Unary Languages

Carlo Mereghetti, Beatrice Palano, Priscilla Raucci

We design Latvian quantum finite state automata (lqfas) recognizing unary regular languages with isolated cut point [Formula: see text]. From an architectural viewpoint, we suitably combine two lqfas recognizing with isolated cut point, respectively, the finite part and the ultimately periodic part any given unary regular language [Formula: see text] consists of. In particular, both these lqfas incorporate a sub-module discriminating strings on the basis of their length. Both the number of basis states and the isolation around the cut point of the resulting lqfa for [Formula: see text] exponentially depend on the size of the minimal deterministic finite state automaton for [Formula: see text]. Moreover, the recognition of [Formula: see text] tends to becoming deterministic as the number of the basis states employed in the length-discriminating sub-module grows.

International Journal of Foundations of Computer Science•Oct 19, 2024•0 citations

Quantum Automata and Periodic Events

Carlo Mereghetti, Beatrice Palano

We study the phenomenon of periodicity on quantum automata from three points of view. First, we provide an efficient algorithm for testing the periodicity of stochastic events induced by measure-once one-way unary quantum automata (1qfa's). Second, we design an algorithm for the synthesis of succinct unary 1qfa's inducing periodic events. To evaluate the size of the resulting 1qfa's, we relate the number of states of a minimal 1qfa inducing a linear approximation of a periodic event p to the harmonic structure of p. Next, we study the complexity of our synthesis algorithm. Third, we apply our synthesis algorithm for building succinct 1qfa's that accept unary periodic languages. We also prove a lower bound on the size of 1qfa's accepting unary periodic languages.

Mathematics, computing, language, and life•Oct 1, 2010•2 citations

On the Size of One-way Quantum Finite Automata with Periodic Behaviors

Carlo Mereghetti, Beatrice Palano

We show that, for any stochastic event p of period n, there exists a measure-once one-way quantum finite automaton (1qfa) with at most states inducing the event ap+b, for constants a>0, b ≥ 0, satisfying a+b ≥ 1. This fact is proved by designing an algorithm which constructs the desired 1qfa in polynomial time. As a consequence, we get that any periodic language of period n can be accepted with isolated cut point by a 1qfa with no more than states. Our results give added evidence of the strength of measure-once 1qfa's with respect to classical automata.

RAIRO - Theoretical Informatics and Applications•Jul 1, 2002•20 citations

Applications of algebraic automata theory to quantum finite automata

Mark Mercer

The computational model of Quantum Finite Automata has been introduced by multiple authors (e.g. [38, 44]) with some variations in definition. The objective of this thesis is to understand what class of languages can be recognized by these different variations, and how many states are required. We begin by showing that we can use algebraic automata theory to characterize the language recognition power of QFAs. Algebraic automata theory associates to each language a canonical syntactic monoid, and the algebraic structure of this monoid becomes a meaningful parameter in describing language classes. We show that the class of languages recognized by Latvian QFAs [3] corresponds exactly to boolean combinations of languages recognized by Brodsky and Pippenger's QFA model [20], which correspond exactly to those languages whose syntactic monoid is in the class BG. Known results give us a decision procedure for testing membership in this language class. We also use algebraic automata theory to give nearly tight upper and lower bounds on the class of languages recognized by Brodsky and Pippenger's QFAs. We then extend a number of lower bound techniques known for Kondacs and Watrous' 1-way QFA model to Nayak's Generalized QFA. Both of these models are related in that they are permitted to halt before reading the entire input, allowing them to recognize certain languages whose syntactic monoid lies outside of BG. Finally, we investigate the question of QFA succinctness. It is known that QFAs can recognize some languages using exponentially fewer states compared to deterministic finite automata. We extend results from [16] to show that the word problem over abelian groups has this property. We also give example of interesting noncommutative languages with this property.

•Jan 1, 2007•3 citations

A Framework for Quantum Finite-State Languages with Density Mapping

SeungYeop Baik, Sicheol Sung, Yo-Sub Han

A quantum finite-state automaton (QFA) is a theoretical model designed to simulate the evolution of a quantum system with finite memory in response to sequential input strings. We define the language of a QFA as the set of strings that lead the QFA to an accepting state when processed from its initial state. QFAs exemplify how quantum computing can achieve greater efficiency compared to classical computing. While being one of the simplest quantum models, QFAs are still notably challenging to construct from scratch due to the preliminary knowledge of quantum mechanics required for superimposing unitary constraints on the automata. Furthermore, even when QFAs are correctly assembled, the limitations of a current quantum computer may cause fluctuations in the simulation results depending on how an assembled QFA is translated into a quantum circuit. We present a framework that provides a simple and intuitive way to build QFAs and maximize the simulation accuracy. Our framework relies on two methods: First, it offers a predefined construction for foundational types of QFAs that recognize special languages MOD and EQU. They play a role of basic building blocks for more complex QFAs. In other words, one can obtain more complex QFAs from these foundational automata using standard language operations. Second, we improve the simulation accuracy by converting these QFAs into quantum circuits such that the resulting circuits perform well on noisy quantum computers. Our framework is available at https://github.com/sybaik1/qfa-toolkit.

arXiv:2407.02776•Jul 3, 2024•0 citations
We study quantum finite automata with control language (qfcs), a theoretical model for finite memory hybrid systems coupling a classical computational framework with a quantum component. We constructively show how to simulate measure-once, measure-many, reversible, and Latvian qfas by qfcs, emphasizing the size cost of such simulations. Next, we prove the decidability of testing the periodicity of the stochastic event induced by a given qfc. Thanks to our qfa simulations, we can extend such a decidability result to measure-once, measure-many, reversible, and Latvian qfas as well. Finally, we focus on comparing the size efficiency of quantum and classical finite state automata on unary regular language recognition. We show that unary regular languages can be recognized by isolated cut point qfcs for which the size is generally quadratically smaller than the size of equivalent dfas.
We design Latvian quantum finite state automata (LQFAs for short) recognizing unary regular languages with isolated cut point 1 2 .From an architectural point of view, we combine two LQFAs recognizing with isolated cut point, respectively, the finite part and the ultimately periodic part of any given unary regular language L. In both modules, we use a component addressed in the literature and here suitably adapted to the unary case, to discriminate strings on the basis of their length.The number of basis states and the isolation around the cut point of the resulting LQFA for L exponentially depends on the size of the minimal deterministic finite state automaton for L.
We design Latvian quantum finite state automata (lqfas) recognizing unary regular languages with isolated cut point [Formula: see text]. From an architectural viewpoint, we suitably combine two lqfas recognizing with isolated cut point, respectively, the finite part and the ultimately periodic part any given unary regular language [Formula: see text] consists of. In particular, both these lqfas incorporate a sub-module discriminating strings on the basis of their length. Both the number of basis states and the isolation around the cut point of the resulting lqfa for [Formula: see text] exponentially depend on the size of the minimal deterministic finite state automaton for [Formula: see text]. Moreover, the recognition of [Formula: see text] tends to becoming deterministic as the number of the basis states employed in the length-discriminating sub-module grows.
We study the phenomenon of periodicity on quantum automata from three points of view. First, we provide an efficient algorithm for testing the periodicity of stochastic events induced by measure-once one-way unary quantum automata (1qfa's). Second, we design an algorithm for the synthesis of succinct unary 1qfa's inducing periodic events. To evaluate the size of the resulting 1qfa's, we relate the number of states of a minimal 1qfa inducing a linear approximation of a periodic event p to the harmonic structure of p. Next, we study the complexity of our synthesis algorithm. Third, we apply our synthesis algorithm for building succinct 1qfa's that accept unary periodic languages. We also prove a lower bound on the size of 1qfa's accepting unary periodic languages.
We show that, for any stochastic event p of period n, there exists a measure-once one-way quantum finite automaton (1qfa) with at most states inducing the event ap+b, for constants a>0, b ≥ 0, satisfying a+b ≥ 1. This fact is proved by designing an algorithm which constructs the desired 1qfa in polynomial time. As a consequence, we get that any periodic language of period n can be accepted with isolated cut point by a 1qfa with no more than states. Our results give added evidence of the strength of measure-once 1qfa's with respect to classical automata.
The computational model of Quantum Finite Automata has been introduced by multiple authors (e.g. [38, 44]) with some variations in definition. The objective of this thesis is to understand what class of languages can be recognized by these different variations, and how many states are required. We begin by showing that we can use algebraic automata theory to characterize the language recognition power of QFAs. Algebraic automata theory associates to each language a canonical syntactic monoid, and the algebraic structure of this monoid becomes a meaningful parameter in describing language classes. We show that the class of languages recognized by Latvian QFAs [3] corresponds exactly to boolean combinations of languages recognized by Brodsky and Pippenger's QFA model [20], which correspond exactly to those languages whose syntactic monoid is in the class BG. Known results give us a decision procedure for testing membership in this language class. We also use algebraic automata theory to give nearly tight upper and lower bounds on the class of languages recognized by Brodsky and Pippenger's QFAs. We then extend a number of lower bound techniques known for Kondacs and Watrous' 1-way QFA model to Nayak's Generalized QFA. Both of these models are related in that they are permitted to halt before reading the entire input, allowing them to recognize certain languages whose syntactic monoid lies outside of BG. Finally, we investigate the question of QFA succinctness. It is known that QFAs can recognize some languages using exponentially fewer states compared to deterministic finite automata. We extend results from [16] to show that the word problem over abelian groups has this property. We also give example of interesting noncommutative languages with this property.
A quantum finite-state automaton (QFA) is a theoretical model designed to simulate the evolution of a quantum system with finite memory in response to sequential input strings. We define the language of a QFA as the set of strings that lead the QFA to an accepting state when processed from its initial state. QFAs exemplify how quantum computing can achieve greater efficiency compared to classical computing. While being one of the simplest quantum models, QFAs are still notably challenging to construct from scratch due to the preliminary knowledge of quantum mechanics required for superimposing unitary constraints on the automata. Furthermore, even when QFAs are correctly assembled, the limitations of a current quantum computer may cause fluctuations in the simulation results depending on how an assembled QFA is translated into a quantum circuit. We present a framework that provides a simple and intuitive way to build QFAs and maximize the simulation accuracy. Our framework relies on two methods: First, it offers a predefined construction for foundational types of QFAs that recognize special languages MOD and EQU. They play a role of basic building blocks for more complex QFAs. In other words, one can obtain more complex QFAs from these foundational automata using standard language operations. Second, we improve the simulation accuracy by converting these QFAs into quantum circuits such that the resulting circuits perform well on noisy quantum computers. Our framework is available at https://github.com/sybaik1/qfa-toolkit.