Multi-letter {\it quantum finite automata} (QFAs) were a quantum variant of classical {\it one-way multi-head finite automata} (J. Hromkovič, Acta Informatica 19 (1983) 377-384), and it has been shown that this new one-way QFAs (multi-letter QFAs) can accept with no error some regular languages
(a+b)∗b that are unacceptable by the previous one-way QFAs. In this paper, we study the decidability of the equivalence of multi-letter QFAs, and the main technical contributions are as follows: (1) We show that any two automata, a
k1-letter QFA
A1 and a
k2-letter QFA
A2, over the same input alphabet
Σ are equivalent if and only if they are
(n2mk−1−mk−1+k)-equivalent, where
m=∣Σ∣ is the cardinality of
Σ,
k=max(k1,k2), and
n=n1+n2, with
n1 and
n2 being the numbers of states of
A1 and
A2, respectively. When
k=1, we obtain the decidability of equivalence of measure-once QFAs in the literature. It is worth mentioning that our technical method is essentially different from that for the decidability of the case of single input alphabet (i.e.,
m=1). (2) However, if we determine the equivalence of multi-letter QFAs by checking all strings of length not more than $ n^2m^{k-1}-m^{k-1}+k$, then the worst time complexity is exponential, i.e.,
O(n6mn2mk−1−mk−1+2k−1). Therefore, we design a polynomial-time
O(m2k−1n8+kmkn6) algorithm for determining the equivalence of any two multi-letter QFAs. Here, the time complexity is concerning the number of states in the multi-letter QFAs, and
k is thought of as a constant.
We first show that given a
k1-letter quantum finite automata
A1 and a
k2-letter quantum finite automata
A2 over the same input alphabet
Σ, they are equivalent if and only if they are
(n12+n22−1)∣Σ∣k−1+k-equivalent where
n1,
i=1,2, are the numbers of state 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 numbers of state in
Ai respectively, and
k=max{k1,k2}. Next, we study the language equivalence problem of those two kinds of quantum finite automata. We show that for
k-letter quantum finite automata, the non-strict cut-point language equivalence problem is undecidable, i.e., it is undecidable whether
L≥λ(A1)=L≥λ(A2) where
0<λ≤1 and
Ai are
ki-letter quantum finite automata. Further, we show that both strict and non-strict cut-point language equivalence problem for
k-letter measure many quantum finite automata are undecidable. The direct consequences of the above outcomes are summarized in the paper. Finally, we comment on existing proofs about the minimization problem of one way quantum finite automata not only because we have been showing great interest in this kind of problem, which is very important in classical automata theory, but also due to that the problem itself, personally, is a challenge. This problem actually remains open.
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.
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.
We study 1-way quantum finite automata (QFAs). First, we compare them with their classical counterparts. We show that, if an automaton is required to give the correct answer with a large probability (greater than 7/9), then any 1-way QFAs can be simulated by a 1-way reversible automaton. However, quantum automata giving the correct answer with smaller probabilities are more powerful than reversible automata. Second, we show that 1-way QFAs can be very space-efficient. We construct a 1-way QFA that is exponentially smaller than any equivalent classical (even randomized) finite automaton. We think that this construction may be useful for design of other space-efficient quantum algorithms. Third, we consider several generalizations of 1-way QFAs. Here, our goal is to find a model which is more powerful than 1-way QFAs keeping the quantum part as simple as possible.