In this note, we show that quantum finite automata can be polynomially more succinct than their classical counterparts for promise problems in case of exact computation. Additionally, in terms of language recognition, the same result is shown to be valid up to a constant factor depending on how bigger the size of the alphabet is.
The potential of the exact quantum information processing is an interesting, important and intriguing issue. For examples, it has been believed that quantum tools can provide significant, that is larger than polynomial, advantages in the case of exact quantum computation only, or mainly, for problems with very special structures. We will show that this is not the case. In this paper the potential of quantum finite automata producing outcomes not only with a (high) probability, but with certainty (so called exactly) is explored in the context of their uses for solving promise problems and with respect to the size of automata. It is shown that for solving particular classes [Formula: see text] of promise problems, even those without some very special structure, that succinctness of the exact quantum finite automata under consideration, with respect to the number of (basis) states, can be very small (and constant) though it grows proportional to [Formula: see text] in the case deterministic finite automata (DFAs) of the same power are used. This is here demonstrated also for the case that the component languages of the promise problems solvable by DFAs are non-regular. The method used can be applied in finding more exact quantum finite automata or quantum algorithms for other promise problems.
Some of the most interesting and important results concerning quantum finite automata are those showing that they can recognize certain languages with (much) less resources than corresponding classical finite automata. This paper shows three results of such a type that are stronger in some sense than other ones because (a) they deal with models of quantum finite automata with very little quantumness (so-called semi-quantum one- and two-way finite automata); (b) differences, even comparing with probabilistic classical automata, are bigger than expected; (c) a trade-off between the number of classical and quantum basis states needed is demonstrated in one case and (d) languages (or the promise problem) used to show main results are very simple and often explored ones in automata theory or in communication complexity, with seemingly little structure that could be utilized.
Even though quantum computation is useful for solving certain problems, classical computation is more powerful in some cases. Thus, it is significant to compare the abilities of quantum computation and its classical counterpart, based on such a simple computation model as automata. In this paper we focus on the quantum pushdown automata which were defined by Golovkins in 2000, who showed that the class of languages recognized by quantum pushdown automata properly contains the class of languages recognized by finite automata. However, no one knows the entire relationship between the recognitive abilities of quantum and classical pushdown automata. As a part, we show a proposition that quantum pushdown automata can deterministically solve a certain problem that cannot be solved by any deterministic pushdown automata.
{\it Two-way quantum automata with quantum and classical states} (2QCFA) were introduced by Ambainis and Watrous in 2002. In this paper we study state succinctness of 2QCFA. For any m∈Z+ and any ε<1/2, we show that: {enumerate} there is a promise problem Aeq(m) which can be solved by a 2QCFA with one-sided error ε in a polynomial expected running time with a constant number (that depends neither on m nor on ε) of quantum states and O(logε1) classical states, whereas the sizes of the corresponding {\it deterministic finite automata} (DFA), {\it two-way nondeterministic finite automata} (2NFA) and polynomial expected running time {\it two-way probabilistic finite automata} (2PFA) are at least 2m+2, logm, and 3(logm)/b, respectively; there exists a language Ltwin(m)={wcw∣w∈{a,b}∗} over the alphabet Σ={a,b,c} which can be recognized by a 2QCFA with one-sided error ε in an exponential expected running time with a constant number of quantum states and O(logε1) classical states, whereas the sizes of the corresponding DFA, 2NFA and polynomial expected running time 2PFA are at least 2m, m, and 3m/b, respectively; {enumerate} where b is a constant.
Since some quantum algorithms were introduced by Shor [1] or by Grover [2], much attention has been given to the field of quantum computation.The quantum computation is so useful for solving certain problems, however, the classical computation is more powerful in some cases.Thus, it is significant to compare the ability of quantum computation with the ability of classical counterpart, based on simple computation models, like automata.In this paper, we focus on the quantum pushdown automata, QPAs, which was defined by Golovkins in 2000 [4].It is shown that the class of languages recognized by QPAs contains the class of languages recognized by finite automata.However, no one knows the relationships between the cognitive ablity of QPAs and the classical counterparts.We make a proposition in this paper, the QPAs that deterministically solve a certain problem, which cannot be solved by deterministic pushdown automata.
We continue the systematic investigation of probabilistic and quantum finite automata (PFAs and QFAs) on promise problems by focusing on unary languages. We show that bounded-error QFAs are more powerful than PFAs. But, in contrary to the binary problems, the computational powers of Las-Vegas QFAs and bounded-error PFAs are equivalent to deterministic finite automata (DFAs). Lastly, we present a new family of unary promise problems with two parameters such that when fixing one parameter QFAs can be exponentially more succinct than PFAs and when fixing the other parameter PFAs can be exponentially more succinct than DFAs.