The minimum amount of resources to recognize a nonregular language is a fundamental research topic in theoretical computer science which has been examined for different kinds of resources and many different models. In this note, we focus on unary languages and space complexity on counters. Our model is two-way one-counter automaton with quantum and classical states (2QCCA), which is a two-way finite automaton with one-counter (2DCA) augmented with a fixed size quantum register or a two-way finite automaton with quantum and classical states (2QCFA) augmented with a classical counter. It is known that any 2DCA using a sublinear space on its counter can recognize only regular languages \cite{DG82B}. In this note, we show that bounded-error 2QCCAs can recognize a non-regular unary language by using logarithmic space on its counters for the members. Note that it is still an open problem whether bounded-error 2QCFA can recognize a non-regular unary language.
The minimum amount of resources to recognize a nonregular language is a fundamental research topic in theoretical computer science which has been examined for different kinds of resources and many different models. In this note, we focus on unary languages and space complexity on counters. Our model is two-way one-counter automaton with quantum and classical states (2QCCA), which is a two-way finite automaton with one-counter (2DCA) augmented with a fixed size quantum register or a two-way finite automaton with quantum and classical states (2QCFA) augmented with a classical counter. It is known that any 2DCA using a sublinear space on its counter can recognize only regular languages \cite{DG82B}. In this note, we show that bounded-error 2QCCAs can recognize a non-regular unary language by using logarithmic space on its counters for the members. Note that it is still an open problem whether bounded-error 2QCFA can recognize a non-regular unary language.
It is known that poly-time constant-space quantum Turing machines (QTMs) and logarithmic-space probabilistic Turing machines (PTMs) recognize uncountably many languages with bounded error (A.C. Cem Say and A. Yakaryılmaz, Magic coins are useful for small-space quantum machines. Quant. Inf. Comput. 17 (2017) 1027–1043). In this paper, we investigate more restricted cases for both models to recognize uncountably many languages with bounded error. We show that double logarithmic space is enough for PTMs on unary languages in sweeping reading mode or logarithmic space for one-way head. On unary languages, for quantum models, we obtain middle logarithmic space for counter machines. For binary languages, arbitrary small non-constant space is enough for PTMs even using only counter as memory. For counter machines, when restricted to polynomial time, we can obtain the same result for linear space. For constant-space QTMs, we obtain the result for a restricted sweeping head, known as restarting realtime.
The two-way finite automaton with quantum and classical states (2QCFA), defined by Ambainis and Watrous, is a model of quantum computation whose quantum part is extremely limited; however, as they showed, 2QCFA are surprisingly powerful: a 2QCFA with only a single-qubit can recognize the language Lpal={w∈{a,b}∗:w is a palindrome} with bounded error in expected time 2O(n), on inputs of length n. We prove that their result essentially cannot be improved upon: a 2QCFA (of any size) cannot recognize Lpal with bounded error in expected time 2o(n). To our knowledge, this is the first example of a language that can be recognized with bounded error by a 2QCFA in exponential time but not in subexponential time. Moreover, we prove that a quantum Turing machine (QTM) running in space o(logn) and expected time 2n1−Ω(1) cannot recognize Lpal with bounded error; again, this is the first lower bound of its kind. Far more generally, we establish a lower bound on the running time of any 2QCFA or o(logn)-space QTM that recognizes any language L in terms of a natural "hardness measure" of L. This allows us to exhibit a large family of languages for which we have asymptotically matching lower and upper bounds on the running time of any such 2QCFA or QTM recognizer.
Condon and Lipton (FOCS 1989) showed that the class of languages having a space-bounded interactive proof system (IPS) is a proper subset of decidable languages, where the verifier is a probabilistic Turing machine. In this paper, we show that if we use architecturally restricted verifiers instead of restricting the working memory, i.e. replacing the working tape(s) with a single counter, we can define some IPS's for each decidable language. Such verifiers are called two-way probabilistic one-counter automata (2pca's). Then, we show that by adding a fixed-size quantum memory to a 2pca, called a two-way one-counter automaton with quantum and classical states (2qcca), the protocol can be space efficient. As a further result, if the 2qcca can use a quantum counter instead of a classical one, then the protocol can even be public, also known as Arthur-Merlin games. We also investigate the computational power of 2pca's and 2qcca's as language recognizers. We show that bounded-error 2pca's can be more powerful than their deterministic counterparts by giving a bounded-error simulation of their nondeterministic counterparts. Then, we present a new programming technique for bounded-error 2qcca's and show that they can recognize a language which seems not to be recognized by any bounded-error 2pca. We also obtain some interesting results for bounded-error 1-pebble quantum finite automata based on this new technique. Lastly, we prove a conjecture posed by Ravikumar (FSTTCS 1992) regarding 1-pebble probabilistic finite automata, i.e. they can recognize some nonstochastic languages with bounded error.
Although polynomial-time probabilistic Turing machines can utilize uncomputable transition probabilities to recognize uncountably many languages with bounded error when allowed to use double logarithmic space, it is known that such “magic coins” give no additional computational power to constant-space versions of those machines. We show that adding a few quantum bits to the model changes the picture dramatically. For every language L, there exists such a two-way quantum finite automaton (2qcfa) that recognizes a language of the same Turing degree as L with bounded error in polynomial time. When used as verifiers in public-coin interactive proof systems, such automata can verify membership in all languages with bounded error, outperforming their classical counterparts, which are known to fail for the palindromes language. Corollaries demonstrate even faster machines when one is allowed to use a counter as memory, and an alternative proof of the uncountability of stochastic languages.
In this thesis, we introduce a new quantum Turing machine (QTM) model that supports general quantum operators, together with its pushdown, counter, and finite automaton variants, and examine the computational power of classical and quantum machines using small space bounds in many different cases. The main contributions are summarized below. Firstly, we consider QTMs in the unbounded error setting: (i) in some cases of sublogarithmic space bounds, the class of languages recognized by QTMs is shown to be strictly larger than that of classical ones; (ii) in constant space bounds, the same result can still be obtained for restricted QTMs; (iii) the complete characterization of the class of languages recognized by realtime constant space nondeterministic QTMs is given. Secondly, we consider constant space-bounded QTMs in the bounded error setting: (i) we introduce a new type of quantum and probabilistic finite automata (QFAs and PFAs, respectively,) with a special two-way input head which is not allowed to be stationary or move to the left but has the capability to reset itself to its starting position; (ii) the computational power of this type of quantum machine is shown to be superior to that of the probabilistic machine; (iii) based on these models, two-way PFAs and two-way classical-head QFAs are shown to be more succinct than two-way nondeterministic finite automata and their one-way variants; (iv) we also introduce PFAs and QFAs with postselection with their bounded error language classes, and give many characterizations of them. Thirdly, the computational power of realtime QFAs augmented with a write-only memory is investigated by showing many simulation results for different kinds of counter automata. Finally, some lower bounds of realtime classical Turing machines in order to recognize a nonregular language are shown to be tight.
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.