Abuzer Yakaryılmaz
email: abuzer@boun.edu.tr

A C Cem

Succinctness of two-way probabilistic and quantum finite automata † ‡

Keywords: quantum and probabilistic automata, succinctness, probability amplification

We introduce a new model of two-way finite automaton, which is endowed with the capability of resetting the position of the tape head to the left end of the tape in a single move during the computation. Several variants of this model are examined, with the following results: The weakest known model of computation where quantum computers recognize more languages with bounded error than their classical counterparts is identified. We prove that two-way probabilistic and quantum finite automata (2PFAs and 2QFAs) can be considerably more concise than both their one-way versions (1PFAs and 1QFAs), and two-way nondeterministic finite automata (2NFAs). For this purpose, we demonstrate several infinite families of regular languages which can be recognized with some fixed probability greater than 1 2 by just tuning the transition amplitudes of a 2QFA (and, in one case, a 2PFA) with a constant number of states, whereas the sizes of the corresponding 1PFAs, 1QFAs and 2NFAs grow without bound. We also show that 2QFAs with mixed states can support highly efficient probability amplification.

Introduction

In recent years, the research effort on quantum versions of finite automata has mainly focused on oneway models, with the study of two-way quantum finite automata (2QFAs), which are synonymous with constant space quantum Turing machines, receiving relatively less attention. In their seminal paper, Kondacs and Watrous [START_REF] Kondacs | On the power of quantum finite state automata[END_REF] proved that 2QFAs recognize all regular languages with zero error, and the language L eq = {a n b n | n ≥ 0} with any desired error bound > 0, in time O( 1 |w|), using O( 1 2 ) states, where w is the input string. Since two-way probabilistic finite automata (2PFAs) can decide L eq only in exponential time [START_REF] ¸š | Probabilistic two-way machines[END_REF][START_REF] Greenberg | A lower bound for probabilistic algorithms for finite state machines[END_REF][START_REF] Kan | Minimal nontrivial space complexity of probabilistic one-way Turing machines[END_REF][START_REF] Dwork | Finite state verifiers I: The power of interaction[END_REF], this established the superiority of 2QFAs over 2PFAs. Paralleling work by Aharonov et al. [START_REF] Aharonov | Quantum circuits with mixed states[END_REF] on quantum circuits with mixed states, Ambainis and Watrous [START_REF] Ambainis | Two-way finite automata with quantum and classical states[END_REF] introduced an alternative model, the two-way finite automaton with quantum and classical states (2QCFA), which includes a constant-size quantum part which may be in a mixed state, but requires the tape head position to be classical. Yakaryılmaz and Say [START_REF] Yakaryılmaz | Efficient probability amplification in two-way quantum finite automata[END_REF] noted that conventional methods of probability amplification give significantly inefficient results when applied to 2QFAs, and presented methods which can be used to decide L eq with error bound in as low as O(|w|) steps (i.e. with runtime independent of ), and with as low as O(log 2 ( 1 ) log log( 1 )) states.

In this paper, we introduce a new model of two-way finite automaton, which is endowed with the capability of resetting the position of the tape head to the left end of the tape in a single move during the computation. A restricted quantum version of these machines, called the one-way quantum finite automaton with restart (1QFA ), which can switch only to the initial state during left resets, and cannot perform single-step left or stationary moves, is shown to be the weakest known model of computation where quantum computers recognize more languages with bounded error than their classical counterparts. The classical counterpart of the same version is compared with the standard 2PFA model.

We use this new model in the proofs of several facts about the properties of well-known models of probabilistic and quantum two-way finite automata. As our main result, we demonstrate several infinite families of regular languages which can be recognized with some fixed probability greater than 1 2 by just tuning the transition amplitudes of a 2QFA (and, in one case, a 2PFA) with a constant number of states, whereas the sizes of the corresponding one-way machines, and two-way nondeterministic finite automata (2NFAs) grow without bound.

The Kondacs-Watrous model of quantum finite automaton (to be called, from now on, KWQFA), which allows measurements of a restricted type, rather than the full set sanctioned by quantum theory, has been proven to be weaker in terms of language recognition power [START_REF] Kondacs | On the power of quantum finite state automata[END_REF], probability amplification capability [START_REF] Ambainis | 1-way quantum finite automata: strengths, weaknesses and generalizations[END_REF], and, in some cases at least, succinctness [START_REF] Ambainis | Dense quantum coding and quantum finite automata[END_REF], than the corresponding classical model, in the one-way case. More general models, such as the 2QCFA, employing mixed states, are able to simulate the corresponding classical probabilistic automata efficiently in both the one-way and two-way settings, and to recognize some languages that 2PFAs cannot [START_REF] Ambainis | Two-way finite automata with quantum and classical states[END_REF]. We show that 2QFAs with mixed states can support highly efficient probability amplification, surpassing the best known methods for 2KWQFAs recognizing these languages.

The rest of this paper is structured as follows: Section 2 contains the definitions and some basic facts about our new model that will be used throughout the paper. In Section 3, we prove some key lemmata about the relationship between one-way quantum finite automata with and without restart, and examine the class of languages recognized with bounded error by 1QFA 's. Our main succinctness result is presented in Section 4. In Section 5, we present several algorithms that improve previous results about the efficiency of probability amplification in 2KWQFAs and 2QCFAs. In Section 6, we investigate the computational power of probabilistic finite automata with restart. Section 7 is a conclusion.

Preliminaries

Watrous [START_REF] Watrous | On the power of 2-way quantum finite state automata[END_REF] notes that a 2KWQFA algorithm he presents for recognizing a nonregular language is remarkably costly in terms of probability amplification, and states that this problem stems from the fact that 2KWQFAs cannot "reset" themselves during execution to repeatedly carry out the same computation. The 2QCFA model provides one way of solving this problem, by having a classical part, in addition to the quantum register. We present an alternative 2QFA model, employing only quantum states, whose only difference from the 2KWQFA is the existence of an additional "reset move" in its repertory. Section 2.1 contains the definitions of this and the other models that will be examined in the paper. Section 2.2 describes some facts which will make the analyses of the algorithms in later sections easier.

Definitions

Let Σ be an input alphabet, not containing the end-marker symbols ¢ and $, and let Γ = Σ ∪ {¢, $} be the tape alphabet.

A 2-way quantum finite automaton with reset (2QFA ) is a 7-tuple

M = (Q, Σ, δ, q 0 , Q acc , Q rej , Q reset = ∪ q∈Qnon Q q ), (1)
where 1. Q = {q 0 , . . . , q n } is the finite set of states;

2. δ is the transition function, described below;

3. q 0 ∈ Q is the initial state;

4. Q acc is the set of accepting states;

5. Q rej is the set of rejecting states;

6. Q non = Q \ (Q acc ∪ Q rej ∪ Q reset )
is the set of nonhalting and nonresetting states;

7. Q reset is the union of disjoint reset sets, i.e., each Q q∈Qnon contains reset states that cause the computation to restart with state q, as described below.

We assume that the states in Q non have smaller indices than other members of Q;

q i ∈ Q non for 0 ≤ i < |Q non |.
The configurations of a 2QFA are pairs of the form (state, head position). Initially, the head is on the left end-marker ¢, and so the machine starts computation in the superposition |q 0 , 0 .

The transition function of a 2QFA working on an input string w ∈ Σ * , (that is, a tape containing w = ¢w$,) is required to induce a unitary operator U w δ on the Hilbert space 2 (Q × Z |w| ), since quantum machines can exist in superpositions of more than one configuration.

In all 2QFA 's described in this paper, every transition entering the same state involves the tape head moving in the same direction (left, right, or stationary). With this simplification, considering the Hilbert space 2 (Q), a syntactically correct 2QFA (that is, one where U w δ is unitary for every w,) can be specified easily by just providing a unitary operator

U σ : 2 (Q) → 2 (Q) for each symbol σ ∈ Γ. More formally, δ(q, σ, q , d q ) = q |U σ |q (2)
is the amplitude with which the machine currently in state q and scanning symbol σ will jump to state q and move the head in direction d q . Here, d q ∈ {-1, 0, 1} is the direction of the tape head determined by q . For the remaining directions, all transitions with target q have amplitude zero. Apart from the left reset capability, 2QFA 's are identical to 2KWQFAs. In the following, we focus on this new capability, and refer the reader to [START_REF] Kondacs | On the power of quantum finite state automata[END_REF] for detailed coverage of the technical properties of 2KWQFAs.

In each step of its execution, a 2QFA undergoes two linear operations: The first one is a unitary transformation of the current superposition according to δ, and the second one is a measurement. The observable describing this measurement process is designed so that the outcome of any observation is one of "accept", "reject", "continue without resetting", or "reset with state q", for any q ∈ Q non . Formally, we use the observable O, corresponding to the decomposition

E = E acc ⊕ E rej ⊕ E non ⊕ E reset-0 ⊕ E reset-1 ⊕ • • • ⊕ E reset-(k-1) , (3)
where k = |Q non |, and for a given input w,

