Let
L>λ(A) and
L≥λ(A) be the languages recognized by {\em measure many 1-way quantum finite automata (MM-QFA)} (or,{\em enhanced 1-way quantum finite automata(EQFA)})
A with strict and non-strict cut-point
λ, respectively. We consider the language equivalence problem and show the following 1. both strict and non-strict language equivalence are undecidable; 2. we provide an another proof of the undecidability of non-strict and strict emptiness of MM-QFA and EQFA, and then reducing the language equivalence problem to emptiness problem; 3. lastly, we obtain some other properties which can be derived from the above results.
Quantum Finite Automata with Classical states (QFACs) are nondeterministic finite automata over a finite alphabet of quantum operations. We study expressiveness of this model on finite words and the corresponding emptiness problem. We show that regular languages are incomparable with those definable by Quantum Finite Automata (QFAs) and that both are strictly subsumed by QFAC-definable languages. We show that the emptiness problem for a QFAC can be reduced to the emptiness of the language intersection of a QFA and a finite automaton. This intersection is known to be decidable for strict thresholds but undecidable for non-strict cases. Furthermore, we consider the problem for flat QFACs, a restriction where the underlying automata contain no nested loops, and relate it to the higher-dimensional orbit problem, a long-standing open challenge in dynamical systems. Finally, we propose a sound and semi-complete witness searching procedure to verify the non-emptiness of one-loop QFACs, which are sufficiently expressive to represent some prominent quantum algorithms, such as Grover's search and quantum random walks.
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.
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
In this paper, we study some decision problems both for {\it multi-letter quantum finite automata} and {\it measure many multi-letter quantum finite automata}. We first show that given a
k1-letter quantum finite automaton
A1 and a
k2-letter quantum finite automaton
A2 over the same input alphabet
Σ, they are equivalent if and only if they are
(n12+n22−1)∣Σ∣k−1+k-equivalent where
ni,
i=1,2, are the number of states in
Ai respectively, and
k=max{k1,k2}. By applying a method, due to the author, used to deal with the equivalence problem of {\it measure many one-way quantum finite automata}, we also show that a
k1-letter measure many quantum finite automaton
A1 and a
k2-letter measure many quantum finite automaton
A2 are equivalent if and only if they are
(n12+n22−1)∣Σ∣k−1+k-equivalent where
ni,
i=1,2, are the number of states in
Ai respectively, and
k=max{k1,k2}.
Next, we study the emptiness problem of those two kinds of quantum finite automata. We show that whether the language recognized by a
k-letter quantum finite automaton with non-strict cut-point is empty is undecidable, but we leave open the emptiness of language reorganized by a
k-letter quantum finite automaton with strict cutpoint. We also show that whether the languages recognized by a
k-letter measure many quantum finite automaton with both nonstrict and strict cutpoints are undecidable. And the direct consequences of the above outcomes are summarized in the paper.
Quantum finite automata were introduced by C.Moore, J.P. Crutchfield, and by A.Kondacs and J.Watrous. This notion is not a generalization of the deterministic finite automata. Moreover, it was proved that not all regular languages can be recognized by quantum finite automata. A.Ambainis and R.Freivalds proved that for some languages quantum finite automata may be exponentially more concise rather than both deterministic and probabilistic finite automata. In this paper we introduce the notion of quantum finite multitape automata and prove that there is a language recognized by a quantum finite automaton but not by a deterministic or probabilistic finite automata. This is the first result on a problem which can be solved by a quantum computer but not by a deterministic or probabilistic computer. Additionally we discover unexpected probabilistic automata recognizing complicated languages.