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

Fundamenta Informaticae

Behaviours of Unary Quantum Automata

Maria Paola Bianchi, Beatrice Palano

Published Jan 1, 2010• 24 citations
Publisher

Abstract

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
DOI
10.3233/fi-2010-333

Related papers

Events and Languages on Unary Quantum Automata

Maria Paola Bianchi, Beatrice Palano

Non-Classical Models for Automata and Applications•Jan 1, 2009•3 citations

Representation of Unary Singleton Languages using Quantum Finite State Automata

Sicheol Sung, Yo-Sub Han

양자 오토마타(quantum finite-state automaton, QFA)는 각 상태를 유한한 수의 큐비트(qubit)로 표현하는 오토마타다. QFA는 확률에 따라 문자열을 수락하거나 거부하며, QFA가 인식하는 언어는 해당 QFA가 임계값 이상의 확률로 수락하는 문자열의 집합이다. 본 논문에서는 다수측정(measure-many, MM-) QFA가 유계 단측오류(bounded one-sided error)를 통해 언어를 정의하는 경우, 모든 단항(unary) 한원소(singleton) 언어에 대하여 이를 정의하는 크기 4의 MM-QFA가 존재함을 보인다. 또한 이 경우에 상수 크기의 오류발생 확률을 보장하기 위한 QFA의 수행횟수를 제시한다.

정보과학회 컴퓨팅의 실제 논문지•Mar 25, 2025•0 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

Unary probabilistic and quantum automata on promise problems

Aida Gainutdinova, Abuzer Yakaryılmaz

Quantum Information Processing•Dec 26, 2017•22 citations

Unary Probabilistic and Quantum Automata on Promise Problems

Aida Gainutdinova, Abuzer Yakaryılmaz

Lecture notes in computer science•Jan 1, 2015•16 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
양자 오토마타(quantum finite-state automaton, QFA)는 각 상태를 유한한 수의 큐비트(qubit)로 표현하는 오토마타다. QFA는 확률에 따라 문자열을 수락하거나 거부하며, QFA가 인식하는 언어는 해당 QFA가 임계값 이상의 확률로 수락하는 문자열의 집합이다. 본 논문에서는 다수측정(measure-many, MM-) QFA가 유계 단측오류(bounded one-sided error)를 통해 언어를 정의하는 경우, 모든 단항(unary) 한원소(singleton) 언어에 대하여 이를 정의하는 크기 4의 MM-QFA가 존재함을 보인다. 또한 이 경우에 상수 크기의 오류발생 확률을 보장하기 위한 QFA의 수행횟수를 제시한다.
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.