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.
We exhibit a family {L_n} of finite regular languages such that any 1-way quantum finite automaton (QFA) accepting L_n with probability 1/2 + epsilon (for any constant epsilon > 0) must have 2^{Omega(n/log n)} states. On the other hand, each language L_n can be recognized by a deterministic finite automaton (DFA) of size O(n). This is in immediate contrast to the recent result of Ambainis and Freivalds which shows that for some regular languages, 1-way QFAs can be exponentially more space-efficient as compared to DFAs.
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.
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.
In automata theory, quantum computation has been widely examined for finite state machines, known as quantum finite automata (QFAs), and less attention has been given to QFAs augmented with counters or stacks. In this paper, we focus on such generalizations of QFAs where the input head operates in one-way or realtime mode, and present some new results regarding their superiority over their classical counterparts. Our first result is about the nondeterministic acceptance mode: Each quantum model architecturally intermediate between realtime finite state automaton and one-way pushdown automaton (one-way finite automaton, realtime and one-way finite automata with one-counter, and realtime pushdown automaton) is superior to its classical counterpart. The second and third results are about bounded error language recognition: for any k > 0, QFAs with k blind counters outperform their deterministic counterparts; and, a one-way QFA with a single head recognizes an infinite family of languages, which can be recognized by one-way probabilistic finite automata with at least two heads. Lastly, we compare the nondeterminictic and deterministic acceptance modes for classical finite automata with k blind counter(s), and we show that for any k > 0, the nondeterministic models outperform the deterministic ones.
This paper introduces a variant of two-way quantum finite automata named two-way multihead quantum finite automata. A two-way quantum finite automaton is more powerful than classical two-way finite automata. However, the generalizations of two-way quantum finite automata have not been defined so far as compared to one-way quantum finite automata model. We have investigated the newly introduced automata from two aspects: the language recognition capability and its comparison with classical and quantum counterparts. It has been proved that a language which cannot be recognized by any one-way and multi-letter quantum finite automata can be recognized by two-way quantum finite automata. Further, it has been shown that a language which cannot be recognized by two-way quantum finite automata can be recognized by two-way multihead quantum finite automata with two heads. Furthermore, it has been investigated that quantum variant of two-way deterministic multihead finite automata takes less number of heads to recognize a language containing of all words whose length is a prime number.