key: cord-0045919-ugits3n4 authors: Lippa, Gustaw; Makieła, Krzysztof; Kuta, Marcin title: Simulations of Quantum Finite Automata date: 2020-05-25 journal: Computational Science - ICCS 2020 DOI: 10.1007/978-3-030-50433-5_34 sha: e60e2ed7a2df83b49d0f02752b1fa5f7b18ef2bc doc_id: 45919 cord_uid: ugits3n4 This paper presents a Python library to simulate different kinds of quantum finite automata on a classical computer. The library also provides tools for language generation and visual representation of simulation results. We have conducted experiments to measure the time complexity of the simulation in a function of the automaton size, alphabet size and word length. Examples of library usage are also provided. Finite automata are real models of computers, which have only limited amount of memory. Finite automata are also interesting models themselves, due to their simplicity but at the same time rich structure and interesting properties [7] . Since the introduction of finite automata in 1959 by Rabin and Scott [13] , the theme has been quite well recognized and approached from various aspects. Connections with different domains, including algebra and logics, have also been established. The picture for theory of quantum automata and languages generated by them is less clear, and various important problems remain open [2, 11] . The task of quantum finite automata is to recognise quantum languages. Studying these languages is useful in establishing the computational and expressive power of quantum machines in general. However, such devices are not yet available and simulators have to be used instead. Because of that, we developed a library written in Python, running on a classical computer and providing implementation of several types of quantum finite automata. This paper presents the library for simulating quantum finite automata. The library can help in exploring hypotheses on unknown relations between classes of quantum finite automata and quantum languages by providing evidence about accepting probabilities of particular words and sets of words. The library could also be useful for teaching students courses on finite automata in a quantum context. Simulation of classical finite automata is a mature area. A comprehensive survey of simulators of classical finite automata is given in [5] and JFLAP emerges as the most mature and popular tool [14] . On the other hand, there have been many libraries focused on bringing quantum computation onto the classical architectures, perhaps the best known being Q# 1 . The low-level libraries include Quirk 2 , with graphical interface available through a web browser, or Quantum++ 3 , a high performance library written in C++11. The high-level libraries provide similar functionalities but focus more on code expressiveness. They often enable using real life simulators or quantum computers as their back-ends. Examples of such libraries include ProjectQ 4 , Qiskit 5 and the aforementioned Q#. However, we have not found a solution focused solely on quantum finite automata. The available pieces of software were either too low-level, focusing on quantum gates and quantum phenomena in micro-scale, or too abstract, providing interfaces for developing quantum algorithms in general, but without tools dedicated specifically for quantum automata. In this work we consider only one-way finite automata, i.e., in each step of a simulation the head reads one symbol from the tape and moves forward. Backward or empty moves of the head are forbidden. The paper defines all automata in a uniform framework, which means that for classical finite automata notation differs slightly from the one adopted widely in literature. Preliminaries. An input alphabet Σ is a finite set of symbols. The working alphabet Γ equals Σ ∪{$}, where $ denotes a special end-marker symbol outside the input alphabet. Set Q is a finite set of states and q I ∈ Q is a distinguished state, called the initial state. Each classical state q ∈ Q has a quantum counterpart |q . A pure quantum state |ψ of quantum automaton is defined as where α 1 , . . . , α n ∈ C and n i=1 |α i | 2 = 1. Vector 1 denotes column vector consisting of |Q| ones. Matrix I |Q| denotes square |Q| × |Q| matrix containing ones on a diagonal and zeros elsewhere. Definition 1. Nondeterministic Finite Automaton (NFA) [13] is a 5-tuple A = (Σ, Q, q I , Q acc , {M σ } σ∈Σ ), where Q acc ⊆ Q is a set of accepting states, and for all σ ∈ Σ transition matrix M σ satisfies M σ ∈ {0, 1} |Q|×|Q| . If transition matrices M σ additionally satisfy for all σ ∈ Σ condition then an automaton is Deterministic Finite Automaton (DFA). Classes of NFAs and DFAs are equivalent as they recognize the same class of languages, i.e., class of regular languages. where vector I is a stochastic column vector describing initial distribution of states, i.e., I ∈ [0, 1] |Q|×1 and Vector F is a column vector of size |Q| with i-th entry equal 1 if q i is a accepting state and 0 otherwise. For all σ ∈ Σ transition matrix M σ is Markovian, i.e., its rows define probability distribution. Thus, for all σ ∈ Σ we have M σ ∈ [0, 1] |Q|×|Q| and M σ satisfies (2) . The set of accepting states corresponds to a projective operator: where Q rej ⊆ Q is a set of rejecting states, and U σ ∈ C |Q|×|Q| are transition matrices satisfying (3). where Q non is a set of nonhalting (neutral) states. Sets Q acc , Q rej and Q non should be pairwise disjoint. In a manner analogous to (4), projective operators P rej and P non are defined as follows: Definition 5. General Quantum Finite Automaton (GQFA) [10] is a 6-tuple A = (Q, Σ, q I , Q acc , Q rej , {U σ } σ∈Γ ). The model is similar to MM-QFA, but the transition matrices U σ are more general -they are a composition of a finite sequence of applications of unitary transformations followed by orthogonal measurements. Note, that there is a more general definition of GQFA, provided by Hirvensalo [6] , but it is not considered in our work. For a broader description of these and other types of quantum automata we refer a reader to [3, 7, 11] . Let P A (x) denote probability of accepting word x ∈ Σ * by automaton A and let λ be a real number such that λ ∈ [0, 1). Given x = σ 1 . . . σ n , probability P A (x) is computed as P acc U σn . . . U σ1 |q 0 2 for MO-QFA, but for MM-QFA is more complicated. There exist several modes of language acceptance: • with a cut-point λ ∈ [0, 1), if for all x ∈ L, we have P A (x) > λ and for all x / ∈ L, we have P A (x) ≤ λ. This mode of acceptance is also called with an unbounded error. • with an isolated cut-point λ ∈ [0, 1), if there exists ε ≥ 0, such, that for all This mode of acceptance is equivalent to acceptance with an isolated cut-point, where cut-point λ = 1 2 is isolated with value 1 2 − ε. • with a positive one-sided unbounded error if for all x ∈ L, we have P A (x) > 0. • with a negative one-sided unbounded error if for all x ∈ L, we have P A (x) = 1. • Monte Carlo acceptance [4] , if there exists ε ∈ (0, 1 2 ] such, that for all x ∈ L, we have P A (x) = 1 and for all x / ∈ L, we have P A (x) ≤ ε. Such A is called Monte Carlo QFA for L. Acceptance with a cut-point and acceptance with an isolated cut-point are the most import modes of language acceptance, and are implemented in our library. The simulation library 6 provides its interface through a number of classes, each representing one of the automata models. It also uses modules LanguageGenerator, LanguageChecker and Plotter. Figure 1 presents main components of the simulation library, which offers the following functionality. A new automaton is constructed with an object belonging to a class representing implemented automaton (one of PFA, MO 1QFA, MM 1QFA, GQFA) and data defining chosen automaton, such as the alphabet, transition matrices and matrices of projective measurements are passed. A user has to assure unitarity of transition matrices. Automaton Simulation. The LanguageChecker module of the library enables simulation of an automaton run on a single word or on a random or user-defined sample of defined language. A simulation is determined by a transition matrix and one simulation of the automaton on a given word is sufficient to obtain all information about word acceptance or rejection. Thus, there is no need to repeat a simulation since transition matrices are stationary. Simulation results are returned with respect to two modes of language acceptance: with a cut-point and with an isolated cut-point. Results Visualisation. The library has a dedicated Plotter module to plot histograms of counts of words accepted and words rejected with a given probability. A cut-point and an isolation interval can also be shown. There exist two ways of simulating systems of a probabilistic nature. One way is the strong simulation, which requires calculating the exact probability of an outcome. The other way is the weak simulation, which is based on a sampling from the output distribution in order to approximate the probability. The latter is the only tractable way of simulating quantum computers because of the complexity of the task. However, our library performs a strong simulation, which is adequate because of the simpler nature of quantum automata. We have performed a handful of experiments to determine the time complexity of the simulations depending on various parameters. Automaton size. During our research we concluded that the most important factor in the time complexity of a simulation is the number of automaton states. In a true QFA, the relation between the number of states and computation time would be linear. In our simulator the time complexity is polynomial which agrees with the result proven in [3] . Figure 2 shows simulation time of GQFA with the growing number of its states. The results are quite close to the values predicted theoretically. Simulation time is reported as the arithmetic mean from 5 simulations for each automaton size. Figure 3 presents simulation time of GQFA as a function of the size of alphabet, over which automaton is defined. For each alphabet size, simulation time was measured as the arithmetic mean over 500 random words. It should be noted that the scale in ordinate axis (y-axis) does not start from 0. Figure 3 shows that there is no dependence between the size of the alphabet and the time of simulation. This is because the change of the alphabet size influences only the amount of input data (transition matrices and projective measurement matrices) required to define an automaton but does not impact computation time at all. For each letter a transition function must be applied and a measurement may be performed, depending on the type of an automaton. Figure 4 shows simulation time of GQFA as a function of the length of simulated words. For each word length, 100 random words were simulated and simulation time was taken as the arithmetic mean over these 100 words. Listing 1.1 presents exemplary code for defining a MM-QFA automaton. This automaton is well-known in literature and was proposed by Ambainis and Freivalds [1] as a part of the proof that there exists a one-way QFA, which recognizes language a * b * with probability p = 0.68.., where p is the real root of the equation p 3 + p = 1. Figure 5 visualizes obtained acceptance probabilities and their corresponding word counts. The library provides a simple API for functionality required to simulate quantum finite automata. We hope the library will encourage research at the intersection of quantum computations and theory of formal languages and automata. We have experimentally shown that the time complexity of simulating a quantum finite automaton is polynomial in relation to the size of the automaton. Nevertheless, we believe that the library may be useful for researchers, lecturers and students as a tool to prove or disprove certain properties of quantum automata and languages in a reasonable time. We have successfully used our library and thus shown that it returns expected results for examples taken from literature. The scope of the project can be broadened in several directions, e.g. by adding new types of automata. 1-way quantum finite automata: strengths, weaknesses and generalizations On the class of languages recognizableby 1-way quantum finite automata Automata and quantum computing Quantum finite automata: advances on bertoni's ideas. Theor Fifty years of automata simulation: a review Quantum automata with open time evolution Quantum automata theory -a review On the power of quantum finite state automata Quantum automata and quantum grammars Optimal lower bounds for quantum automata and random access codes Quantum finite automata Probabilistic automata Finite automata and their decision problems JFLAP: An Interactive Formal Languages and Automata Package Acknowledgments. The research presented in this paper was supported by the funds assigned to AGH University of Science and Technology by the Polish Ministry of Science and Higher Education.