1. the set of all configurations of the 2QFA is Q × Z |w| ; 2. E = span{|c | c ∈ Q × Z |w| }; 3. E acc = span{|c | c ∈ Q acc × Z |w| }; 4. E rej = span{|c | c ∈ Q rej × Z |w| }; 5. E non = span{|c | c ∈ Q non × Z |w| }; 6. E reset-i = span{|c | c ∈ Q qi∈Qnon × Z |w| } (0 ≤ i ≤ k -1).
The probability of each outcome is determined by the amplitudes of the relevant configurations in the present superposition. The contribution of each configuration to this probability is the modulus squared of its amplitude. For instance, the outcome "reset with state q i " will be measured with probability

c∈Q q i ×Z |w| |α c | 2
, where α c is the amplitude of configuration c. If "accept" or "reject" is measured, the computation halts. If "continue without resetting" is measured, the machine continues running from a superposition of the nonhalting and nonresetting configurations, obtained by normalizing the projection of the superposition before the measurement onto span{|c |c ∈ Q non × Z |w| }. If "reset with state q i " is measured, the tape head is reset to point to the left end-marker, and the machine continues from the superposition |q i , 0 in the next step. Note that the decoherence associated with this measurement means that the system allows mixed states.

A 2QFA M is said to recognize a language L with error bounded by if M's computation results in "accept" being measured for all members of L with probability at least 1 -, and "reject" being measured for all other inputs with probability at least 1 -.

A 2-way quantum finite automaton with restart (2QFA ) is a restricted 2QFA in which the "reset moves" can target only the original start state of the machine, that is, in terms of Equation 1, all the Q q of a 2QFA are empty, with the exception of Q q0 , represented as Q restart .

The two-way probabilistic finite automaton (2PFA) is the classical probabilistic counterpart of 2KWQ-FAs; see [Fre81, Kan ¸91] for the details. A one-way probabilistic finite automaton (1PFA) [START_REF] Michael | Probabilistic automata[END_REF] is a 2PFA in which the head moves only to the right in every step. A rational 1PFA [START_REF] Turakainen | On languages representable in rational probabilistic automata[END_REF] is a 1PFA where all entries in the transition matrices are rational numbers.

Other variants of two-way automata with reset that will be examined in this paper are 1. A one-way (Kondacs-Watrous) quantum finite automaton with reset (1QFA ) is a restricted 2QFA which uses neither "move one square to the left" nor "stay put" transitions, and whose tape head is therefore classical, 2. A one-way (Kondacs-Watrous) quantum finite automaton with restart (1QFA ) is a 1QFA where the reset moves can target only the original start state, and, 3. A one-way probabilistic finite automaton with restart (1PFA ) is a 1PFA which has been enhanced with the capability of resetting the tape head to the left end-marker and swapping to the original start state.

A one-way (Kondacs-Watrous) quantum finite automaton (1KWQFA) [START_REF] Kondacs | On the power of quantum finite state automata[END_REF] is a 2KWQFA which moves its tape head only to the right in every step.

A well-known two-way mixed-state model is the 2QCFA [START_REF] Ambainis | Two-way finite automata with quantum and classical states[END_REF]. Formally, a 2-way finite automaton with quantum and classical states (2QCFA) is a 9-tuple M = (Q, S, Σ, Θ, δ, q 0 , s 0 , S acc , S rej ),

where 1. Q = {q 0 , . . . , q n1 } is the finite set of the quantum states;

2. S = {s 0 , . . . , s n2 } is the finite set of the classical states;

3. Θ and δ govern the machine's behavior, as described below;

4. q 0 ∈ Q is the initial quantum state; 5. s 0 ∈ S is the initial classical state;

6. S acc ⊂ S is the set of classical accepting states;

7. S rej ⊂ S is the set of classical rejecting states.

The functions Θ and δ specify the evolution of the quantum and classical parts of M, respectively. Both functions take the currently scanned symbol σ ∈ Γ and current classical state s ∈ S as arguments. Θ(s, σ) is either a unitary transformation, or an orthogonal measurement. In the first case, the new classical state and tape head direction (left, right, or stationary) are determined by δ, depending on s and σ. In the second case, when an orthogonal measurement is applied on the quantum part, δ determines the new classical state and the tape head direction using the result of that measurement, as well as s and σ. The quantum and classical parts are initialized with |q 0 and s 0 , respectively, and the tape head starts on the first cell of the tape, on which ¢w$ is written for a given input string w ∈ Σ * . During the computation, if an accepting or rejecting state is entered, the machine halts with the relevant response to the input string.

Note that like the 1QFA , and unlike the 2QFA and the 2QFA , the tape head position of a 2QCFA is classical, (that is, there are no superpositions with the head in more than one position simultaneously,) meaning that the machine can be implemented using a quantum part of constant size.

Basic facts

We start by stating some basic facts concerning automata with restart, which will be used in later sections.

A segment of computation which begins with a (re)start, and ends with a halting or restarting configuration will be called a round. Clearly, every automaton with restart which makes nontrivial use of its restarting capability will run for infinitely many rounds on some input strings. Throughout this paper, we make the assumption that our two-way automata do not contain infinite loops within a round, that is, the computation restarts or halts with probability 1 in a finite number steps for each round.

Everywhere in this section, R will stand for a finite state automaton with restart, and w ∈ Σ * will represent an input string using the alphabet Σ.

Definition 1

• p acc (R, w), p rej (R, w), and p restart (R, w) denote the probabilities that R will accept, reject, or restart, respectively, on input w, in the first round.

• P acc (R, w) and P rej (R, w) denote the overall acceptance and rejection probabilities of w by R, respectively.

Moreover, p halt (R, w) = p acc (R, w) + p rej (R, w).

Lemma 1

P acc (R, w) = 1 1 + prej (R,w) pacc(R,w) ; P rej (R, w) = 1 1 + pacc(R,w) prej (R,w)
.

(5)

Proof:

P acc (R, w) = ∞ i=0 (1 -p acc (R, w) -p rej (R, w)) i p acc (R, w) = p acc (R, w) 1 1 -(1 -p acc (R, w) -p rej (R, w)) = p acc (R, w) p acc (R, w) + p rej (R, w) = 1 1 + prej (R,w) pacc(R,w)
.

P rej (R, w) is calculated in the same way. 2

Lemma 2 The language L ⊆ Σ * is recognized by R with error bound > 0 if and only if

prej (R,w) pacc(R,w) ≤ 1-when w ∈ L, and pacc(R,w) prej (R,w) ≤ 1-when w / ∈ L. Furthermore, if prej (R,w) pacc(R,w) ( pacc(R,w) prej (R,w) ) is at most , then P acc (R, w) (P rej (R, w)) is at least 1 -. Proof: This follows from Lemma 1, since, for all p ≥ 0, ∈ [0, 1 2 ), 1 1 + p ≥ 1 -⇔ p ≤ 1 - , and (6)
p ≤ ⇒ 1 1 + p ≥ 1 -. (7)
2 Lemma 3 Let p = p halt (R, w), and let s(w) be the maximum number of steps in any branch of a round of R on w. The worst-case expected runtime of R on w is

1 p (s(w)). (8)
Proof: The worst-case expected running time of R on w is

∞ i=0 (i + 1)(1 -p) i (p)(s(w)) = (p)(s(w)) 1 p 2 = 1 p (s(w)). (9)
2 Lemma 4 Any one-way automaton with restart with expected runtime t can be simulated by a corresponding two-way automaton without restart in expected time no more than 2t.

Proof: The program of the two-way machine (R 2 ) is identical to that of the one-way machine with restart (R 1 ), except for the fact that each restart move of R 1 is imitated by R 2 by moving the head one square per step all the way to the left end-marker. This causes the runtimes of the i nonhalting rounds in the summation in Equation ( 9) in Lemma 3 to increase by a factor of 2. 2

We will now give a quick review of the technique of probability amplification. Suppose that we are given a machine (with or without reset) A, which recognizes a language L with error bounded by , and we wish to construct another machine which recognizes L with a much smaller, but still positive, probability of error, say, . It is well known (i) that one can achieve this by running A O(log( 1 )) times on the same input, and then giving the majority answer as our verdict about the membership of the input string in L.

Suppose that the original machine A needs to be run 2k + 1 times for the overall procedure to work with the desired correctness probability. Two counters can be used to count the acceptance and rejection responses, and the overall computation accepts (rejects) when the number of recorded acceptances (rejections) reaches k + 1. To implement these counters in the finite automaton setting, we need to "connect" (k + 1) 2 copies of A, {A i,j | 0 ≤ i, j ≤ k}, where the subscripts indicate the values of the two counters, i.e., the states of A i,j encode the information that A has accepted i times and rejected j times in its previous runs. The new machine M is constructed from the A i,j 's as follows:

