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:quant-ph/9903014 · SIAM Journal on Computing

Characterizations of 1-Way Quantum Finite Automata

Alex Brodsky, Nicholas J. Pippenger

Published Jan 1, 2002• 151 citations
arXivHTMLPDF

Abstract

The 2-way quantum finite automaton introduced by Kondacs and Watrous [Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997, IEEE Computer Society, pp. 66--75] can accept nonregular languages with bounded error in polynomial time. If we restrict the head of the automaton to moving classically and to moving only in one direction, the acceptance power of this 1-way quantum finite automaton is reduced to a proper subset of the regular languages. In this paper we study two different models of 1-way quantum finite automata. The first model, termed measure-once quantum finite automata, was introduced by Moore and Crutchfield [Theoret. Comput. Sci., 237 (2000), pp. 275--306], and the second model, termed measure-many quantum finite automata, was introduced by Kondacs and Watrous [Proceedings of the38th Annual Symposium on Foundations of Computer Science, 1997, IEEE Computer Society, pp. 66--75]. We characterize the measure-once model when it is restricted to accepting with bounded error and show that, without that restriction, it can solve the word problem over the free group. We also show that it can be simulated by a probabilistic finite automaton and describe an algorithm that determines if two measure-once automata are equivalent. We prove several closure properties of the classes of languages accepted by measure-many automata, including inverse homomorphisms, and provide a new necessary condition for a language to be accepted by the measure-many model with bounded error. Finally, we show that piecewise testable sets can be accepted with bounded error by a measure-many quantum finite automaton, introducing new construction techniques for quantum automata in the process.

DOI
10.1137/s0097539799353443

Related papers

Models and characterizations of 1-way quantum finite automata

Brodsky, Alexander

In the past year two different models of quantum finite automata have been proposed. The first model, introduced by Moore and Crutchfield[MC98], makes one measurement on its state at the end of its computation and is called a measure-once quantum finite automata. The second model, introduced by Kondacs and Watrous[KW97], makes a measurement of its state after every transition and is called a measure-many quantum finite automata. In this thesis we investigate the characteristics of the two models. We characterize measure-once quantum finite automata when they are restricted to acceptance with bounded error, and we show that, when they are not so restricted, they can solve the word problem over the free group. We show that they can be simulated by probabilistic finite automata, which implies that they are no more powerful than probabilistic finite automata. We also describe an algorithm that determines if two automata are equivalent. We show that the class of languages accepted by measure-many quantum finite automata is closed under quotient, complement, and inverse homomorphisms. We prove a necessary condition for a language to be accepted by a measure-many automaton with bounded error and we show that certain sets, including piecewise testable sets, can be accepted with bounded error by this automata.

•Jan 1, 2009•1 citation

One-way quantum finite automata together with classical states: Equivalence and Minimization

Daowen Qiu, Paulo Mateus, Xiangfu Zou +1 more

One-way quantum finite automata (1QFA) proposed by Moore and Crutchfield and by Kondacs and Watrous accept only subsets of regular languages with bounded error. In this paper, we develop a new computing model of 1QFA, namely, one-way quantum finite automata together with classical states (1QFAC for short). In this model, a component of classical states is added, and the choice of unitary evolution of quantum states at each step is closely related to the current classical state. 1QFAC can accept all regular languages with no error, and in particular, 1QFAC can accept some languages with essentially less number of states than deterministic finite automata (DFA). The main technical results are as follows. (1) We prove that the set of languages accepted by 1QFAC with bounded error consists precisely of all regular languages. (2) We show that, for any prime number m ≥ 2, there exists a regular language L0(m) whose minimal DFA needs O(m) states and that can not be accepted by the 1QFA proposed by Moore and Crutchfield and by Kondacs and Watrous, but there exists 1QFAC accepting L0(m) with only constant classical states and O(log(m)) quantum basis states. Analogous results for multi-letter automata are also established. (3) By a bilinearization technique we prove that any two 1QFAC A1 and A2 are equivalent if and only if they are (k1n1) 2 + (k2n2) 2 − 1-equivalent, and there exists a polynomial-time O([(k1n1) 2 + (k2n2) 2]4) algorithm for determining their equivalence, where k1 and k2 are the numbers of classical states of A1 and A2, as well as n1 and n2 are the numbers of quantum basis states of A1 andA2, respectively. (4) We show that the minimization problem of 1QFAC is in EXPSPACE. As a corollary of this result, we obtain that the minimization problem of MO-1QFA is also in EXPSPACE. Finally, we draw some conclusions and point out open ∗Corresponding author. E-mail address: issqdw@mail.sysu.edu.cn (D. Qiu). †E-mail address: {paulo.mateus,amilcar.sernadas}@math.ist.utl.pt.

