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

Quantum Finite Automata: A Modern Introduction

A. C. Cem Say, Abuzer Yakaryılmaz

Published Jan 1, 2014• 56 citations
Publisher
DOI
10.1007/978-3-319-13350-8_16

Related papers

Quantum Automata: An Overview

Stanley Gudder

International Journal of Theoretical Physics•Sep 1, 1999•20 citations

Quantum finite automata: A modern introduction

A. C. Cem Say, Abuzer Yakaryılmaz

We present five examples where quantum finite automata (QFAs) outperform their classical counterparts. This may be useful as a relatively simple technique to introduce quantum computation concepts to computer scientists. We also describe a modern QFA model involving superoperators that is able to simulate all known QFA and classical finite automaton variants.

arXiv:1406.4048•Jun 16, 2014•5 citations

Quantum Finite Automata

Daowen Qiu, Lvzhou Li, Paulo Mateus +1 more

Chapman & Hall/CRC eBooks•Nov 29, 2012•2 citations

Introduction to Quantum Cellular Automata

Bachir Aoun, Mohamad Tarifi

We provide an introduction to Quantum Cellular Automata.

arXiv:quant-ph/0401123•Jan 20, 2004•18 citations

QUANTUM COUNTER AUTOMATA

A. C. Cem Say, Abuzer Yakaryılmaz

The question of whether quantum real-time one-counter automata (rtQ1CAs) can outperform their probabilistic counterparts has been open for more than a decade. We provide an affirmative answer to this question, by demonstrating a non-context-free language that can be recognized with perfect soundness by a rtQ1CA. This is the first demonstration of the superiority of a quantum model to the corresponding classical one in the real-time case with an error bound less than 1. We also introduce a generalization of the rtQ1CA, the quantum one-way one-counter automaton (1Q1CA), and show that they too are superior to the corresponding family of probabilistic machines. For this purpose, we provide general definitions of these models that reflect the modern approach to the definition of quantum finite automata, and point out some problems with previous results. We identify several remaining open problems.

arXiv:1105.0165•International Journal of Foundations of Computer Science•Aug 1, 2012•11 citations

Quantum finite automata

Jozef Gruska

•Jan 1, 2006•0 citations
The question of whether quantum real-time one-counter automata (rtQ1CAs) can outperform their probabilistic counterparts has been open for more than a decade. We provide an affirmative answer to this question, by demonstrating a non-context-free language that can be recognized with perfect soundness by a rtQ1CA. This is the first demonstration of the superiority of a quantum model to the corresponding classical one in the real-time case with an error bound less than 1. We also introduce a generalization of the rtQ1CA, the quantum one-way one-counter automaton (1Q1CA), and show that they too are superior to the corresponding family of probabilistic machines. For this purpose, we provide general definitions of these models that reflect the modern approach to the definition of quantum finite automata, and point out some problems with previous results. We identify several remaining open problems.