• The start state of M is the start state of A 0,0 ;

• Upon reaching any accept state of A i,j (0 ≤ i, j < k), M moves the head back to the left endmarker and then switches to the start state of A i+1,j ;

• Upon reaching any reject states of A i,j (0 ≤ i, j < k), M moves the head back to the left endmarker and then switches to the start state of A i,j+1 ;

• The accept states of M are the accept states of A k,j (0 ≤ j < k);

• The reject states of M are the reject states of A i,k (0 ≤ i < k).

Lemma 5 If language L ⊆ Σ * is recognized by R with a fixed error bound > 0, then for any positive error bound < , there exists a finite automaton with reset, R , recognizing L . Moreover, if R has n states and its (expected) runtime is O(s(|w|)), then R has O(log 2 ( 1 )n) states, and its (expected) runtime is O(log( 1 )s(|w|)), where w is the input string.

(i) See, for instance, pages 369-370 of [START_REF] Sipser | Introduction to the Theory of Computation[END_REF].

Proof: Follows easily from the above description. 2

Finally, we note the following relationship between the computational powers of the 2QCFA and the 1QFA .

Lemma 6 For any 1QFA M 1 with n states and expected runtime t(|w|), there exists a 2QCFA M 2 with n quantum states, O(n) classical states, and expected runtime O(t(|w|)), such that M 2 accepts every input string w with the same probability that M 1 accepts w.

Proof: We utilize the 2QCFAs ability of making arbitrary orthogonal measurements. Given a 1QFA M 1 , we construct a 2QCFA M 2 with the same set of quantum states. On each tape square, M 2 first performs the unitary transformation associated with the current symbol by the program of M 1 . It then makes a measurement (over the space spanned by the set of quantum states) using an observable O , which is formed by replacing each subspace of the form E reset-i in the observable O (Equation 3) of M 1 (ii) by its subspaces

{E reset-i-qi 1 ⊕ E reset-i-qi 2 ⊕ • • • ⊕ E reset-i-qi m },
where {q i1 , q i2 , . . . , q im } = Q qi , and

E reset-i-qi j = span{|q ij } (1 ≤ j ≤ m).
The outcome associated with E reset-i-qi j is simply the name of q ij . M 2 takes the action specified below according to the result of this observation:

1. "continue without resetting": move the head one square to the right, 2. "accept": accept, 3. "reject": reject, 4. "q ij ": enter a classical state that moves the head left until the left end-marker ¢ is seen, and perform a unitary transformation that transforms the quantum register from state q ij to q i . 2

3 Computational power of 1QFA 's

In this section, we focus on the 1QFA , which turns out to be the simplest and most restricted known model of quantum computation that is strictly superior in terms of bounded-error language recognition to its classical counterpart.

Our first result shows that 1QFA 's can simulate any 1PFA with small state cost, albeit with great slowdown. Note that no such relation is known between the 2KWQFA and its classical counterpart, the 2PFA, in the bounded error case.

Theorem 1 Any language L ⊆ Σ * recognized by an n-state 1PFA with error bound can be recognized by a 2n + 4-state 1QFA with the same error bound. Moreover, if the expected runtime of the 1PFA is O(s(|w|)), then the expected runtime of the 1QFA is O(l 2|w| s 2 (|w|)) for a constant l > 1 depending on n, where w is the input string.

(ii) Since the head is classical, the observable is redefined to be a decomposition of the space spanned by just the set of states.

Proof: Let P be an n-state 1PFA recognizing L with error bound . We will construct a 2n + 4-state 1QFA M recognizing the same language with error bound ≤ .

By adding two more states, s acc and s rej , to P, we obtain a new 1PFA , P , where the halting of the computation in each round is postponed to the last symbol, $, on which the overall accepting and rejecting probabilities are summed up into s acc and s rej , respectively. Therefore, for any given input string w ∈ Σ * , the value of s acc and s rej are p acc (P, w) and p rej (P, w), respectively, at the end of the first round.

By using the method described in [START_REF] Yakaryılmaz | Languages recognized with unbounded error by quantum finite automata[END_REF][START_REF] Yakaryılmaz | Unbounded-error quantum computation with small space bounds[END_REF], each stochastic matrix can be converted to a unitary one with twice the size as shown in the template

U = 1 l (A | B) D ,
where A is the original stochastic matrix; the columns of B, corresponding to newly added states, are filled in to ensure that each row of (A | B) is pairwise orthogonal to the others, and has the same length l, which depends only on the dimension of A, and the entries of D are then selected to make U a unitary matrix.

Each transition matrix of P can be converted to a (2n + 4) × (2n + 4)-dimensional unitary matrix according to this template. These are the transition matrices of M. The state set of M can be specified as follows:

1. The states corresponding to s acc and s rej are the accepting and rejecting states, q acc and q rej , respectively, 2. the states corresponding to the non-halting and non-restarting states of P are non-halting and nonrestarting states, respectively, and, 3. all remaining states are restarting states.

The initial state of M is the state corresponding to the initial state of P.

When M runs on input string |w|, the amplitudes of q acc and q rej , the only halting states of M, at the end of the first round are 1 l |w|+2 p acc (P, w) and 1 l |w|+2 p rej (P, w), respectively. Therefore, when

w ∈ L, p rej (M, w) p acc (M, w) = p 2 rej (P, w) p 2 acc (P, w) ≤ 2 (1 -) 2 ,
and similarly, when w / ∈ L,

p acc (M, w) p rej (M, w) = p 2 acc (P, w) p 2 rej (P, w) ≤ 2 (1 -) 2 .
By solving the equation

1 - = 2 (1 -) 2 ,
we obtain

= 2 1 -2 + 2 2 ≤ .
The expected runtime of P is

1 p acc (P, w) + p rej (P, w) ∈ O(s(|w|)),
and so the expected runtime of M is

(l) 2|w|+4 1 p 2 acc (P, w) + p 2 rej (P, w) < 3 (l) 2|w|+4 1 p acc (P, w) + p rej (P, w) 2 ∈ O(l 2|w| s 2 (|w|)).

2

Corollary 1 1QFA 's can recognize all regular languages with zero error.

To establish the strict superiority of 1QFA 's over 1PFA 's, we will make use of the following concepts.

An automaton M is said to recognize a language L with positive one-sided unbounded error if every input string w ∈ L is accepted by M with nonzero probability, and every w / ∈ L is rejected by M with probability 1. An automaton M is said to recognize a language L with negative one-sided unbounded error if every input string w ∈ L is accepted by M with probability 1, and every w / ∈ L is rejected by M with nonzero probability. In the cases described in the previous two sentences, if L is also recognized with bounded error by M, it is said to be recognized with positive (respectively, negative) one-sided bounded error.

For an automaton M recognizing a language L, we define the gap function, g M : N → [0, 1], such that g M (n) is the difference between the minimum acceptance probability of a member of L with length at most n and the maximum acceptance probability of a non-member of L with length at most n (iii) .

Lemma 7 If a language L is recognized by a 1KWQFA M with positive (negative) one-sided unbounded error such that g M (n) ≥ c -n for some c > 1, then for all ∈ (0, 1 2 ), L is recognized by some 1QFA having three more states than M with positive (negative) one-sided error in expected time O( 1 c |w| |w|).

Proof: We consider the case of positive one-sided error. The adaptation to the other case is trivial. M is converted into a 1QFA M as follows. M starts by branching to two equiprobable paths, path 1 and path 2 , at the beginning of the computation. path 1 imitates the computation of M, except that all reject states that appear in its subpaths are replaced by restart states. Regardless of the form of the input, path 2 moves right with amplitude 1 √ c , (and so restarts the computation with the remaining probability,) on every input symbol. When it arrives at the right end-marker, path 2 rejects with amplitude √ , and restarts the computation with amplitude √ 1 -. When w / ∈ L, p acc (M , w) = 0, and p rej (M , w) = 2c |w| , and so the input is rejected with probability 1. When w ∈ L, p acc (M , w) ≥ 1 2c |w| , and p rej (M , w) = 2c |w| , (iii) The definition of g M is due to Bertoni and Carpentieri [START_REF] Bertoni | Regular languages accepted by quantum automata[END_REF], who call it the "error function."

and so the input is accepted with error bound > 0 due to Lemma 2, since p rej (M , w) p acc (M , w) ≤ .

Since p halt (M , w) is always greater than 2c |w| , the expected runtime of

M is O( 1 c |w| |w|). 2
Lemma 8 If a language L is recognized by a 1KWQFA M with positive (negative) one-sided bounded error such that g M (n) ≥ c -1 for some c > 1, then for all ∈ (0, 1 2 ), L is recognized by some 1QFA having three more states than M with positive (negative) one-sided error in expected time O( 1 c|w|).

Proof: The construction is almost identical to that in Lemma 7, except that path 2 rejects with amplitude √ , and restarts the computation with amplitude √ 1immediately on the left end-marker, thereby causing every input to be rejected with the constant probability 2c . Hence, the expected runtime of M turns out to be O( 1 c|w|). 2