•Sep 8, 2009•2 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

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•2 citations

On the power of quantum finite state automata

A. Kondacs, John Watrous

In this paper, we introduce 1-way and 2-way quantum finite state automata (1qfa's and 2qfa's), which are the quantum analogues of deterministic, nondeterministic and probabilistic 1-way and 2-way finite state automata. We prove the following facts regarding 2qfa's. 1. For any /spl epsiv/>0, there is a 2qfa M which recognizes the non-regular language L={a/sup m/b/sup m/|m/spl ges/1} with (one-sided) error bounded by E, and which halts in linear time. Specifically, M accepts any string in L with probability 1 and rejects any string not in L with probability at least 1-/spl epsiv/. 2. For every regular language L, there is a reversible (and hence quantum) 2-way finite state automaton which recognizes L and which runs in linear time. In fact, it is possible to define 2qfar's which recognize the non-context-free language {a/sup m/b/sup m/c/sup m/|m/spl ges/1}, based on the same technique used for 1. Consequently, the class of languages recognized by linear time, bounded error 2qfa's properly includes the regular languages. Since it is known that 2-way deterministic, nondeterministic and polynomial expected time, bounded error probabilistic finite automata can recognize only regular languages, it follows that 2qfa's are strictly more powerful than these "classical" models. In the case of 1-way automata, the situation is reversed. We prove that the class of languages recognizable by bounded error 1qfa's is properly contained in the class of regular languages.

Annual Symposium on Foundations of Computer Science•Nov 22, 2002•348 citations

Quantum Finite Automata with One-Sided Unbounded Error

Abuzer Yakaryılmaz, A. C. Cem Say

Abstract. We prove that several variants of the quantum finite automaton (QFA) model are strictly superior to their probabilistic counterparts, in terms of both language recognition power and succinctness, in the onesided unbounded error setting. This is the first case where one-way QFA models have been shown to outperform the corresponding probabilistic automata in both these respects. We give a characterization of the class of languages recognized by these QFA’s with cutpoint 0, demonstrating that it is equal to the class of exclusive stochastic languages. We prove several closure properties of the related classes. 1

