# An Enhanced Photonic Quantum Finite Automaton
## 2 Formal Languages, Finite Automata, and Quantum Computing  
In this section, we would like to expand on motivations that have been driving our research covered by the present contribution and the previous one in [6]. The aim of our work, that bridges between Theoretical Computer Science and Experimental Quantum Optics, has been and is to show that a quantum computing device with finite memory is physically realizable by means of photonics, using a very limited amount of \"quantum hardware\". To the best of our knowledge, our physical implementation, described here and in [6], of a quantum finite automaton for language acceptation is the first proposed in the literature. Thus, we have shown how the quantum behaviour of microscopic systems can actually represent a computational resource, as theoretically established within the discipline of Quantum Computing. From this perspective, the simple language \(L_{m}\), introduced in the next section and for which we build our photonic quantum finite automaton, is not really the point here. Instead, the point is the concrete creation of a programmable fully quantum computer with finite memory. With this being said, we would also like to quickly comment on the language \(L_{m}\) from a Theoretical Computer Science viewpoint. Notwithstanding its simplicity, the language \(L_{m}\) plays a crucial role in Descriptional Complexity Theory (see, e.g., in [17; 18; 19; 20; 21]), the area of Formal Language Theory in which the _size_ of computational models is investigated. In particular, a well-consolidated trend in Descriptional Complexity is devoted to study the size of several types of _finite automata_. The reader is referred to, e.g., the work in [22] for extensive presentations of automata theory. Very roughly speaking, the hardware of a (one-way) finite automaton \(A\) features a read-only input tape consisting of a sequence of cells, each one being able to store an input symbol. The tape is scanned by an input head always moving one position right at each step. At each time during the computation of \(A\), a finite state control is in a state from a _finite_ set \(Q\). Some of the states in \(Q\) are designated as accepting states, while a state \(q_{0}\in Q\) is a designated initial state. The computation of \(A\) on a word (i.e., a finite sequence of symbols) \(\omega\) from a given input alphabet begins by having (i) \(\omega\) stored symbol by symbol, left to right, in the cells of the input tape; (ii) the input head scanning the leftmost tape cell; and (iii) the finite state control being in the state \(q_{0}\). In a move, \(A\) reads the symbol below the input head and, depending on such a symbol and the state of the finite state control, it switches to the next state according to a fixed transition function and moves the input head one position forward. We say that \(A\) accepts \(\omega\) whenever it enters an accepting state after scanning the rightmost symbol of \(\omega\); otherwise, \(A\) rejects \(\omega\). The language accepted by \(A\) consists of all the input words accepted by \(A\). The one described so far is the original model of a finite automaton, called _deterministic_. Several variants of such an original model have been introduced and studied in the literature, sharing the same hardware but different dynamics. Therefore, we have _nondeterministic_, _probabilistic_ and, recently, _quantum_ finite automata (see, e.g., in [23; 24; 25]). Furthermore, _two-way_ automata are studied, where the input head can move back and forth on the input tape. Finite automata represent a formidable theoretical model used in the design and analysis of several devices such as the control units for vending machines, elevators, traffic lights, combination locks, etc. Particularly important is the use of finite automata in very large-scale integration (VLSI) design, namely, in the project of sequential networks which are the building blocks of modern computers and digital systems. Very roughly speaking, a sequential network is a boolean circuit equipped with memory.