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

arXiv:0809.0073

Languages recognized with unbounded error by quantum finite automata

Abuzer Yakaryılmaz, A. C. Cem Say

Published Aug 30, 2008• 4 citations
arXivHTMLPDF

Abstract

This paper has been superseded by arXiv:1007.3624
DOI
10.48550/arxiv.0809.0073

Related papers

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

Languages Recognizable by Quantum Finite Automata

Rūsiņš Freivalds

Lecture notes in computer science•Jan 1, 2006•5 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•41 citations

Small size quantum automata recognizing some regular languages

Alberto Bertoni, Carlo Mereghetti, Beatrice Palano

Theoretical Computer Science•Apr 19, 2005•30 citations

Quantum Automata and Languages of Finite Index

Andrea Benso, Flavio D’Alessandro, Paolo Papi

Lecture notes in computer science•Jan 1, 2024•1 citation

Language recognition by generalized quantum finite automata with unbounded error (abstract & poster)

Abuzer Yakaryılmaz, A. C. Cem Say

In this note, we generalize the results of arXiv:0901.2703v1 We show that all one-way quantum finite automaton (QFA) models that are at least as general as Kondacs-Watrous QFA's are equivalent in power to classical probabilistic 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 does enlarge the class of languages recognized by such QFA's with unbounded error. (Note that, the proof of Theorem 1 in the abstract was presented in the previous version (arXiv:0901.2703v1).)

arXiv:0901.2703•Jan 18, 2009•3 citations
In this note, we generalize the results of arXiv:0901.2703v1 We show that all one-way quantum finite automaton (QFA) models that are at least as general as Kondacs-Watrous QFA's are equivalent in power to classical probabilistic 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 does enlarge the class of languages recognized by such QFA's with unbounded error. (Note that, the proof of Theorem 1 in the abstract was presented in the previous version (arXiv:0901.2703v1).)