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

Journal of Computer Research and Development

The Equivalence Between Quantum Mealy Automata and Quantum Moore Automata

Zhengjun Xi, Xin Wang, Yongming Li

Published Sep 15, 2009• 0 citations
OpenAlex

Related papers

Determining the equivalence for one-way quantum finite automata

Lvzhou Li, Daowen Qiu

Theoretical Computer Science•Apr 2, 2008•50 citations

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

Hierarchy and equivalence of multi-letter quantum finite automata

Daowen Qiu, Sheng Yü

arXiv:0812.0852•Theoretical Computer Science•Apr 8, 2009•30 citations

Computational Complementarity for Mealy Automata

Cristian S. Calude, Elena Calude, Cătălina Ştefănescu

In this paper we extend (and study) two computational complementary principles from Moore to Mealy automata which are finite machines possessing better “quantum-like” features. We conjecture that automata which are reversible according to Svozil do not satisfy any of these computational complementarity principles. This result is consistent with the embeddability of irreversible computations into reversible ones (via Bennett’s method, for example). Mathematica experiments confirmed this hypothesis.

Bulletin of the European Association for Theoretical Computer Science•May 1, 1998•5 citations

On quantum-mechanical automata

Asher Peres

Physics Letters A•Apr 1, 1984•23 citations

Quantum Pushdown Automata

Marats Golovkins

Quantum finite automata, as well as quantum pushdown automata (QPA) were first introduced by C. Moore and J. P. Crutchfield. In this paper we introduce the notion of QPA in a non-equivalent way, including unitarity criteria, by using the definition of quantum finite automata of Kondacs and Watrous. It is established that the unitarity criteria of QPA are not equivalent to the corresponding unitarity criteria of quantum Turing machines. We show that QPA can recognize every regular language. Finally we present some simple languages recognized by QPA, not recognizable by deterministic pushdown automata.

arXiv:quant-ph/0102054•Feb 9, 2001•0 citations
In this paper we extend (and study) two computational complementary principles from Moore to Mealy automata which are finite machines possessing better “quantum-like” features. We conjecture that automata which are reversible according to Svozil do not satisfy any of these computational complementarity principles. This result is consistent with the embeddability of irreversible computations into reversible ones (via Bennett’s method, for example). Mathematica experiments confirmed this hypothesis.
Quantum finite automata, as well as quantum pushdown automata (QPA) were first introduced by C. Moore and J. P. Crutchfield. In this paper we introduce the notion of QPA in a non-equivalent way, including unitarity criteria, by using the definition of quantum finite automata of Kondacs and Watrous. It is established that the unitarity criteria of QPA are not equivalent to the corresponding unitarity criteria of quantum Turing machines. We show that QPA can recognize every regular language. Finally we present some simple languages recognized by QPA, not recognizable by deterministic pushdown automata.