Lemma 7 is a useful step towards an eventual characterization of the class of languages that are recognized with one-sided bounded error by 1QFA 's, since full classical characterizations are known [YS] for the classes of languages recognized by one-sided unbounded error by several 1QFA models, including the 1KWQFA.

A language L is said to belong to the class S = rat [START_REF] Turakainen | On languages representable in rational probabilistic automata[END_REF][START_REF] Macarie | Closure properties of stochastic languages[END_REF] if there exists a rational 1PFA that accepts all and only the members of L with probability 1 2 . Theorem 2 For every language L ∈ S = rat , there exists a number n such that for all error bounds > 0, there exist n-state 1QFA 's that recognize L and L with one-sided error bounded by .

Proof: For a language L in S = rat , let P be the rational 1PFA associated by L as described above. Turakainen [START_REF] Turakainen | On languages representable in rational probabilistic automata[END_REF] showed that there exists a constant b > 1 such that for any string w / ∈ L, the probability that P accepts w cannot be in the interval ( 1 2 -b -|w| , 1 2 + b -|w| ). By using the method described in [YS], we can convert P to a 1KWQFA M recognizing L with one-sided unbounded error, so that M accepts any w ∈ L with probability greater than c -|w| , for a constant c > b. We can conclude with Lemma 7. 2 S = rat contains many well-known languages, such as L eq , L pal = {w | w = w R }, L twin = {wcw | w ∈ {a, b} * }, L mult = {x#y#z | x, y, z are natural numbers in binary notation and x × y = z}, L square = {a n b n 2 | n > 0}, L power = {a n b 2 n }, the word problem for finitely generated free groups, and all polynomial languages, [Tur82] defined as

{a n1 1 • • • a n k k b p1(n1,...,n k ) 1 • • • b pr(n1,...,n k ) r | p i (n 1 , . . . , n k ) ≥ 0},
where a 1 , . . . , a k , b 1 , . . . , b r are distinct symbols, and each p i is a polynomial with integer coefficients. Note that Theorem 2 and Lemma 6 answer a question posed by Ambainis and Watrous [AW02] about whether L square and L power can be recognized with bounded error by 2QCFAs affirmatively.

Corollary 2 The class of languages recognized by 1QFA 's with bounded error properly contains the class of languages recognized by 1PFA 's.

Proof: This follows from Theorems 1 and 2, Lemma 4, and the fact [DS92, FK94] that L pal cannot be recognized with bounded error by 2PFAs. 2

Since general 1QFAs [Pas00, Hir08, YS10] are known to be equivalent in language recognition power to 1PFAs, one has to consider a two-way model to demonstrate the superiority of quantum computers over classical ones. The 2QCFA is known [START_REF] Ambainis | Two-way finite automata with quantum and classical states[END_REF] to be superior to its classical counterpart, the 2PFA, also by virtue of L pal . Recall that, by Lemma 6, 2QCFAs can simulate 1QFA 's easily, and we do not know of a simulation in the other direction.

Conciseness of 2QFAs with mixed states and 2PFAs

In this section, we demonstrate several infinite families of regular languages which can be recognized with some fixed probability greater than 1 2 by just tuning the transition amplitudes of a 1QFA with a constant number of states, whereas the sizes of the corresponding 1QFAs, 1PFAs, and 2NFAs grow without bound. One of our constructions can be adapted easily to show that 1PFA 's, (and, equivalently, 2PFAs), also possess the same advantage over those machines.

Definition 2 For an alphabet Σ containing symbols a and b, and m ∈ Z + , the family of languages A m is defined as

A m = {ua | u ∈ Σ * , |u| ≤ m}.
Note that Ambainis et al. [START_REF] Ambainis | Dense quantum coding and quantum finite automata[END_REF] report that any Nayak one-way quantum finite automaton (iv) that recognizes A m with some fixed probability greater than 1 2 has 2 Ω(m) states. Theorem 3 A m is recognized by a 6-state 1QFA M m, for any error bound > 0. Moreover, the expected runtime of M m, on input w is O( 1 2m |w|). iv) This is a 1QFA model of intermediate power, subsuming the 1KWQFA, but strictly weaker than the most general models ([Pas00, Hir08, YS10]) which recognize any regular language with at most the same state cost as the corresponding DFA.

