arXiv:quant-ph/0009004

On the class of languages recognizable by 1-way quantum finite automata

Andris Ambainis, Arnolds Ķikusts, Māris Valdats

Published Sep 1, 2000• 6 citations

Abstract

It is an open problem to characterize the class of languages recognized by quantum finite automata (QFA). We examine some necessary and some sufficient conditions for a (regular) language to be recognizable by a QFA. For a subclass of regular languages we get a condition which is necessary and sufficient. Also, we prove that the class of languages recognizable by a QFA is not closed under union or any other binary Boolean operation where both arguments are significant.

DOI: 10.48550/arxiv.quant-ph/0009004

Related papers

The class of languages recognizable by 1-way quantum finite automata is not closed under union

Māris Valdats

In this paper we develop little further the theory of quantum finite automata (QFA). There are already few properties of QFA known, that deterministic and probabilistic finite automata do not have e.g. they cannot recognize all regular languages. In this paper we show, that class of languages recognizable by QFA is not closed under union, even not under any Boolean operation, where both arguments are significant.

arXiv:quant-ph/0001005Jan 4, 20003 citations

Languages recognized by nondeterministic quantum finite automata

Abuzer Yakaryılmaz, A. C. Cem Say

The nondeterministic quantum finite automaton (NQFA) is the only known case where a one-way quantum finite automaton (QFA) model has been shown to be strictly superior in terms of language recognition power to its probabilistic counterpart. We give a characterization of the class of languages recognized by NQFAs, demonstrating that it is equal to the class of exclusive stochastic languages. We also characterize the class of languages that are recognized necessarily by two-sided error by QFAs. It is shown that these classes remain the same when the QFAs used in their definitions are replaced by several different model variants that have appeared in the literature. We prove several closure properties of the related classes. The ramifications of these results about classical and quantum sublogarithmic space complexity classes are examined.

arXiv:0902.2081Quantum Information and ComputationSep 1, 201049 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 ScienceNov 22, 2002348 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, 20092 citations

1-Way Multihead Quantum Finite State Automata

Debayan Ganguly, Kingshuk Chatterjee, Kumar S. Ray

1-way multihead quantum finite state automata (1QFA(k)) can be thought of modified version of 1-way quantum finite state automata (1QFA) and k-letter quantum finite state automata (k-letter QFA) respectively. It has been shown by Moore and Crutchfield as well as Konadacs and Watrous that 1QFA can’t accept all regular language. In this paper, we show different language recognizing capabilities of our model 1-way multihead QFAs. New results presented in this paper are the following ones: 1) We show that newly introduced 1-way 2-head quantum finite state automaton (1QFA(2)) structure can accept all unary regular languages. 2) A language which can’t be accepted by 1-way deterministic 2-head finite state automaton (1DFA((2)) can be accepted by 1QFA(2) with bounded error. 3) 1QFA(2) is more powerful than 1-way reversible 2-head finite state automaton (1RMFA(2)) with respect to recognition of language.

Applied MathematicsJan 1, 20165 citations

Applications of algebraic automata theory to quantum finite automata

Mark Mercer

The computational model of Quantum Finite Automata has been introduced by multiple authors (e.g. [38, 44]) with some variations in definition. The objective of this thesis is to understand what class of languages can be recognized by these different variations, and how many states are required. We begin by showing that we can use algebraic automata theory to characterize the language recognition power of QFAs. Algebraic automata theory associates to each language a canonical syntactic monoid, and the algebraic structure of this monoid becomes a meaningful parameter in describing language classes. We show that the class of languages recognized by Latvian QFAs [3] corresponds exactly to boolean combinations of languages recognized by Brodsky and Pippenger's QFA model [20], which correspond exactly to those languages whose syntactic monoid is in the class BG. Known results give us a decision procedure for testing membership in this language class. We also use algebraic automata theory to give nearly tight upper and lower bounds on the class of languages recognized by Brodsky and Pippenger's QFAs. We then extend a number of lower bound techniques known for Kondacs and Watrous' 1-way QFA model to Nayak's Generalized QFA. Both of these models are related in that they are permitted to halt before reading the entire input, allowing them to recognize certain languages whose syntactic monoid lies outside of BG. Finally, we investigate the question of QFA succinctness. It is known that QFAs can recognize some languages using exponentially fewer states compared to deterministic finite automata. We extend results from [16] to show that the word problem over abelian groups has this property. We also give example of interesting noncommutative languages with this property.

Jan 1, 20073 citations