Two-way finite automata with quantum and classical states (2QCFA’s), introduced by Ambainis and Watrous, extend deterministic two-way finite automata with a constant-size quantum register and provide a natural hybrid model of computation. In this paper, we introduce two-way nondeterministic finite automata with quantum and classical states (2QCNFA’s), extending this framework to the nondeterministic setting. We show that 2QCNFA’s are closed under union, intersection, and marked concatenation, and that they can recognize certain comparison languages whose status for 2QCFA’s remains open. We further initiate the study of decision problems for this model by proving that 2QCNFA’s can recognize the set of invalid computations of a deterministic Turing machine, which implies that the universality problem is undecidable. In addition, we investigate descriptional complexity, showing that there is no approximation algorithm for minimization between 2QCNFA’s and classical models such as DFA’s and context-free grammars, and that the corresponding trade-offs are non-recursive.
Two-way finite automata with quantum and classical states (2QCFA’s), introduced by Ambainis and Watrous, extend deterministic two-way finite automata with a constant-size quantum register and provide a natural hybrid model of computation. In this paper, we introduce two-way nondeterministic finite automata with quantum and classical states (2QCNFA’s), extending this framework to the nondeterministic setting. We show that 2QCNFA’s are closed under union, intersection, and marked concatenation, and that they can recognize certain comparison languages whose status for 2QCFA’s remains open. We further initiate the study of decision problems for this model by proving that 2QCNFA’s can recognize the set of invalid computations of a deterministic Turing machine, which implies that the universality problem is undecidable. In addition, we investigate descriptional complexity, showing that there is no approximation algorithm for minimization between 2QCNFA’s and classical models such as DFA’s and context-free grammars, and that the corresponding trade-offs are non-recursive.
{\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.
Quantum finite automata derive their strength by exploiting interference in complex valued probability amplitudes. Of particular interest is the 2-way model of Ambainis and Watrous that has both quantum and classical states (2QCFA) [A. Ambainis and J. Watrous, Two-way finite automata with quantum and classical state, Theoretical Computer Science, 287 (2002) 1, 299-311], since it combines the advantage of the power of interference in a constant-sized quantum system with a 2-way head. This paper is a step towards finding the least powerful model which is purely classical and can mimic the dynamics of quantum phase. We consider weighted automata with the Cortes-Mohri definition of language recognition [C. Cortes and M. Mohri, Context-Free Recognition with Weighted Automata, Grammars 3 (2000) 2/3, 133-150] as a candidate model for simulating 2QCFA. Given any 2QCFA that (i) uses the accept-reject-continue observable, (ii) recognizes a language with one-sided error and (iii) the entries of whose unitary matrices are algebraic complex numbers, we show a method of constructing a weighted automaton over C that simulates it efficiently.
Two-way finite automata with quantum and classical states (2QCFA) were introduced by Ambainis and Watrous, and it was shown that 2QCFA have superiority over two-way probabilistic finite automata (2PFA) for recognizing some non-regular languages such as the language Leq = {anbn ∣ n ∈ N} and the palindrome language Lpal = {w ∈ {a,b}* ∣ w=wR}, where xR is x in the reverse order. It is interesting to find more languages like these that witness the superiority of 2QCFA over 2PFA. In this paper, we consider the language Lm = {xcy ∣ ∑ = {a,b,c},x,y ∈ {a,b}*, ∣x∣ = ∣y∣} that is similar to the middle language Lmiddle = {xay ∣ x,y ∈ {a,b}*, ∣x∣ = ∣y∣}. We prove that the language Lm show that Lm can be recognized by 2PFA with bounded error, but only in exponential expected time. Thus Lm is another witness of the fact that 2QCFA are more powerful than their classical counterparts.
We show that there are quantum devices that accept all regular languages and that are exponentially more concise than deterministic finite automata (DFA). For this purpose, we introduce a new computing model of {\it one-way quantum finite automata} (1QFA), namely, {\it one-way quantum finite automata together with classical states} (1QFAC), which extends naturally both measure-only 1QFA and DFA and whose state complexity is upper-bounded by both. The original contributions of the paper are the following. First, we show that the set of languages accepted by 1QFAC with bounded error consists precisely of all regular languages. Second, we prove that 1QFAC are at most exponentially more concise than DFA. Third, we show that the previous bound is tight for families of regular languages that are not recognized by measure-once (RMO), measure-many (RMM) and multi-letter 1QFA. % More concretely we exhibit regular languages L0(m) for m prime such that: (i) L0(m) cannot be recognized by measure-once, measure-many and multi-letter 1QFA; (ii) the minimal DFA that accepts L0(m) has O(m) states; (iii) there is a 1QFAC with constant classical states and O(log(m)) quantum basis that accepts L0(m). Fourth, we give a polynomial-time algorithm for determining whether any two 1QFAC are equivalent. Finally, we show that state minimization of 1QFAC is decidable within EXPSPACE. We conclude the paper by posing some open problems.
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.
One-way quantum finite automata together with classical states (1QFAC) proposed in [Journal of Computer and System Sciences 81(2) (2015) 359--375] is a new one-way quantum finite automata (1QFA) model that integrates quantum finite automata (QFA) and deterministic finite automata (DFA). This model uses classical states to control the evolution and measurement of quantum states. As a quantum-classical hybrid model, 1QFAC recognize all regular languages. It was shown that the state complexity of 1QFAC for some languages is essentially superior to that of DFA and other 1QFA. In this paper, our goal is to clarify state complexity problems for 1QFAC. We obtain the following results: (1) We optimize the bound given by Qiu et al. that characterizes the relationship between quantum basis state number and classical state number of 1QFAC as well as the state number of its corresponding minimal DFA for recognizing any given regular language. (2) We give an upper bound showing that how many classical states are needed if the quantum basis states of 1QFAC are reduced without changing its recognition ability. (3) We give a lower bound of the classical state number of 1QFAC for recognizing any given regular language, and the lower bound is exact if the given language is finite. (4) We show that 1QFAC are exponentially more succinct than DFA and probabilistic finite automata (PFA) for recognizing some regular languages that can not be recognized by measure-once 1QFA (MO-1QFA), measure-many 1QFA (MM-1QFA) or multi-letter 1QFA. (5) We reveal essential relationships between 1QFAC, MO-1QFA and multi-letter 1QFA, and induce a result regarding a quantitative relationship between the state number of multi-letter 1QFA and DFA.