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

Theoretical Computer Science

Small size quantum automata recognizing some regular languages

Alberto Bertoni, Carlo Mereghetti, Beatrice Palano

Published Apr 19, 2005• 31 citations
Publisher
DOI
10.1016/j.tcs.2005.03.032

Related papers

Regular Languages Accepted by Quantum Automata

Alberto Bertoni, Marco Carpentieri

Information and Computation•Mar 1, 2001•54 citations

Lower Bounds on the Size of Quantum Automata Accepting Unary Languages

Alberto Bertoni, Carlo Mereghetti, Beatrice Palano

Lecture notes in computer science•Jan 1, 2003•8 citations

Languages Recognized with Unbounded Error by Quantum Finite Automata

Abuzer Yakaryılmaz, A. C. Cem Say

Lecture notes in computer science•Jan 1, 2009•30 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•3 citations

Languages Recognizable by Quantum Finite Automata

Rūsiņš Freivalds

Lecture notes in computer science•Jan 1, 2006•5 citations

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
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.