Proof: Let M m, = {Q, Σ, δ, q 0 , Q acc , Q rej , Q restart } be a 1QFA with Q non = {q 0 , q 1 }, Q acc = {A}, Q rej = {R}, Q restart = {I 1 , I 2 }. M m, contains the transitions U ¢ |q 0 = |q 1 + 2m+5 2 |R + 1 -2 -2m+5 |I 1 U a |q 0 = |q 0 + 1 2 -2 |I 1 + 1 √ 2 |I 2 U a |q 1 = |q 0 + 1 2 -2 |I 1 - 1 √ 2 |I 2 U Σ\{a} |q 0 = |q 1 + 1 2 -2 |I 1 + 1 √ 2 |I 2 U Σ\{a} |q 1 = |q 1 + 1 2 -2 |I 1 - 1 √ 2 |I 2 U $ |q 0 = |A U $ |q 1 = |R (
and the transitions not mentioned above can be completed easily, by extending each U σ to be unitary. On the left end-marker, M m, rejects with probability 2m+5 , goes on to scan the input string with amplitude , and restarts immediately with the remaining probability. States q 0 and q 1 implement the check for the regular expression Σ * a, but the machine restarts with probability 1 -2 on all input symbols during this check.

If w = uσ for u ∈ Σ * , and σ = a, the input is rejected with probability 1, since p acc (M m, , w) = 0.

If w = ua for u ∈ Σ * , p acc (M m, , w) = 2|w|+2 , p rej (M m, , w) = 2m+5 . Hence, if w ∈ A m , p acc (M m, , w) ≥ 2m+4 ,
and if w / ∈ A m , p acc (M m, , w) ≤ 2m+6 .
In both cases, the corresponding ratio prej (Mm, ,w) pacc(Mm, ,w) or pacc(Mm, ,w) prej (Mm, ,w) is not greater than . Thus, by Lemma 2, we conclude that M m, recognizes A m with error bounded by . Since p halt (M m, , w) is always greater than 2m+5 , the expected runtime of M m, is O( 1 2m |w|).

2

By a theorem of Rabin [START_REF] Michael | Probabilistic automata[END_REF], for any fixed error bound, if a language L is recognized with bounded error by a 1PFA with n states, then there exists a deterministic finite automaton (DFA) that recognizes L with 2 O(n) states. Parallelly, Freivalds et al. [START_REF] Rūsin ¸š Freivalds | Improved constructions of mixed state quantum automata[END_REF] note that one-way quantum finite automata with mixed states are no more than superexponentially more concise than DFAs. These facts can be used to conclude that a collection of 1PFAs (or 1QFAs) with a fixed common number of states that recognize an infinite family of languages with a fixed common error bound less than 1 2 , à la the two-way quantum automata of Theorem 3, cannot exist, since that would imply the existence of a similar family of DFAs of fixed size. By the same reasoning, the existence of such families of 2NFAs can also be overruled.

The reader should note that there exists a bounded-error 1PFA (and therefore, a 2PFA (v) ,) for A m , which one can obtain simply by replacing each transition amplitude of 1QFA M m, defined in Theorem 3 by the square of its modulus. This establishes the fact that 2PFAs also possess the succinctness advantage discussed above over 1PFAs, 1QFAs and 2NFAs.

We proceed to present two more examples.

Definition 3 For m ∈ Z + , the language family B m ⊆ {a} * is defined as

B m = {a i | i mod (m) ≡ 0}.
Theorem 4 For any error bound > 0, there exists a 7-state 1QFA M m, which accepts any w ∈ B m with certainty, and rejects any w / ∈ B m with probability at least 1 -. Moreover, the expected runtime of M m, on w is O 1 sin -2 ( π m )|w| .

Proof: We will construct a 4-state 1KWQFA recognizing B m with positive one-sided unbounded error, as described in [START_REF] Ambainis | 1-way quantum finite automata: strengths, weaknesses and generalizations[END_REF]. Let M m = (Q, Σ, δ, q 0 , Q acc , Q rej ) be 1KWQFA with Q non = {q 0 , q 1 }, (v) See Section 6 for an examination of the relationship between the computational powers of the 1PFA and the 2PFA.

Q acc = {A}, Q rej = {R}. M m contains the transitions U ¢ |q 0 = |q 0 U a |q 0 = cos( π m )|q 0 + sin( π m )|q 1 U a |q 1 = -sin( π m )|q 0 + cos( π m )|q 1 U $ |q 0 = |R U $ |q 1 = |A ,
and the transition amplitudes not listed above are filled in to satisfy unitarity. M m begins computation at the |q 0 -axis, and performs a rotation by angle π m in the |q 0 -|q 1 plane for each a it reads. Therefore, the value of the gap function, g Mm , is not less than sin 2 ( π m ) for |w| > 0. By Lemma 8, there exists a 7state 1QFA M m, recognizing B m with positive one-sided bounded error and whose expected runtime is O 1 sin -2 ( π m )|w| . By swapping the accepting and rejecting states of M m, , we can get the desired machine.

2

Definition 4 For an alphabet Σ, and m ∈ Z + , the language family C m is defined as

C m = {w ∈ Σ * | |w| = m}.
Theorem 5 For any error bound > 0, there exists a 7-state 1QFA M m, which accepts any w ∈ C m with certainty, and rejects any w / ∈ C m with probability at least 1 -. Moreover, the expected runtime of M m, on w is O( 1 2 m |w|).

Proof: We will contruct a 4-state 1KWQFA recognizing C m with positive one-sided unbounded error.

Let M m = (Q, Σ, δ, q 0 , Q acc , Q rej ) be 1KWQFA with Q non = {q 0 , q 1 }, Q acc = {A}, Q rej = {R}. M m contains the transitions U ¢ |q 0 = 1 √ 2 |q 0 + 1 √ 2 m+1 |q 1 + 1 2 - 1 2 m+1 |R U σ∈Σ |q 0 = 1 √ 2 |q 0 + 1 √ 2 |R U σ∈Σ |q 1 = |q 1 U $ |q 0 = 1 √ 2 |A + 1 √ 2 |R U $ |q 1 = - 1 √ 2 |A + 1 √ 2 |R
with the amplitudes of the transitions not mentioned above filled in to ensure unitarity.

M m encodes the length of the input string in the amplitude of state q 0 , which equals 1 √ 2 |w|+1 just before the processing of the right end-marker. The desired length m is "hardwired" into the amplitudes of q 1 . For a given input string w ∈ Σ * , if w ∈ C m , then the amplitudes of states q 0 and q 1 are equal, and the quantum Fourier transform (QFT) [START_REF] Kondacs | On the power of quantum finite state automata[END_REF] performed on the right end-marker sets the amplitude of A to 0. Therefore, w is rejected with certainty. If w ∈ C m , then the accepting probability is equal to

1 √ 2 |w|+2 - 1 √ 2 m+2 2
, and it is minimized when |w| = m + 1, which gives us the inequality

g Mm (w) > 1 2 m+6 .
By Lemma 8, there exists a 7-state 1QFA M m, recognizing C m with positive one-sided bounded error and whose expected runtime is O 1 2 m |w| . By swapping the accepting and rejecting states of M m, , we can get the desired machine. 2

Note that, unlike what we had with Theorem 3, the QFAs of Theorems 4 and 5 cannot be converted so easily to 2PFAs. In fact, we can prove that there exist no 2PFA families of fixed size which recognize B m and C m with fixed one-sided error less than 1 2 , like those QFAs: Assume that such a 2PFA family exists. Switch the accept and reject states to obtain a family for the complements of the languages. The 2PFAs thus obtained operate with cutpoint 0. Obtain an equivalent 2NFA with the same number of states by converting all transitions with nonzero weight to nondeterministic transitions. But there are only finitely many 2NFAs of this size, meaning that they cannot recognize our infinite family of languages.

Efficient Probability Amplification

Many automaton descriptions in this paper, and elsewhere in the theory of probabilistic and quantum automata, describe not a single algorithm, but a general template which one can use for building a machine M that operates with a desired error bound . The dependences of the runtime and number of states of M on 1 are measures of the complexity of the probability amplification process involved in the construction method used. Viewed as such, the constructions described in the theorems in Section 4 are maximally efficient in terms of the state cost, with no dependence on the error bound. In this section, we present improvements over previous results about the efficiency of probability amplification in 2QFAs.

Improved algorithms for L eq

In classical computation, one only needs to sequence O(log( 1 )) identical copies of a given probabilistic automaton with one sided error p < 1 to run on the same input in order to obtain a machine with error bound . Yakaryılmaz and Say [START_REF] Yakaryılmaz | Efficient probability amplification in two-way quantum finite automata[END_REF] noted that this method of probability amplification does not yield efficient results for 2KWQFAs; the number of machine copies required to reduce the error to can be as high as ( 1 ) 2 . The most succinct 2KWQFAs for L eq produced by alternative methods developed in [START_REF] Yakaryılmaz | Efficient probability amplification in two-way quantum finite automata[END_REF] have O(log 2 ( 1 ) log log( 1 )) states, and runtime linear in the size of the input w. In Appendix Appendix A, we present a construction which yields (exponential time) 1QFA 's that recognize L eq within any desired error bound , with no dependence of the state set size on . Ambainis and Watrous [START_REF] Ambainis | Two-way finite automata with quantum and classical states[END_REF] present a method which can be used to build 2QCFAs that recognize L eq also with constant state set size, where the "tuning" of the automaton for a particular error bound is achieved by setting some transition amplitudes appropriately, and the expected runtime of those machines is O(|w| 4 ). We now show that the 2QFA formalism allows more efficient probability amplification.

Theorem 6 There exists a constant n, such that, for any > 0, an n-state 2QFA which recognizes L eq with one-sided error bound within O( 1 |w|) expected runtime can be constructed, where w is the input string.

Proof: We start with Kondacs and Watrous' original 2KWQFA [START_REF] Kondacs | On the power of quantum finite state automata[END_REF] M N , which recognizes L eq with one-sided error 1 N , for any integer N > 1. After a deterministic test for membership of a * b * , M N branches to N computational paths, each of which perform a QFT at the end of the computation. Set N = 2. M 2 accepts all members of L eq with probability 1. Non-members of L eq are rejected with probability at least 1 2 . We convert M 2 to a 2QFA M by changing the target states of the QFT as follows:

path 1 → 1 √ 2 |Reject + 2 |Accept + 1 - 2 |Restart path 2 → - 1 √ 2 |Reject + 2 |Accept + 1 - 2 |Restart
where the amplitude of each path is 1 √ 2 . For a given input w ∈ Σ * , 1. if w is not of the form a * b * , then p rej (M , w) = 1;

2. if w is of the form a * b * and w / ∈ L, then p rej (M , w) = 1 2 , and p acc (M , w) = 2 ; 3. if w ∈ L, then p rej (M , w) = 0 and p acc (M , w) = .

It is easily seen that the error is one-sided. Since pacc(M ,w) prej (M ,w) = , we can conclude with Lemma 2. Moreover, the minimum halting probability occurs in the third case above, and so the expected runtime of M is O( 1 |w|). 2

Theorem 7 For any ∈ (0, 1 2 ), there exists a 2QFA with O(log( 1 )) states that recognizes L eq with one-sided error bound in O(log( 1 )|w|) steps, where w is the input string.

Proof: Let M 2 be the 2KWQFA recognizing L eq with one-sided error bound 1 2 mentioned in the proof of Theorem 6. Then, a 2QFA that is constructed by sequentially connecting O(log( 1 )) copies of M 2 , so that the input is accepted only if it is accepted by all the copies, and rejected otherwise, can recognize L eq with one-sided error bound . 2

An improved algorithm for L pal

Ambainis and Watrous [START_REF] Ambainis | Two-way finite automata with quantum and classical states[END_REF] present a 2QCFA construction which decides L pal in expected time O( 1 |w| |w|) with error bounded by > 0, where w is the input string. (Watrous [Wat98] describes a 2KWQFA which accepts all members of the complement of L pal with probability 1, and fails to halt for all palindromes; it is not known if 2KWQFAs can recognize this language by halting for all inputs.) We will now present a 1QFA construction, which, by Lemma 6, can be adapted to yield 2QCFAs with the Proof: We will first construct a modified version of the 1KWQFA algorithm of Lāce et al. [START_REF] Lāce | Languages recognizable by quantum finite automata with cut-point 0[END_REF] for recognizing the nonpalindrome language. The idea behind the construction is that we encode both the input string and its reverse into the amplitudes of two of the states of the machine, and then perform a substraction between these amplitudes using the QFT [START_REF] Lāce | Languages recognizable by quantum finite automata with cut-point 0[END_REF]. If the input is not a palindrome, the two amplitudes do not cancel each other completely, and the nonzero difference is transferred to an accept state. Otherwise, the accepting probability will be zero.

Paths U ¢ , Ua U b U ¢ |q0 = 1 √ 2 |p1 + 1 √ 2 |q1 path1 Ua|p1 = 2 3 |p1 -1 √ 3 |R1 Ua|p2 = 1 √ 6 |p1 + 1 √ 6 |p2 + 1 √ 3 |R1 + 1 √ 3 |R2 U b |p1 = 1 √ 6 |p1 + 1 √ 6 |p2 + 1 √ 3 |R1 + 1 √ 3 |R2 U b |p2 = 2 3 |p2 -1 √ 3 |R1 path2 Ua|q1 = 1 √ 6 |q1 + 1 √ 6 |q3 -1 √ 3 |R3 + 1 √ 3 |R4 Ua|q2 = 2 3 |q2 + 1 √ 3 |R5 Ua|q3 = 2 3 |q3 + 1 √ 3 |R3 U b |q1 = 1 √ 6 |q1 + 1 √ 6 |q2 -1 √ 3 |R3 + 1 √ 3 |R4 U b |q2 = 2 3 |q2 + 1 √ 3 |R3 U b |q3 = 2 3 |q3 + 1 √ 3 |R5 U $ path1 U $ |p1 = |R1 U $ |p2 = 1 √ 2 |A + 1 √ 2 |R2 path2 U $ |q1 = |R3 U $ |q2 = -1 √ 2 |A + 1 √ 2 |R2 U $ |q3 = |R4
Let M = (Q, Σ, δ, q 0 , Q acc , Q rej ) be 1KWQFA with Q non = {p 1 , p 2 , q 0 , q 1 , q 2 , q 3 } ,

Q acc = {A}, Q rej = {R i | 1 ≤ i ≤ 5}.
The transition function of M is shown in Figure 1. As before, we assume that the transitions not specified in the figure are filled in to ensure that the U σ are unitary. path 2 and path 1 encode the input string and its reverse [START_REF] Michael | Probabilistic automata[END_REF][START_REF] Paz | Introduction to Probabilistic Automata[END_REF] into the amplitudes of states q 2 and p 2 , respectively. If the input is w = w 1 w 2 • • • w l , then the values of these amplitudes just before the transition associated with the right end-marker in the first round are as follows:

• State p 2 has amplitude 1 √ 2 2 3 |w| (0.w l w l-1 • • • w 1 ) 2 , and • state q 2 has amplitude 1 √ 2 2 3 |w| (0.w 1 w 2 • • • w l ) 2 .
The factor of 2 3 is due to the "loss" of amplitude necessitated by the fact that the originally non-unitary encoding matrices of [START_REF] Michael | Probabilistic automata[END_REF][START_REF] Paz | Introduction to Probabilistic Automata[END_REF] have to be "embedded" in a unitary matrix [START_REF] Yakaryılmaz | Languages recognized with unbounded error by quantum finite automata[END_REF][START_REF] Yakaryılmaz | Unbounded-error quantum computation with small space bounds[END_REF]. Note that the symbols a and b are encoded by 0 and 1, respectively.

If w ∈ L pal , the acceptance probability is zero. If w ∈ L pal , the acceptance probability is minimized by strings which are almost palindromes, except for a single defect in the middle, that is, when |w| = 2k for k ∈ Z + , w i = w 2k-i+1 , where 1 ≤ i ≤ k -1, and w k = w k+1 , so, Note that the technique used in the proof above can be extended easily to handle bigger input alphabets by using the matrices defined on Page 169 of [START_REF] Paz | Introduction to Probabilistic Automata[END_REF], and the method of simulating stochastic matrices by unitary matrices described in [START_REF] Yakaryılmaz | Languages recognized with unbounded error by quantum finite automata[END_REF][START_REF] Yakaryılmaz | Unbounded-error quantum computation with small space bounds[END_REF].

g M (w) ≥ 1

1PFA vs. 2PFA

It is interesting to examine the power of the restart move in classical computation as well. Any 1PFA which runs in expected t steps can be simulated by a 2PFA which runs in expected 2t steps (see Lemma 4). We ask in this section whether the restart move can substitute the "left" and "stationary" moves of a 2PFA without loss of computational power. Since every polynomial-time 2PFA recognizes a regular language, which can of course be recognized by using only "right" moves, we focus on the best-known example of a nonregular language that can be recognized by an exponential-time 2PFA.

Theorem 9 There exists a natural number k, such that for any > 0, there exists a k-state 1PFA P recognizing language L eq with error bound and expected runtime O(( 22 ) |w| |w|), where w is the input string.

Proof: We will construct the 1PFA P as follows: Let x = 2 2 . The computation splits into three paths called path 1 , path 2 , and path 3 with equal probabilities on symbol ¢. All three paths, while performing their main tasks, parallelly check whether the input is of the form a * b * , if not, all paths simply reject. The main tasks of the paths are as follows:

• path 1 moves on with probability x and restarts with probability 1 -x when reading symbols a and b. After reading the right end-marker $, it accepts with probability with 1.

• path 2 moves on with probability x 2 and restarts with probability 1 -x 2 when reading symbol a. On b's, it continues with the "syntax" check. After reading the $, it rejects with probability 2 and restarts with probability 1 -2 .

• path 3 is similar to path 2 , except that the transitions of symbols a and b are interchanged.

If the input is of the form a m b n , then the accept and reject probabilities of the first round are calculated as p acc (P , w) = 1 3

x m+n , and p rej (P , w) = 6 x 2m + x 2n .

If m = n, then p rej (P , w) p acc (P , w) = .

If m = n (assume without loss of generality that m = n + d for some d ∈ Z + ) , then states, where the number b depends on and the constant hidden in the big-O. The two-way machines of Section 4 can be seen to have such factors that grow with m in the expressions for their time complexities; this is how the machines described in that section achieve their huge superiority in terms of the state cost over the other models that they are compared with.

p
It is known [YS09b, YS10, FYS10] that 2KWQFAs can recognize some nonstochastic languages (i.e. those which cannot be recognized by 2PFAs) in the unbounded error setting. On the other hand, we conjecture that 2QFAs with classical head position, such as the 2QCFA, cannot recognize any nonstochastic language. Therefore, it is an interesting question whether 2QFA 's (or possibly an even more general 2QFA model allowing head superposition) can recognize any nonstochastic language with bounded error or not.

Some other open questions related to this work are:

1. Can 1QFA 's simulate 2QCFAs?

2. Are 1PFA 's (with just "restart" and "right" moves) equivalent in power to 2PFAs in the boundederror setting, as hinted by Section 6?

3. Does there exist an analogue of the Dwork-Stockmeyer theorem mentioned above for two-way quantum finite automata?

Fig. 1 :

 1 Fig. 1: Specification of the transition function of M same complexity, which reduces the dependence of the Ambainis-Watrous method on the desired error bound considerably.Theorem 8 For any > 0, there exists a 15-state 1QFA M which accepts any w ∈ L pal with certainty, and rejects any w / ∈ L pal with probability at least 1 -. Moreover, the expected runtime of M on w is O( 1 3 |w| |w|).

  By Lemma 7, there exists a 15-state 1QFA M recognizing L pal with positive one-sided bounded error, whose expected runtime is O( 1 3 |w| |w|). By swapping accepting and rejecting states of M m , we can get the desired machine.2

		1
	8	3

|w|

.

  By using Lemma 2, we can conclude that P recognizes L eq with error bound .Since p halt (P , w) is always greater than 1 3 x |w| , the expected runtime of the algorithm is O(( 2 2 ) |w| |w|), where w is the input string. 2 7 Concluding remarks By a theorem of Dwork and Stockmeyer [DS90], for every < 1 2 , if L is recognized by a O(n)-time 2PFA with c states within error probability , then L is also recognized by a DFA with c bc 2

			acc (P , w) p rej (P , w)	=	2	x 2n+d x 2n+2d + x 2n =	2 x d x 2d + 1	<	2 x d ≤	2 x
		2
	By replacing x =	2	, we can get
						p acc (P , w) p rej (P , w)	< .

Acknowledgements

We are grateful to Andris Ambainis and John Watrous for their helpful comments on earlier versions of this paper. We also thank Rūsin ¸š Freivalds for kindly providing us a copy of reference [LSDF09].

‡ This work was partially supported by the Scientific and Technological Research Council of Turkey (T ÜB İTAK) with grant 108142 and the Bogazic ¸i University Research Fund with grant 08A102. 1365-8050

Appendix A A 1QFA algorithm for L eq Theorem 10 For any > 0, there exists a 15-state 1QFA M , which accepts any w ∈ L eq with certainty, and rejects any w / ∈ L eq with probability at least 1 -. Moreover, the expected runtime of

Proof: We will contruct a 12-state 1KWQFA recognizing L eq with positive one-sided unbounded er-

Fig. 2: Specification of the transition function of M assume that the transitions not specified in the figure are filled in to ensure that the U σ are unitary. As seen in the figure, M branches to two paths on the left end-marker. Both paths reject immediately if the input w ∈ {a, b} * is the empty string, and accept with nonzero probability, say α, if it is of the form

, and the amplitudes of the paths just before the transition associated with the right end-marker in the first round are as follows:

If m = n, then the accepting probability is zero. If m = n (assume without loss of generality that m = n + d for some d ∈ Z + ), then the accepting probability is equal to

Since α is always greater than this value,

, for |w| > 0. By Lemma 7, there exists a 15-state 1QFA M recognizing L eq with positive one-sided bounded error and whose expected runtime is O( 1 (2 √ 2) |w| |w|). By swapping accepting and rejecting states of M m , we can get the desired machine.


Ying Liu
email: liuying@lixin.edu.cn

The Laplacian spread of Cactuses

Keywords: Cactus, Laplacian spread, Laplacian eigenvalues

Connected graphs in which any two of its cycles have at most one common vertex are called cactuses. In this paper, we continue the work on Laplacian spread of graphs, and determine the graph with maximal Laplacian spread in all cactuses with n vertices.

Introduction

Let G = (V, E) be a simple connected graph with vertex set V = {v 1 , v 2 , • • • , v n } and edge set E. Denote by d i (or d(v i )) the degree of the vertex v i of the graph G. Let A(G) be the adjacency matrix of G and L(G) = D(G)-A(G) be the Laplacian matrix of the graph G, where D(G) =diag(d 1 , d 2 , • • • , d n ) denotes the diagonal matrix of vertex degrees of G. It is easy to see that L(G) is a positive semidefinite symmetric matrix and its rows sum to 0, so L(G) is singular. Denote its eigenvalues by µ 1 (G) ≥ µ 2 (G) ≥ • • • ≥ µ n (G) = 0, which are always enumerated in non-increasing order and repeated according to their multiplicities. We call the largest eigenvalue of L(G) the Laplacian spectral radius of the graph G, denoted by µ(G). Moreover, since G is connected if and only if µ n-1 (G) > 0, Fielder [START_REF] Fielder | Algebra connectivity of graphs[END_REF][START_REF] Fielder | A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory[END_REF] thought, in a sense, µ n-1 (G) as a quantitative measure of connectivity. Hence he called µ n-1 (G) the algebraic connectivity of G and denoted by α(G). The Laplacian spread of the graph G is defined to be

ϕ L (G) = µ(G) -α(G).
The notion of Laplacian spread is very significant in characterizing the global structural property of graphs. Recently, Fan et al [START_REF] Fan | The Laplacian spread of a tree[END_REF] have showed that, among all trees with n vertices, K 1,n-1 and P n are the unique trees with the maximal Laplacian spread and minimal Laplacian spread, respectively. Bao [START_REF] Bao | The Laplacian spread of unicyclic graphs[END_REF] et al determined the graph with maximal in all unicyclic graphs.

Connected graphs in which any two of its cycles have at most one common vertex are called cactuses. Throughout this paper, the characteristic polynomial det(xI row and column corresponding to the vertex v. Let C n be the set of cactuses with n vertices. In this paper, we continue the work on Laplacian spread of graphs, and determine the graph class C 1 (see Fig. 1) with maximal Laplacian spread in all C n (n ≥ 10), where C 1 is the graph class by gluing one vertex of s triangles to the maximum degree vertex of K 1,r (2s + r = n -1), respectively. Now, we give the main theorem in this paper:

-L(G)) is denoted by Φ(G; x), or simply Φ(G). If v ∈ V (G), let L v (G)
Theorem 1 Let G ∈ C n -{C 1 } (n ≥ 5), then ϕ L (G) = µ(G) -α(G) < n -1 = ϕ L (C 1 ).
2 Proof of Theorem 1

The following lemmas are necessary for our main results. Denote by

N (v) the neighborhood of the vertex v ∈ V (G). Lemma 2 ([10]) Let G be a connected graph, then µ(G) ≤ max{d(v i ) + d(v j ) -|N (v i ) ∩ N (v j )| : v i = v j }.
uu i1 u i2 • • • u ipi (i = 1, • • • , s) at u and t new paths vv j1 v j2 • • • v jpj (j = 1, • • • , t) at v, respectively. Suppose ∆(G) ≥ 3. Let X be a unit eigenvector of G corresponding to µ(G). Let R G (u, W, v) = G -vv 11 -vv 21 -• • • -vv t1 + uv 11 + uv 21 + • • • + uv t1 where W = {v 11 , • • • , v t1 }. Then µ(G) ≤ max{µ(R G (u, W, v)), µ(R G (v, W , u))} where W = {u 11 , • • • , u s1 } and this inequality is strict if |x u | = |x v |. Lemma 5 ([7]
) Let G be a connected graph of n vertices and with a cutpoint v. Then

0 < α(G) ≤ 1,
the equality holds if and only if v is adjacent to every other vertex of G.

Lemma 6 [START_REF] Shao | The ordering of trees and connected graphs by algebraic connectivity[END_REF] Let G be a connected graph on n vertices. Suppose that

v 1 , v 2 , • • • , v s (s ≥ 2) are pairwisely non-adjacent vertices of G and N (v 1 ) = N (v 2 ) = • • • = N (v s ). Let G t be a graph obtained from G by adding any t (0 ≤ t ≤ s(s -1) 2 ) edges among v 1 , v 2 , • • • , v s , then we have µ(G) = µ(G t ).
Lemma 7 ( [START_REF] Ji-Ming | On the second largest Laplacian eigenvalue of trees[END_REF]) Let G = G 1 u : vG 2 be the graph obtained by joining the vertex u of the graph G 1 to the vertex v of the graph G 2 by an edge. Then (2) If u, v are not adjacent, then d(u) + d(v) ≤ n.

Φ(L(G)) = Φ(L(G 1 ))Φ(L(G 2 )) -Φ(L(G 1 ))Φ(L v (G 2 )) -Φ(L(G 2 ))Φ(L u (G 1 )). Lemma 8 Let G ∈ C n and u, v ∈ V (G), then (1)
Proof: Since for any u, v ∈ V (G), we have

d(u) + d(v) -|N (u) ∩ N (v)| = |N (u) ∪ N (v)| ≤ n, then (1) If u, v are adjacent, we know |N (u) ∪ N (v)| ≤ n, |N (u) ∩ N (v)| ≤ 1, so d(u) + d(v) ≤ n + 1. ( 2) If u, v are not adjacent, we know |N (u) ∪ N (v)| ≤ n -2, |N (u) ∩ N (v)| ≤ 2, so d(u) + d(v) ≤ n. 2
From (1), Lemma 3 and by Lemma 5, for

G ∈ C 1 we obtain µ(G) = n and α(G) = 1, respectively. Then ϕ L (G) = µ(G) -α(G) = n -1, so ϕ L (C 1 ) = µ(C 1 ) -α(C 1 ) = n -1.

Combining (1) and Lemma 2, we know if

G ∈ C n -{C 1 } and |N (u) ∪ N (v)| ≤ n -1 for all u, v ∈ V (G), then µ(G) ≤ n -1, thus ϕ L (G) = µ(G) -α(G) < n -1 = ϕ L (C 1 ).
So in the followings we may always assume that there exist u, v ∈ V (G) such that

d(u) + d(v) -|N (u) ∩ N (v)| = |N (u) ∪ N (v)| = n.
We introduce some notations. Let T i (p, q) (i = 1, 2, 3) be a tree obtained from P i+1 by adding p, q pendent edges to a pendent vertex, respectively.

Each unicyclic graph can be obtained by attaching rooted trees to the vertices of a cycle

C k of length k. Thus if R 1 , • • • , R k are k rooted trees (of orders n 1 , • • • , n k , say), then we adopt the notation U k (R 1 , • • • , R k ) (or simply U (R 1 , • • • , R k ) sometime for convenience) to denote the unicyclic graph G (of order n = n 1 + • • • + n k ) obtained by attaching the rooted tree R i to the vertex v i of a cycle C k = v 1 v 2 • • • v k v 1 (i.e., by identifying the root of R i with the vertex v i ) for i = 1, • • • , k.
In order to prove our main theorem, we give three graph classes G 1 , G 2 and G 3 . Fig. 2:

Ying

Lemma 9 Let G ∈ C n (n ≥ 5) and G ∈ {G 1 , G 2 , G 3 }, then ϕ L (G) = µ(G) -α(G) < n -1 = ϕ L (C 1 )
.

Proof: If G ∈ G 1 ,
(G) = x(x -1) n-5 f (x), where f (x) = [x 4 -(n + 5)x 3 + (6n + 3)x 2 - (9n -5)x + 3n]. And if n ≥ 5, f ( 3 7 ) = 3 2401 (133n + 1868) > 0, f (1) = -n + 4 < 0, f (2) = n -2 > 0, f (n -1) = -n + 4 < 0, f (n - 4 7 ) = 1 2401 (1029n 3 -7938n 2 + 14924n -2012) > 0, then we have n -1 < µ(G) < n - 4 7 , 3 7 < α(G) < 1. So ϕ L (G) = µ(G) -α(G) < n -1 = ϕ L (C 1 ).
Using the similar method, we can obtain the same result.

If G ∈ G 2 , by Lemma 6 and Lemma 4, we have µ(G) ≤ µ(T 1 (n -3, 1)). Using Lemma 7, it is not difficult to calculate Φ(G) = x(x -2)(x -1) n-4 h(x), where h(x) =

) = -2 343 (7n + 322) < 0, g(1) = n -4 > 0, g(4) = -2(n -4) < 0,

