{'fraction_non_alphanumeric': 0.04980223706034959, 'fraction_numerical': 0.015480797856504911, 'mean_word_length': 3.8492472674778306, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 16, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Research report: State complexity of operations on two-way quantum finite automata

This paper deals with the size complexity of minimal {\it two-way quantum finite automata} (2qfa's) necessary for operations to perform on all inputs of each fixed length. Such a complexity measure, known as state complexity of operations, is useful in measuring how much information is necessary to convert languages. We focus on intersection, union, reversals, and catenation operations and show some upper bounds of state complexity of operations on 2qfa's. Also, we present a number of non-regular languages and prove that these languages can be accepted by 2qfa's with one-sided error probabilities within linear time. Notably, these examples show that our bounds obtained for these operations are not tight, and therefore worth improving. We give an instance to show that the upper bound of the state number for the simulation of one-way deterministic finite automata by two-way reversible finite automata is not tight in general.


Background of this topic and relevant results
Finite (state) automata represent one of the most simple form of computation to date. The minimal number of inner states used in a finite automaton has been a focal point of a recent study of finite automata (for example, see [5,9,13,15,16,26,30] and the references therein). Such a number serves as a complexity measure and is generally referred to as state complexity. The importance of the study of state complexity arises from recent applications of finite automata to numerous practical fields, which include natural language and speech processing, software engineering, and image generation and encoding, etc [7,25]. In the literature, there are by and large three distinct streams of studies concerning state complexity of finite automata.
• State complexity of language recognition on a fixed automata model.
• State complexity of transformation of one automata model to another.
• State complexity of operations on a fixed automata model. Indeed, these complexity measures have a long history of their own. In the 1950s, Rabin and Scott [24] showed that an n-state one-way nondeterministic finite automaton (1nfa) is transformed to its equivalent one-way deterministic finite automaton (1dfa) of at most 2 n inner states. This is generally referred to as the state complexity of transformation. The notion of state complexity of operations, on the contrary, dates back to 1981 when Leiss [18] showed that the reversal of a langauge recognized by an n-state 1dfa requires 2 n inner states.
In this paper, we focus on the state complexity of operations on two-way quantum finite automata (2qfa's), which is defined as the minimal number of inner states necessary for a finite automaton to "witness" a given operation on all inputs of each fixed length. An automaton that achieves such minimality is called a minimal automaton.
Since the state complexity dealt with in this report is concerning quantum computing models, we recall some background regarding quantum computing. Exactly, quantum mechanical computationa new breed of nature-inspired computation-has recently drawn wide attention as an alternative computation paradigm [12,20]. The notion of quantum finite automata (qfa's) was introduced by the pioneering work of Moore and Crutchfield [19] and Kondacs and Watrous [17]. The computational model of Kondacs and Watrous is a natural quantization of probabilistic finite automata, which have been studied for more than four decades since its introduction by Rabin [24]. Their model consists of an input tape, a read-only head, and a finite control unit holding an inner state and evolves by a rule of quantum mechanics. As two-way quantum finite automata, the read-only head moves along the input tape in two directions (also being allowed to stay still). A configuration of such a machine is in general in a so-called superposition. The models of Kodacs and Watrous and of Moore and Cruchfield differ in one point: the number of measurements performed during a computation. Specifically, Kodacs and Watrous' models perform measurement each step of computing, whereas Moore and Crutchfield's ones only measure at the end of a computation.
Note that, similar to probabilistic finite automata, 2qfa's and 1qfa's are quite different in power. We are particularly interested in the power of two-way quantum finite automata (2qfa's). Kondacs and Watrous [17] showed that, by exploiting quantum interference, 2qfa's can recognize even non-regular languages, in particular, U pal = {0 n 1 n | n ∈ N} in worst-case linear time. This shows a sharp contrast with the fact that there is a regular language that cannot be recognized by any one-way quantum finite automaton (1qfa) with any constant error bound because of its reversibility constraint. Notably, Amano and Iwama [2] showed that the empty problem for certain restricted 2qfa's (which they call 1.5qfa's) is undecidable.
It is worth mentioning that Ambainis, ect. [1,3], Nayak [21], Brodsky and Pippenger [6], and the others have dealt with some operation properties and state size on quantum finite automata. For example, Ambainis etc. [3] proved that the union of the languages accepted by one-way quantum finite automata with bounded error is not closed.

Our goals and obtained results
A recent interest in practical fields makes state complexity a practically important and theoretically interesting entity. It is natural to discuss state complexity based on quantum finite automata. Is such complexity measure quite different from that classical one? In this paper, we focus our study on the state complexity of operations on fixed automata models, i.e., 2qfa's, that were first proposed and studied by Kodacs and Watrous [17]. We attempt to demonstrate that this complexity measure indeed proves vital in quantum complexity theory.
For notational convenience, we introduce the notation QSC ǫ [L](n) to denote the smallest number of inner states necessary to solve language L on a 2qfa model M with error probability bounded above by ǫ when inputs are exactly length n. To be more precise, for any x ∈ L ∩ Σ n , the probability of accepting x is at least 1 − ǫ, and the probability of rejecting x ∈ L ∩ Σ n is also at least 1 − ǫ, where Σ n denotes the set of strings with length n, and L is the complement of L. For simplicity, we call M accepting L ∩ Σ n with error probability bounded by ǫ.
In this paper, we mainly prove the following results. Theorem 1. For any languages L 1 and L 2 over Σ 1 and Σ 2 respectively, and any n ∈ N , let M 1 and M 2 be the minimum 2qfa for L 1 ∩ Σ n 1 and L 2 ∩ Σ n 2 with error probabilities bounded by ǫ 1 and ǫ 2 , respectively. If M 2 is non-recurrent, then where ǫ = ǫ 1 + ǫ 2 − ǫ 1 ǫ 2 , |Q acc,1 | denotes the number of the rejecting states of M 1 .
Theorem 2. For any language L over Σ, let M be the minimum 2qfa for L with error probability bounded by ǫ. If M is non-recurrent, then for any n ∈ N, where L R denotes the reversal of L, i.e., L R = {x R |x ∈ L} (for x = σ 1 σ 2 . . . σ n , then x R = σ n σ n−1 . . . σ 1 ).
Theorem 3. Let L i be a language over alphabet Σ i with ǫ ∈ L i for i = 1, 2. If Σ 1 ∩ Σ 2 = ∅, and the error probabilities of the minimum 2qfs's M 1 and M 2 accepting L 1 and L 2 are respectively ǫ 1 and ǫ 2 , then the catenation L 1 L 2 is accepted by a 2qfa M with error probability ǫ = ǫ 1 + ǫ 2 − ǫ 1 ǫ 2 .
Then L is accepted by 2qfa with one-sided error in linear time.
Then there exist 2qfa M 1 and M 2 accepting L 1 and L 2 , respectively, with one-sided error in linear time. From the above theorems and propositions it follows a number of corollaries which will be stated in Sections 3 and 4. Also, in order to prove the above results, we need verify some lemmas, that will be detailed in the sequel.

Basic notions and notation
We review some related notions and notation that will be used in this paper. In addition, some will be explained when they appear first.

General definitions
Let N be the set of all natural numbers (that is, nonnegative integers), Z be that of all integers, R be that of all real numbers, and C be that of all complex numbers. Let N + = N − {0}. For any complex number α, α * denotes its conjugate. For any two numbers m, n ∈ N with m < n, the notation [m, n] Z denotes the set {m, m + 1, m + 2, . . . , n}. For any finite set Q, |Q| denotes the cardinality of Q.
We use the notation Σ in general for a nonempty input alphabet (not necessarily be limited to {0, 1}). A string over Σ is a finite sequence of symbols in Σ and the length of a string is the number of occurrences of symbols in the string. In particular, the string of length 0 is called the empty string and often denoted λ. For each number n ∈ N, Σ n denotes the set of all strings over Σ that have length exactly n. Write Σ * for n∈N Σ n . A partial problem over alphabet Σ is a pair (A, B) such that A, B ⊆ Σ * and A ∩ B =. When A ∪ B = Σ * , B becomes the complement of A (denoted Σ * − A) and thus we identify (A, B) with A, which is simply called a language.
We assume the reader's familiarity with classical finite automata. We use the notation REG to denote the collection of all regular languages.
Let A be any m × n complex matrix. The notation A T denotes the transposed matrix of A. Moreover, A † denotes the transposed conjugate of A. For any vector x, x denotes the ℓ 2 -norm. Let A be the operator norm defined as A = max{ Ax : x = 0}. Let A 2 be the Frobenius norm . Let A tr be the trace norm min{|T r(AX † )| : X ≤ 1}.

Quantum finite automata
We briefly give the formal definition of a quantum finite automaton (qfa). Formally, a qfa is described as a sextuple M = (Q, Σ, q 0 , δ, Q acc , Q rej ), where Q is a finite set of inner states with Q acc ∪ Q rej ⊆ Q, Σ is a finite alphabet, q 0 is the initial inner state, and δ is a transition function mapping from Q × Σ to Q × {−1, 0, +1}. The transition function δ is also expressed by a series of transitions define by the complexy number (called an amplitude) δ(p, σ, q, d) for p, q ∈ Q, σ ∈ Σ, and d ∈ {−1, 0, +1}. This means that, assuming that a machine is in inner state p scanning a symbol σ, the machine at next step changes its inner state to q moving its head in direction d. The set Q is partitioned into three sets: Q acc , Q rej , and Q non . Inner states in Q acc (in Q rej , resp.) are called accepting states (rejecting states, resp.). A halting state refers to both an accepting state and a rejecting state. The rest Q non is known as a set of non-halting states. A configuration is a description of a single moment of M 's computation, including an inner state and a head position; we regard Q × [0, |x| + 1] Z as the configuration space on input x. In general, M 's computation is a series of superpositions of configurations, each of which evolves by an application of δ to its predecessor (if not the initial configuration). More generally, we can view an application of δ as an application of a linear operator over a configuration space. More precisely, the operator U n δ with respect to inputs of length n is defined as the linear operator acting on the configuration space CON F n , which is the Hilbert space spanned by {|p, i | q ∈ Q, i ∈ [0, n + 1] Z }, in the following way: , and x i is the ith symbol of x for each i ∈ [1, n] Z . Throughout this paper, we assume that U n δ is always unitary for any n ∈ N.

State complexity by quantum finite automata
We formally introduce the notation of state complexity of langauge recognition on quantum finite automata.

Definition of state complexity
Roughly speaking, the state complexity of a language is the number of inner states of the minimal qfa that recognizes the language with designated error probability. More formally, we say that a language L over alphabet Σ has state complexity s(n) with error probability ǫ and amplitude set K if there exists a 2qfa M n = (Q n , Σ, q 0 , δ n , Q acc,n , Q rej,n ) such that (i) |Q n | ≤ s(n) and (ii) for every When n is concerned, we say that L has state complexity s(n) at n with error probability ǫ. In the literature, qfa's are sometimes specified by their partial transitions because it is easy to expand such partial transitions to standard transitions (see [27,28,29], for example). To discuss the number of inner states, it is therefore important to note that here we consider only "complete" qfa's, which are equipped with transition functions defined completely on the domain Q × Σ.
For notational convenience, we write QSC K,ǫ [L](n) for the minimal number m such that L has state complexity m at n with error probability at most ǫ and with amplitude set K. In particular, when K = C, we omit the subscript K from QSC K,ǫ [L](n) for readability. For comparison, we also introduce the notations for classical state complexity measures. Write DSC[L](n) for the minimal number of inner states of any 2dfa recognizing L. A minimal 2qfa refers to a 2qfa that witnesses QSC K,ǫ [L](n). Moreover, we write PSC ǫ [L](n) for the minimal number of inner states of any 2pfa recognizing L with error probability at most ǫ. Since any 2dfa is also a 2pfa, we clearly obtain the following relationships: Let L be any language and let ǫ resp.), for instance, to emphasize that we use only 2qfa's which run in expected polynomial time (expected linear time, resp.).
In the subsequent subsection, we review basic properties of state complexity defined by 2qfa's.

Fundamental properties
We show several fundamental properties of state complexity measures. Lemma 1. Let L be any language over alphabet Σ, let ǫ be any constant in [0, 1/2), and let K be any amplitude set. Proof.
1) The lower bound comes from the fact that every 2qfa requires the initial inner state and at least one accepting or rejecting inner state. Actually, we can set Q acc = {q 0 } and Q rej = Ø in the case of L = Σ * . In this case, QSC 0 [Σ * ](n) = 1 for all n ∈ N. The upper bound is shown as follows. After the machine reads the left end-marker symbol, the initial state evolves also into initial state. Then the machine needs at most |Σ| states after scanning the first input symbol (since there are only |Σ| symbols). For the second step, there are at most |Σ| states and each evolves at most |Σ| states, which implies that the second step needs at most |Σ| 2 states. Proceeding with this method, we therefore get the above result.
2) By the proof of Proposition 4 in the reference [17] by Kondacs and Watrous, we directly obtain this result. 2 A natural problem is whether or not the bound in Lemma 2 is tight. Indeed, from the following Lemma 2 we know that for some language L we have Proposition 3 stated in Section 1. Therefore it says that it is not tight.
Lemma 2. Let Σ = {a, b}, and let L = {w ∈ Σ * |# a (w) = # b (w) = n}, where n ∈ N, and # a (w) and # b (w) denote respectively the number of a and b in the string w. Then there exists 2qfa (exactly 2rfa, i.e., two-way reversible finite automaton) M with 6n + 4 states to accept L.
One can readily check that the 2rfa constructed above can accept L = {w ∈ Σ * |# a (w) = # b (w) = n} with 6n + 4 states. 2 However, in terms of the Myhill-Nerode Theorem [14], any deterministic finite automaton accepting L needs at least n 2 states. Therefore, for language L above we have that Proposition 3 holds.
for any n ∈ N.
The following lemma is immediate from the definitions of 2QFA, 2QFA(poly-time), and state complexity.

State complexity of basic operations
The main theme of this paper, as stated in Section 1, is to determine the upper bounds of state complexity of basic operations on 2qfa's. First, we consider the operation called "complementation" on 2qfa's. This is the easiest case. From the definition of 2qfa's, we immediately obtain the exact bound as follows. Proof. This is obtained by replacing the roles of Q acc and Q rej .
Also, the well-formed conditions of 2qfa's given by Kodacs and Watrous [17] for justifying the unitarity of evolution will be used in what follows. Therefore we recall these conditions here. A 2qfa M = (Q, Σ, δ, q 0 , Q acc , Q rej ) is well-formed of and only if for any σ, σ 1 , σ 2 ∈ Σ ∪ {| c, $}, and any q 1 q 2 ∈ Q, the following hold.
Theorem 1. For any languages L 1 and L 2 over Σ 1 and Σ 2 respectively, and any n ∈ N , let M 1 and M 2 be the minimum 2qfa for L 1 ∩ Σ n 1 and L 2 ∩ Σ n 2 with error probabilities bounded by ǫ 1 and ǫ 2 , respectively. If M 2 is non-recurrent, then where ǫ = ǫ 1 + ǫ 2 − ǫ 1 ǫ 2 , |Q acc,1 | denotes the number of the rejecting states of M 1 .
The proof of Eq. (7) has certain similarity to Eq. (6). The 2qfa M for (L 1 ∪ L 2 ) ∩ Σ n can be constructed according to the following process. For any x ∈ Σ n , firstly M simulates M 1 , and if M 1 accepts x then M also accepts x; otherwise M continues to simulate M 2 and the rest computation is then completed in terms of M 2 . Therefore, with the analogous idea as above, we construct M = (Q, Σ, δ, q 0 , Q acc , Q rej ) as follows.
Also, δ can be extended to satisfy the well-formed conditions of 2qfa's. Using M to compute string x ∈ (Σ 1 ∪ Σ 2 ) n , we obtain the following results: (i) If x ∈ L 1 ∩ Σ n , then M accepts x with probability at least 1 − ǫ 1 .

2
From Theorem 1 it follows the following corollary.
Corollary 1. For any languages L 1 and L 2 over Σ 1 and Σ 2 respectively, and any n ∈ N , let M 1 and M 2 be the minimum 2qfa for L 1 ∩ Σ n 1 and L 2 ∩ Σ n 2 with error probabilities bounded by ǫ 1 and ǫ 2 , respectively. If the tape head of M 1 stays always at the left end-marker when it enters accepting states, and M 2 is non-recurrent, then if the tape head of M 1 stays always at the left end-marker when it enters rejecting states, and M 2 is non-recurrent, then where ǫ = ǫ 1 + ǫ 2 − ǫ 1 ǫ 2 , |Q acc,1 | denotes the number of the rejecting states of M 1 .
Proof. It is straightforward by the proof of Theorem 1. 2 To show that the above bounds are not tight, we verify the following propositions.
Then L is accepted by 2qfa with one-sided error in linear time.

Proof.
The idea borrows Proposition 2 of [17] in which Kodacs and Watrous proved that nonregular language {a m b m |m ≥ 1} can be accepted by 2qfa with one-sided error in linear time. Here, for any N ∈ N, we construct machine M N in terms of the following idea. First we let machine M N check whether the input is of form a + b + 1 a + b + 2 . If not, then M N rejects it at once; otherwise, let the tape head of M N stays at the right end-marker $, and then check whether or not the length of b 2 and a in the right side equals. If not, then M N rejects it with probability at least 1 − 1 N ; otherwise, with probability one M N continues to check the equality of the length of b 1 and a in the left side. If not, then M N rejects it with probability at least 1 − 1 N ; otherwise, M N accepts it with probability one. Now we give the formal description of M N = (Q, Σ, δ, q 0 , Q acc , Q rej ) where the state set Q consists of the all states appearing in the following, δ(q, σ, p, d) = p|V σ |q , D(p) = d, 0, D(p) = d, and Q acc = {s j,0 = |r Then there exist 2qfa M 1 and M 2 accepting L 1 and L 2 , respectively, with one-sided error in linear time.

2
Next we deal with the reversal of languages accepted by 2qfa's, by demonstrating Theorem 2.
Theorem 2. For any language L over Σ, let M be the minimum 2qfa for L 1 with error probability bounded by ǫ. If M is non-recurrent, then

Proof.
With the condition that M is non-recurrent, we only need add a state q ′ 0 as starting state for constructing a 2qfa M R for L R , and let q ′ 0 change to q 0 with its tape head moving to the right end-marker $. Then M R simulate M in the reversal direction. Formally 2) δ R (q, $, p, d) = δ(q, | c, p, −d) for any q, p ∈ Q; 3) δ R (q, | c, p, d) = δ(q, $, p, −d) for any q, p ∈ Q; 4) δ R (q, σ, p, d) = δ(q, σ, p, −d) for any q, p ∈ Q and any σ ∈ Σ.
Then it is clear that δ R satisfies the well-formed conditions of 2qfa's if δ does. Therefore, the second inequality has been proved. The first inequality is only an inference from the second one, since L = (L R ) R .

2
Finally we deal with catenation operation of 2qfs's. For technical reason, we restrict the 2qfa's to be non-circular, that is, when a machine's tape head is scanning the left end-marker (or the right end-marker), the machine will not move its tape head left (right). Also, in the interest of simplicity, we consider only the languages without ǫ.
In the interest of simplicity, as in Corollary 1, we would like to assume that the tape head of the first machine M 1 stays at the right end-marker when it enters accepting states. Without this assumption one can also cope with it by virtue of the similar way used in the proof of Theorem 1.
Proof. Firstly we let M check whether or not the input is of the form Σ + Σ + . If not, M rejects it immediately; otherwise, M simulate M 1 . If the input is rejected, then M rejects it also; otherwise M continues to simulate M 2 for the second part of the input, and therefore M 2 determines the accepting or rejecting result. Specifically, M = (Q, Σ 1 ∪ Σ 2 , δ, q 0 , Q acc , Q rej ) where δ is defined as follows.
The above process checks whether the input is the form of Σ + 1 Σ + 2 . If it is, M begins with simulating M 1 . Therefore, δ is further defined as follows.
Example. For Σ 1 = {a, b 1 } and Σ 2 = {a, b 2 }, languages L 1 over Σ 1 and L 2 over Σ 2 are respectively defined as: 1 |m ≥ 1} and L 2 = {a m b m 2 |m ≥ 1}. In terms of Proposition 2 of [17], L 1 and L 2 can be accepted by 2qfa's with one-sided error in linear time. As well, by Proposition 1 above, the catenation of L 1 and L 2 as the language over Σ 1 ∪ Σ 2 is accepted by 2qfa with one-sided error in linear time. Therefore, this shows that the conditions such as Σ 1 ∩ Σ 2 = ∅ in Theorem 3 are not necessary. 2

Concluding remarks and future works
In this report, we dealt with the state complexity of some operations (including complementation, intersection, union, reversals, catenation) on two-way quantum finite automata. We proved a number of upper bounds of the size of states for these operations, and also obtained lower bound for reversal operation. Also, we provided in detail a number of non-regular languages and demonstrated that these languages can be accepted by two-way quantum finite automata with one-sided error probabilities in linear time. In terms of these examples we have seen that the bounds obtained for these operations are not tight. Therefore, this motivates to further consider related issues along this direction.
Therefore, the further work is how to improve these bounds to make them optimum, and how to verify related lower bounds for intersection and union. In particular, there are some restricted conditions in these theorems (such as non-recurrent), so, proving these theorems without these conditions is worth further exploring.
As is well-known, classical interactive proof systems [8,11] have played an important role in the study of computational complexity, and have been successfully applied to cryptography systems. Notably, by generalizing the classical interactive proof systems of Dwork and Stockmeyer [11] to quantum framework, Nishimura and Yamakami [22] recently have significantly dealt with quantum interactive proof systems by using 2qfa's. Furthermore, to study zero-knowledge quantum interactive proof systems by using two-way quantum finite automata as verifiers is a significant issue for the future consideration.