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

Mathematics, computing, language, and life

Quantum Automata and Periodic Events

Carlo Mereghetti, Beatrice Palano

Published Oct 1, 2010• 2 citations
Publisher

Abstract

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.

DOI
10.1142/9781848165458_0011

Related papers

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

Quantum Automata for some Multiperiodic Languages.

Carlo Mereghetti, Beatrice Palano

We exhibit small size measure-once one-way quantum finite automata (mo-1qfa's) inducing multiperiodic stochastic events. Moreover, for certain classes of multiperiodic languages, we exhibit: (i) isolated cut point mo-1qfa's whose size logarithmically depends on the periods; (ii) Monte Carlo mo-1qfa's whose size logarithmically depends on the periods and polynomially on the inverse of the error probability.

DCFS•Jan 1, 2006•0 citations

Behaviours of Unary Quantum Automata

Maria Paola Bianchi, Beatrice Palano

We study the stochastic events induced by MM-qfa's working on unary alphabets. We give two algorithms for unary MM-qfa's: the first computes the dimension of the ergodic and transient components of the non halting subspace, while the second tests whe

Fundamenta Informaticae•Jan 1, 2010•25 citations

On the power of quantum finite state automata

A. Kondacs, John Watrous

In this paper, we introduce 1-way and 2-way quantum finite state automata (1qfa's and 2qfa's), which are the quantum analogues of deterministic, nondeterministic and probabilistic 1-way and 2-way finite state automata. We prove the following facts regarding 2qfa's. 1. For any /spl epsiv/>0, there is a 2qfa M which recognizes the non-regular language L={a/sup m/b/sup m/|m/spl ges/1} with (one-sided) error bounded by E, and which halts in linear time. Specifically, M accepts any string in L with probability 1 and rejects any string not in L with probability at least 1-/spl epsiv/. 2. For every regular language L, there is a reversible (and hence quantum) 2-way finite state automaton which recognizes L and which runs in linear time. In fact, it is possible to define 2qfar's which recognize the non-context-free language {a/sup m/b/sup m/c/sup m/|m/spl ges/1}, based on the same technique used for 1. Consequently, the class of languages recognized by linear time, bounded error 2qfa's properly includes the regular languages. Since it is known that 2-way deterministic, nondeterministic and polynomial expected time, bounded error probabilistic finite automata can recognize only regular languages, it follows that 2qfa's are strictly more powerful than these "classical" models. In the case of 1-way automata, the situation is reversed. We prove that the class of languages recognizable by bounded error 1qfa's is properly contained in the class of regular languages.

Annual Symposium on Foundations of Computer Science•Nov 22, 2002•371 citations

Unary Quantum Finite State Automata with Control Language

Carlo Mereghetti, Beatrice Palano, Priscilla Raucci

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.

Applied Sciences•Feb 12, 2024•5 citations

Quantum finite automata with control language

Carlo Mereghetti, Beatrice Palano

Bertoni et al. introduced in Lect. Notes Comput. Sci. 2710 (2003) 1–20 a new model of 1-way quantum finite automaton (1qfa) called 1qfa with control language (1qfc). This model, whose recognizing power is exactly the class of regular languages, generalizes main models of 1qfa's proposed in the literature. Here, we investigate some properties of 1qfc's. In particular, we provide algorithms for constructing 1qfc's accepting the inverse homomorphic images and quotients of languages accepted by 1qfc's. Moreover, we give instances of binary regular languages on which 1qfc's are proved to be more succinct (i.e. , to have less states) than the corresponding classical (deterministic) automata.

RAIRO - Theoretical Informatics and Applications•Apr 1, 2006•28 citations
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.
In this paper, we introduce 1-way and 2-way quantum finite state automata (1qfa's and 2qfa's), which are the quantum analogues of deterministic, nondeterministic and probabilistic 1-way and 2-way finite state automata. We prove the following facts regarding 2qfa's. 1. For any /spl epsiv/>0, there is a 2qfa M which recognizes the non-regular language L={a/sup m/b/sup m/|m/spl ges/1} with (one-sided) error bounded by E, and which halts in linear time. Specifically, M accepts any string in L with probability 1 and rejects any string not in L with probability at least 1-/spl epsiv/. 2. For every regular language L, there is a reversible (and hence quantum) 2-way finite state automaton which recognizes L and which runs in linear time. In fact, it is possible to define 2qfar's which recognize the non-context-free language {a/sup m/b/sup m/c/sup m/|m/spl ges/1}, based on the same technique used for 1. Consequently, the class of languages recognized by linear time, bounded error 2qfa's properly includes the regular languages. Since it is known that 2-way deterministic, nondeterministic and polynomial expected time, bounded error probabilistic finite automata can recognize only regular languages, it follows that 2qfa's are strictly more powerful than these "classical" models. In the case of 1-way automata, the situation is reversed. We prove that the class of languages recognizable by bounded error 1qfa's is properly contained in the class of regular languages.
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.
Bertoni et al. introduced in Lect. Notes Comput. Sci. 2710 (2003) 1–20 a new model of 1-way quantum finite automaton (1qfa) called 1qfa with control language (1qfc). This model, whose recognizing power is exactly the class of regular languages, generalizes main models of 1qfa's proposed in the literature. Here, we investigate some properties of 1qfc's. In particular, we provide algorithms for constructing 1qfc's accepting the inverse homomorphic images and quotients of languages accepted by 1qfc's. Moreover, we give instances of binary regular languages on which 1qfc's are proved to be more succinct (i.e. , to have less states) than the corresponding classical (deterministic) automata.