1 Fig. 1 :

 11 Fig. 1:

Lemma 3 (

 3 [START_REF] Grone | The Laplacian spectrum of graph II[END_REF][START_REF] Merris | Laplacian matrices of graphs: a survey[END_REF]) Let G be a connected graph on n vertices with at least one edge, then µ(G) ≥ ∆(G)+ 1, where ∆(G) is the maximum degree of the graph G, with equality if and only if ∆(G) = n -1.Lemma 4 ([8]) Suppose u, v are two distinct vertices of a connected graph H. Let G be the graph obtained from H by attaching s new paths

  If u, v are adjacent, then d(u) + d(v) ≤ n + 1;

[x 3 - 2 - 1 .

 321 (n + 2)x 2 + (3n -2)x -n]. And if n ≥ 5, 244) < 0, h(1) = n -3 > 0, h(n -1) = -1 < 0, h(n -434n + 15) > 0, then we have n -1 < µ(G) < n -So ϕ L (G) = µ(G) -α(G) < n -1 = ϕ L (C 1 ). If G ∈ G 3 , by Lemma 6 and Lemma 4, we have µ(G) ≤ µ(U 4 (n-4, 0, 0, 0)). Using Lemma 7, it is not difficult to calculate Φ(G) = x(x -2)(x -1) n-5 g(x), where g(x) = [x 3 -(n + 3)x 2 + (4n -2)x -2n].And if n ≥ 5, g(

  by Lemma 6 and Lemma 4, we have µ(G) ≤ µ(U 3 (n -4, 1, 0). Using Lemma 7, it is not difficult to calculate Φ

† Research supported by the National Natural Science Foundation of China 10871166. 1365-8050 c 2010 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France

g(n -1) = -2 < 0, g(n -3 7 ) = 2 343 (98n 2 -476n + 39) > 0, then we have

Then there exist r, s (r ≥ s ≥ 1) such that G ∈ G 1 (see Fig. 2). By Lemma 9, we have if n ≥ 5, then µ(G) < n -1.

Then G ∈ {G 2 , G 3 } (see Fig. 2). If G ∈ G 2 for some r, s, by Lemma 9, we have for n ≥ 5, µ(G) < n -1.

If G ∈ G 3 for some r, s, by Lemma 9, we have for n ≥ 5, µ(G) < n -1. 2

From the above lemmas, we give the proof of Theorem 1.

Proof of Theorem 1: From Lemma 5, we know 0 < α(G) ≤ 1.

If there exists u, v ∈ V (G) such that |N (u) ∪ N (v)| = n, then by Lemma 10 we have

The proof is completed. 2


Elcio Lebensztayn

On the asymptotic enumeration of accessible automata

Keywords: asymptotic enumeration, finite automata, Lagrange series, generalized binomial series

We simplify the known formula for the asymptotic estimate of the number of deterministic and accessible automata with n states over a k-letter alphabet. The proof relies on the theory of Lagrange inversion applied in the context of generalized binomial series.

Main result

Let A n be the set of non-isomorphic accessible (also called initially connected) complete and deterministic automata with n states over a k-letter alphabet. By using suitable combinatorial transformations, [START_REF] Bassino | Enumeration and random generation of accessible automata[END_REF] prove that the order of magnitude of the cardinality of A n is related to the Stirling number of the second kind kn n . Then they reformulate the asymptotic estimate of |A n | due to [START_REF] Korshunov | Enumeration of finite automata[END_REF] in terms of this Stirling number. Our purpose is to state a simplification of this formula.

First we need to recall a few definitions. For m, n non-negative integers, the Stirling number of the second kind, denoted by n m , is the number of ways of partitioning a set of n elements into m non-empty subsets. Let W 0 denote the principal branch of the so-called Lambert W function (which is the inverse of the function x → x e x ). See [START_REF] Graham | Concrete mathematics: a foundation for computer science[END_REF] and [START_REF] Corless | On the Lambert W function[END_REF] for more details about these definitions. Also define the constants

v k = 1 + W 0 (-k e -k ) k , ζ k = k v k = k + W 0 (-k e -k ), β k = k k e k-1 (e ζ k -1) ζ k k .
Except for v k , these constants are considered in [START_REF] Bassino | Enumeration and random generation of accessible automata[END_REF]. Notice that v k is the unique root in (0, 1) of the function

φ k (v) = k v + log (1 -v) and it satisfies v k > (k -1)/k. See Figure 1. 0 k-1 k φ max k φ k (v) v v k 1 Fig. 1: Graph of φ k (v) = k v + log (1 -v).
The next result, due to [START_REF] Bassino | Enumeration and random generation of accessible automata[END_REF], reformulates in terms of the Stirling numbers the asymptotic estimate for |A n | previously obtained by [START_REF] Korshunov | Enumeration of finite automata[END_REF].

Theorem 1 (Bassino and Nicaud ( 2007)) The number |A n | of accessible complete and deterministic automata with n states over a k-letter alphabet satisfies

|A n | ∼ E k n 2 n kn n ,
where

E k = 1 + ∞ r=1 1 r kr r-1 (e k-1 β k ) -r 1 + ∞ r=1 kr r (e k-1 β k ) -r .
Our main result presents a simplified formula for E k .

Theorem 2 For any k ≥ 2,

E k = k - (k -1) v k .
Remark 1 We observe that 0 < E k < 1 for all k ≥ 2. Since the principal branch of W is analytic at 0, we have that

lim k→∞ k (v k -1) = lim k→∞ W 0 (-k e -k ) = W 0 (0) = 0. Consequently, lim k→∞ v k = 1 and lim k→∞ E k = lim k→∞ k (v k -1) + 1 v k = 1.

Proof of Theorem 2

The proof relies on the theory of Lagrange series, which constitutes a fundamental tool for the solution of implicit equations and for the reversion of series. We refer to [START_REF] Henrici | Applied and computational complex analysis[END_REF] for an extensive treatment of this subject. To recall the two basic forms of Lagrange series, suppose that the dependence between the variables y and z is implicitly given by the equation

y = z ϕ(z) ,
where ϕ is a regular function in a neighborhood of the point z = 0 and ϕ(0) = 0. If f is a regular function in a neighborhood of z = 0, then

f (z) = f (0) + ∞ r=1 y r r! d r-1 (f (z) [ϕ(z)] r ) dz r-1 z=0 , f (z) 1 -y ϕ (z) = ∞ r=0 y r r! d r (f (z) [ϕ(z)] r ) dz r z=0 , (1)
where the primes denote derivatives.

To prove Theorem 2, we study a classical application of this theory, namely, the solutions of Problems 212 and 216 in Pólya and Szegő (1998, Chapter 5 of Part III). Let a and b be real numbers and consider the equation 1 -x + y x b = 0, that is, y = (x -1) x -b . We define z = x -1 and apply the formulae in (1) with ϕ(z) = (1 + z) b and f (z) = (1 + z) a . Notice that

1 r! d r-1 (f (z) [ϕ(z)]

  Table 1 exhibits the approximate values of v k and E k for k = 2, . . . , 7. Values of v k and E k .

	k	2	3	4	5	6	7
	v k 0.796812 0.940480 0.980173 0.993023 0.997484 0.999082
	E k 0.744999 0.873426 0.939315 0.971895 0.987386 0.994488
			Tab. 1:

Acknowledgements

I would like to thank the referees for their valuable remarks and suggestions.

† Research supported by CNPq (311909/2009-4). 1365-8050

with y = (x -1) x -b . Next, we consider the case b > 1 and investigate the neighborhood in R of the point x = 1 in which (2) and (3) hold.

For a = 1, the power series appearing in (2)

is called the generalized binomial series. Thus, B b is the solution of the functional equation x(y) = 1 + y x(y) b that satisfies x(0) = 1. Moreover, ( 2) and (3) can be rewritten as

In Graham et al. (1994, Sections 5.4 and 7.5), B b is introduced as a formal power series, these properties are proved and used to derive some combinatorial identities. See also [START_REF] Heggie | An integral representation for the generalized binomial function[END_REF] for a representation of the function B b as a contour integral in the complex plane. Now let b > 1 be fixed. We are interested in studying the set of values of x for which the identity B b ((x -1) x -b ) = x holds. To this end, we observe that by the ratio test the series in (4) converges for |y| < R, where

Lemma 1 There exists xb ∈ (1/2, 1) such that

Consequently, identities (2) and ( 3) are valid for every x ∈ (x b , b (b -1) -1 ). Now define vb = (x b ) -1 ∈ (1, 2). From Lemma 1, we obtain the following result.

Lemma 2 For any v ∈ ((b -1)/b, vb ),

. The result follows from (2) and (3).

We are ready to prove our main result.

Proof of Theorem 2: Note that

whereas the denominator simplifies to

.

The result follows. 2