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

Lecture notes in computer science

Languages Recognized with Unbounded Error by Quantum Finite Automata

Abuzer Yakaryılmaz, A. C. Cem Say

Published Jan 1, 2009• 30 citations
Publisher
DOI
10.1007/978-3-642-03351-3_33

Related papers

Languages recognized with unbounded error by quantum finite automata

Abuzer Yakaryılmaz, A. C. Cem Say

This paper has been superseded by arXiv:1007.3624

arXiv:0809.0073•Aug 30, 2008•4 citations

Small size quantum automata recognizing some regular languages

Alberto Bertoni, Carlo Mereghetti, Beatrice Palano

Theoretical Computer Science•Apr 19, 2005•31 citations

Language Recognition by Generalized Quantum Finite Automata with Unbounded Error

Abuzer Yakaryılmaz, A. C. Cem Say

Abstract. We prove that the class of languages recognized by generalized quantum finite automata (GQFA’s) with unbounded error equals the class of stochastic languages. The capability of performing additional intermediate projective measurements does not increase the recognition power of GQFA’s over Kondacs-Watrous quantum finite automata in this setting. Unlike their probabilistic counterparts, allowing the tape head to stay put for some steps during its traversal of the input enlarges the class of languages recognized by GQFA’s with unbounded error. 1

•Jan 18, 2009•6 citations

Languages Recognizable by Quantum Finite Automata

Rūsiņš Freivalds

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

Quantum finite automata using ancilla qubits

Kathrin Paschen

We introduce a new model of quantum finite automata. By using ancilla qubits, it becomes possible to recognize any regular language with certainty. Some nonregular languages can be recognized with one-sided unbounded error. We analyze a class of languages that can be recognized in this model in terms of a cascade composition of automata. This also allows to treat the case of an automaton with both classical and quantum states.

•Jan 1, 2000•24 citations

Probabilities to Accept Languages by Quantum Finite Automata

Andris Ambainis, Richard Bonner, Rūsiņš Freivalds +1 more

arXiv:quant-ph/9904066•Lecture notes in computer science•Jan 1, 1999•35 citations
Abstract. We prove that the class of languages recognized by generalized quantum finite automata (GQFA’s) with unbounded error equals the class of stochastic languages. The capability of performing additional intermediate projective measurements does not increase the recognition power of GQFA’s over Kondacs-Watrous quantum finite automata in this setting. Unlike their probabilistic counterparts, allowing the tape head to stay put for some steps during its traversal of the input enlarges the class of languages recognized by GQFA’s with unbounded error. 1