•Feb 12, 2009•2 citations
The 2-way quantum finite automaton introduced by Kondacs and Watrous [Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997, IEEE Computer Society, pp. 66--75] can accept nonregular languages with bounded error in polynomial time. If we restrict the head of the automaton to moving classically and to moving only in one direction, the acceptance power of this 1-way quantum finite automaton is reduced to a proper subset of the regular languages. In this paper we study two different models of 1-way quantum finite automata. The first model, termed measure-once quantum finite automata, was introduced by Moore and Crutchfield [Theoret. Comput. Sci., 237 (2000), pp. 275--306], and the second model, termed measure-many quantum finite automata, was introduced by Kondacs and Watrous [Proceedings of the38th Annual Symposium on Foundations of Computer Science, 1997, IEEE Computer Society, pp. 66--75]. We characterize the measure-once model when it is restricted to accepting with bounded error and show that, without that restriction, it can solve the word problem over the free group. We also show that it can be simulated by a probabilistic finite automaton and describe an algorithm that determines if two measure-once automata are equivalent. We prove several closure properties of the classes of languages accepted by measure-many automata, including inverse homomorphisms, and provide a new necessary condition for a language to be accepted by the measure-many model with bounded error. Finally, we show that piecewise testable sets can be accepted with bounded error by a measure-many quantum finite automaton, introducing new construction techniques for quantum automata in the process.
In the past year two different models of quantum finite automata have been proposed. The first model, introduced by Moore and Crutchfield[MC98], makes one measurement on its state at the end of its computation and is called a measure-once quantum finite automata. The second model, introduced by Kondacs and Watrous[KW97], makes a measurement of its state after every transition and is called a measure-many quantum finite automata. In this thesis we investigate the characteristics of the two models. We characterize measure-once quantum finite automata when they are restricted to acceptance with bounded error, and we show that, when they are not so restricted, they can solve the word problem over the free group. We show that they can be simulated by probabilistic finite automata, which implies that they are no more powerful than probabilistic finite automata. We also describe an algorithm that determines if two automata are equivalent. We show that the class of languages accepted by measure-many quantum finite automata is closed under quotient, complement, and inverse homomorphisms. We prove a necessary condition for a language to be accepted by a measure-many automaton with bounded error and we show that certain sets, including piecewise testable sets, can be accepted with bounded error by this automata.
One-way quantum finite automata (1QFA) proposed by Moore and Crutchfield and by Kondacs and Watrous accept only subsets of regular languages with bounded error. In this paper, we develop a new computing model of 1QFA, namely, one-way quantum finite automata together with classical states (1QFAC for short). In this model, a component of classical states is added, and the choice of unitary evolution of quantum states at each step is closely related to the current classical state. 1QFAC can accept all regular languages with no error, and in particular, 1QFAC can accept some languages with essentially less number of states than deterministic finite automata (DFA). The main technical results are as follows. (1) We prove that the set of languages accepted by 1QFAC with bounded error consists precisely of all regular languages. (2) We show that, for any prime number m ≥ 2, there exists a regular language L0(m) whose minimal DFA needs O(m) states and that can not be accepted by the 1QFA proposed by Moore and Crutchfield and by Kondacs and Watrous, but there exists 1QFAC accepting L0(m) with only constant classical states and O(log(m)) quantum basis states. Analogous results for multi-letter automata are also established. (3) By a bilinearization technique we prove that any two 1QFAC A1 and A2 are equivalent if and only if they are (k1n1) 2 + (k2n2) 2 − 1-equivalent, and there exists a polynomial-time O([(k1n1) 2 + (k2n2) 2]4) algorithm for determining their equivalence, where k1 and k2 are the numbers of classical states of A1 and A2, as well as n1 and n2 are the numbers of quantum basis states of A1 andA2, respectively. (4) We show that the minimization problem of 1QFAC is in EXPSPACE. As a corollary of this result, we obtain that the minimization problem of MO-1QFA is also in EXPSPACE. Finally, we draw some conclusions and point out open ∗Corresponding author. E-mail address: issqdw@mail.sysu.edu.cn (D. Qiu). †E-mail address: {paulo.mateus,amilcar.sernadas}@math.ist.utl.pt.
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.
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).)
In this paper, we introduce 1-way and 2-way quantum finite state automata (1qfa's and 2qfa's), which are the quantum analogues of deterministic, nondeterministic and probabilistic 1-way and 2-way finite state automata. We prove the following facts regarding 2qfa's. 1. For any /spl epsiv/>0, there is a 2qfa M which recognizes the non-regular language L={a/sup m/b/sup m/|m/spl ges/1} with (one-sided) error bounded by E, and which halts in linear time. Specifically, M accepts any string in L with probability 1 and rejects any string not in L with probability at least 1-/spl epsiv/. 2. For every regular language L, there is a reversible (and hence quantum) 2-way finite state automaton which recognizes L and which runs in linear time. In fact, it is possible to define 2qfar's which recognize the non-context-free language {a/sup m/b/sup m/c/sup m/|m/spl ges/1}, based on the same technique used for 1. Consequently, the class of languages recognized by linear time, bounded error 2qfa's properly includes the regular languages. Since it is known that 2-way deterministic, nondeterministic and polynomial expected time, bounded error probabilistic finite automata can recognize only regular languages, it follows that 2qfa's are strictly more powerful than these "classical" models. In the case of 1-way automata, the situation is reversed. We prove that the class of languages recognizable by bounded error 1qfa's is properly contained in the class of regular languages.
Abstract. We prove that several variants of the quantum finite automaton (QFA) model are strictly superior to their probabilistic counterparts, in terms of both language recognition power and succinctness, in the onesided unbounded error setting. This is the first case where one-way QFA models have been shown to outperform the corresponding probabilistic automata in both these respects. We give a characterization of the class of languages recognized by these QFA’s with cutpoint 0, demonstrating that it is equal to the class of exclusive stochastic languages. We prove several closure properties of the related classes. 1