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

IEICE Transactions on Information and Systems

On the Power of Non-deterministic Quantum Finite Automata

Tsunehiro Yoshinaga

Published Feb 1, 2002• 7 citations
OpenAlex

Related papers

Revisiting the Power and Equivalence of One-Way Quantum Finite Automata

Lvzhou Li, Daowen Qiu

Lecture notes in computer science•Jan 1, 2010•3 citations

Size of Quantum Versus Deterministic Finite Automata.

Andris Ambainis, Uldis Barbans, Agnese Belousova +7 more

IEEE Transactions on Very Large Scale Integration (VLSI) Systems•Jan 1, 2003•1 citation

Watson-Crick Quantum Finite Automata

Kingshuk Chatterjee, Kumar S. Ray

1-way quantum finite automata are deterministic and reversible in nature, which greatly reduces its accepting property. In fact the set of languages accepted by 1-way quantum finite automata is a proper subset of regular languages. In this paper we replace the tape head of 1-way quantum finite automata with DNA double strand and name the model Watson-Crick quantum finite automata. The non-injective complementarity relation of Watson-Crick automata introduces non-determinism in the quantum model. We show that this introduction of non-determinism increases the computational power of 1-way Quantum finite automata significantly. We establish that Watson-Crick quantum finite automata can accept all regular languages and that it also accepts some languages not accepted by any multihead deterministic finite automata. Exploiting the superposition property of quantum finite automata we show that Watson-Crick quantum finite automata accept the language L=ww where w belongs to {a,b}*.

arXiv:1507.05282•Jul 19, 2015•0 citations

Various Aspects of Finite Quantum Automata

Mika Hirvensalo

Lecture notes in computer science•Jan 1, 2008•31 citations

Two-way Quantum One-counter Automata

Tomohiro Yamasaki, Hirotada Kobayashi, Imai, Hiroshi

After the first treatments of quantum finite state automata by Moore and Crutchfield and by Kondacs and Watrous, a number of papers study the power of quantum finite state automata and their variants. This paper introduces a model of two-way quantum one-counter automata (2Q1CAs), combining the model of two-way quantum finite state automata (2QFAs) by Kondacs and Watrous and the model of one-way quantum one-counter automata (1Q1CAs) by Kravtsev. We give the definition of 2Q1CAs with well-formedness conditions. It is proved that 2Q1CAs are at least as powerful as classical two-way deterministic one-counter automata (2D1CAs), that is, every language L recognizable by 2D1CAs is recognized by 2Q1CAs with no error. It is also shown that several non-context-free languages including {a^n b^{n^2}} and {a^n b^{2^n}} are recognizable by 2Q1CAs with bounded error.

arXiv:cs/0110005•Oct 2, 2001•3 citations

The Complexity of Probabilistic versus Quantum Finite Automata

Gatis Midrijānis

arXiv:quant-ph/0309080•Lecture notes in computer science•Jan 1, 2002•0 citations
1-way quantum finite automata are deterministic and reversible in nature, which greatly reduces its accepting property. In fact the set of languages accepted by 1-way quantum finite automata is a proper subset of regular languages. In this paper we replace the tape head of 1-way quantum finite automata with DNA double strand and name the model Watson-Crick quantum finite automata. The non-injective complementarity relation of Watson-Crick automata introduces non-determinism in the quantum model. We show that this introduction of non-determinism increases the computational power of 1-way Quantum finite automata significantly. We establish that Watson-Crick quantum finite automata can accept all regular languages and that it also accepts some languages not accepted by any multihead deterministic finite automata. Exploiting the superposition property of quantum finite automata we show that Watson-Crick quantum finite automata accept the language L=ww where w belongs to {a,b}*.
After the first treatments of quantum finite state automata by Moore and Crutchfield and by Kondacs and Watrous, a number of papers study the power of quantum finite state automata and their variants. This paper introduces a model of two-way quantum one-counter automata (2Q1CAs), combining the model of two-way quantum finite state automata (2QFAs) by Kondacs and Watrous and the model of one-way quantum one-counter automata (1Q1CAs) by Kravtsev. We give the definition of 2Q1CAs with well-formedness conditions. It is proved that 2Q1CAs are at least as powerful as classical two-way deterministic one-counter automata (2D1CAs), that is, every language L recognizable by 2D1CAs is recognized by 2Q1CAs with no error. It is also shown that several non-context-free languages including {a^n b^{n^2}} and {a^n b^{2^n}} are recognizable by 2Q1CAs with bounded error.