# Quantum Conditional Strategies and Automata for Prisoners' Dilemmata under the EWL Scheme
## 4 Quantum Automata  
Two models of quantum finite automata were initially proposed in [17; 18]. The former model is known as measure-once quantum automata (meaning that a single measurement operator is applied at the end of the computation with respect to the orthonormal kets representing the automaton's accepting states), whereas the latter is known as measure-many quantum automata (since a measurement is applied after each read symbol). A comprehensive overview of these models, along with further insights and examples, is provided in [16]. Here, we follow the measure-once paradigm. In this section, we give the definition of \(\mu\)-periodic quantum automata, which are inspired from the periodic quantum \(\omega\)-automata introduced in [19]. The present definition is appropriate for the case of finite inputs. We mention in passing that despite their simplicity and their inherent limitations, periodic quantum \(\omega\)-automata are capable of recognizing particular languages with a probability of 1. Specifically, they recognize with a probability of 1 languages of the form \((a^{m}b)^{\omega}\). That is, they recognize a language with a probability cut-point \(\lambda=1\). This class of languages was described in [19; 21]. For the purposes of this work, a cut-point other than \(\lambda=1\) (e.g., \(\lambda=c\) with \(0<c<1\) or \(\lambda>0\), which are usually discussed) would not be necessary since the game strategies can be associated to the aforementioned automata model. Measurement is performed infinitely often after the reading of \(\mu\) input symbols (hence the term periodic) with respect to the orthonormal basis of the automaton's states. Note that the cut-point restriction being equal to 1 could be lifted or modified, but it would not contribute anything to the purposes of this work (it would be of interest, though, in case someone is interested in probabilistic acceptance). For a deeper introduction to classical automata and computation theory, the reader is referred to [69]. If we lift the infinite character of the inputs in the previous description, then we have the \(\mu\)-periodic quantum automata, where a single measurement is applied after reading \(\mu\) letters. We keep the notion of periodicity in order to avoid any confusion with the standard measure-once quantum automata of [17]. Periodicity is also somehow \"embedded\" in the functionality of the periodic quantum automata due to the periodic-like evolution of the operators. The set \(P\) of projection matrices is the same for every automaton used later in this paper. **Definition 2**. : _A simple \(\mu\)-periodic 1-way quantum automaton is a tuple \((Q,\Sigma,U_{\alpha\in\Sigma},q_{0},\mu,F,P_{q\in Q})\), where \(Q\) is the finite set of states, \(\Sigma\) is the input alphabet, for each symbol \(\alpha\in\Sigma\), \(U_{\alpha}\) is the \(n\times n\) unitary matrix that describes the corresponding transitions among the states, \(q_{0}\in Q\) is the initial state, \(\mu\) is a positive integer that defines the measurement period, \(F\subseteq Q\) is the set of final states, and for each \(q\in Q\), \(P_{q}\) is the projector to the state \(q\)._  
Periodic quantum automata accept words of the form \(a^{m}b,ba^{m}\), etc., with a probability cut-point \(\lambda=1\) (like the infinite case). Again, measurement is performed after the reading of \(\mu\) symbols (hence the term periodic) with respect to the orthonormal basis of the states (but this time only once, unlike the infinite case). Similarly to the definition of the infinite variant, the set \(P\) of projection matrices is the same for every automaton used later in this paper, thus it is omitted from now on. Note that the value of the period \(\mu\) has to be a positive integer in order for the computation to have a physical meaning (we cannot perform a measurement after reading 2.1 symbols!).