We explore bounds of {em time-space tradeoffs} in language recognition on {em two-way finite automata} for some special languages. We prove: (1) a time-space tradeoff upper bound for recognition of the languages $L_{EQ}(n)$ on {em two-way probabilist
ic finite automata} (2PFA): $TS={bf O}(nlog n)$, whereas a time-space tradeoff lower bound on {em two-way deterministic finite automata} is ${bf Omega}(n^2)$, (2) a time-space tradeoff upper bound for recognition of the languages $L_{INT}(n)$ on {em two-way finite automata with quantum and classical states} (2QCFA): $TS={bf O}(n^{3/2}log n)$, whereas a lower bound on 2PFA is $TS={bf Omega}(n^2)$, (3) a time-space tradeoff upper bound for recognition of the languages $L_{NE}(n)$ on exact 2QCFA: $TS={bf O}(n^{1.87} log n)$, whereas a lower bound on 2PFA is $TS={bf Omega}(n^2)$. It has been proved (Klauck, STOC00) that the exact one-way quantum finite automata have no advantage comparing to classical finite automata in recognizing languages. However, the result (3) shows that the exact 2QCFA do have an advantage in comparison with their classical counterparts, which has been the first example showing that the exact quantum computing have advantage in time-space tradeoff comparing to classical computing. Usually, two communicating parties, Alice and Bob, are supposed to have an access to arbitrary computational power in {em communication complexity} model that is used. Instead of that we will consider communication complexity in such a setting that two parties are using only finite automata and we prove in this setting that quantum automata are better than classical automata and also probabilistic automata are better than deterministic automata for some well known tasks.
The concept of promise problems was introduced and started to be systematically explored by Even, Selman, Yacobi, Goldreich, and other scholars. It has been argued that promise problems should be seen as partial decision problems and as such that the
y are more fundamental than decision problems and formal languages that used to be considered as the basic ones for complexity theory. The main purpose of this paper is to explore the promise problems accepted by classical, quantum and also semi-quantum finite automata. More specifically, we first introduce two acceptance modes of promise problems, recognizability and solvability, and explore their basic properties. Afterwards, we show several results concerning descriptional complexity on promise problems. In particular, we prove: (1) there is a promise problem that can be recognized exactly by measure-once one-way quantum finite automata (MO-1QFA), but no deterministic finite automata (DFA) can recognize it; (2) there is a promise problem that can be solved with error probability $epsilonleq 1/3$ by one-way finite automaton with quantum and classical states (1QCFA), but no one-way probability finite automaton (PFA) can solve it with error probability $epsilonleq 1/3$; and especially, (3) there are promise problems $A(p)$ with prime $p$ that can be solved {em with any error probability} by MO-1QFA with only two quantum basis states, but they can not be solved exactly by any MO-1QFA with two quantum basis states; in contrast, the minimal PFA solving $A(p)$ with any error probability (usually smaller than $1/2$) has $p$ states. Finally, we mention a number of problems related to promise for further study.
State complexity of quantum finite automata is one of the interesting topics in studying the power of quantum finite automata. It is therefore of importance to develop general methods how to show state succinctness results for quantum finite automata
. One such method is presented and demonstrated in this paper. In particular, we show that state succinctness results can be derived out of query complexity results.
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 exac
t 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 ${A^n}_{n=1}^{infty}$ 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 $n$ 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.
In the {em distributed Deutsch-Jozsa promise problem}, two parties are to determine whether their respective strings $x,yin{0,1}^n$ are at the {em Hamming distance} $H(x,y)=0$ or $H(x,y)=frac{n}{2}$. Buhrman et al. (STOC 98) proved that the exact {em
quantum communication complexity} of this problem is ${bf O}(log {n})$ while the {em deterministic communication complexity} is ${bf Omega}(n)$. This was the first impressive (exponential) gap between quantum and classical communication complexity. In this paper, we generalize the above distributed Deutsch-Jozsa promise problem to determine, for any fixed $frac{n}{2}leq kleq n$, whether $H(x,y)=0$ or $H(x,y)= k$, and show that an exponential gap between exact quantum and deterministic communication complexity still holds if $k$ is an even such that $frac{1}{2}nleq k<(1-lambda) n$, where $0< lambda<frac{1}{2}$ is given. We also deal with a promise version of the well-known {em disjointness} problem and show also that for this promise problem there exists an exponential gap between quantum (and also probabilistic) communication complexity and deterministic communication complexity of the promise version of such a disjointness problem. Finally, some applications to quantum, probabilistic and deterministic finite automata of the results obtained are demonstrated.
Equality and disjointness are two of the most studied problems in communication complexity. They have been studied for both classical and also quantum communication and for various models and modes of communication. Buhrman et al. [Buh98] proved that
the exact quantum communication complexity for a promise version of the equality problem is ${bf O}(log {n})$ while the classical deterministic communication complexity is $n+1$ for two-way communication, which was the first impressively large (exponential) gap between quantum and classical (deterministic and probabilistic) communication complexity. If an error is tolerated, both quantum and probabilistic communication complexities for equality are ${bf O}(log {n})$. However, even if an error is tolerated, the gaps between quantum (probabilistic) and deterministic complexity are not larger than quadratic for the disjointness problem. It is therefore interesting to ask whether there are some promis
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 cite{Amb98,Amb09,AmYa11,Ber05,Fr
e09,Mer00,Mer01,Mer02,Yak10,ZhgQiu112,Zhg12}. 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 automata with very little quantumness (so-called semi-quantum one- and two-way automata with one qubit memory only); (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.
