Quantum finite automaton
In quantum computing, quantum finite automata (QFA) or quantum state machines are a quantum analog of probabilistic automata or a Markov decision process. They provide a mathematical abstraction of real-world quantum computers. Several types of automata may be defined, including "measure-once" and "measure-many" automata. Quantum finite automata can also be understood as the quantization of subshifts of finite type, or as a quantization of Markov chains. QFAs are, in turn, special cases of geometric finite automata or topological finite automata. The automata work by receiving a finite-length string formula_1 of letters formula_2 from  a finite alphabet formula_3, and assigning to each such string a probability formula_4 indicating the probability of the automaton being in an accept state; that is, indicating whether the automaton accepted or rejected the string. The languages accepted by QFAs are not the regular languages of deterministic finite automata, nor are they the stochastic languages of probabilistic finite automata. Study of these quantum languages remains an active area of research. Informal description. There is a simple, intuitive way of understanding quantum finite automata. One begins with a graph-theoretic interpretation of deterministic finite automata (DFA). A DFA can be represented  as a directed graph, with states as nodes in the graph, and arrows representing state transitions. Each arrow is labelled with a possible input symbol, so that, given a specific state and an input symbol, the arrow points at the next state. One way of representing such a graph is by means of a set of adjacency matrices, with one matrix for each input symbol. In this case, the list of possible DFA states is written as a column vector. For a given input symbol, the adjacency matrix indicates how any given state (row in the state vector) will transition  to the next state; a state transition is given by matrix multiplication. One needs a distinct adjacency matrix for each possible input symbol, since each input symbol can result in a different transition. The entries in the adjacency matrix must be zero's and one's. For any given column in the matrix, only one entry can be non-zero: this is the entry that indicates the next (unique) state transition. Similarly, the state of the system is a column vector, in which only one entry is non-zero: this entry corresponds to the current state of the system. Let  formula_3 denote the set of input symbols. For a given input symbol formula_6, write formula_7 as the adjacency matrix that describes the evolution of the DFA to its next state. The set formula_8 then completely describes the state transition function of the DFA. Let "Q" represent the set of possible states of the DFA. If there are "N" states in "Q", then each matrix formula_7 is "N" by "N"-dimensional. The initial state formula_10 corresponds to a column vector with a one in the "q"'th row. A general state "q" is then a column vector with a one in the "q"'th  row. By abuse of notation, let "q" and "q" also denote these two vectors. Then, after reading input symbols formula_11 from the input tape, the state of the DFA will be given by formula_12 The state transitions are given by ordinary matrix multiplication (that is, multiply "q" by formula_7, "etc."); the order of application is 'reversed' only because we follow the standard notation of linear algebra. The above description of a DFA, in terms of linear operators and vectors, almost begs for generalization, by replacing the state-vector "q" by some general vector, and the matrices formula_14 by some general  operators. This is essentially what a QFA does: it replaces "q" by a probability amplitude, and the formula_14 by unitary matrices. Other, similar generalizations also become obvious: the vector "q" can be some distribution on a manifold; the set of transition matrices become automorphisms of the manifold; this defines a topological finite automaton. Similarly, the matrices could be taken as automorphisms of a homogeneous space; this defines a geometric finite automaton. Before moving on to the formal description of a QFA, there are two noteworthy generalizations that should be mentioned and understood. The first is the non-deterministic finite automaton  (NFA). In this case, the vector "q" is replaced by a vector which can have more than one entry that is non-zero. Such a vector then represents an element of the power set of "Q"; its just an indicator function on "Q". Likewise, the state transition matrices formula_14 are defined in such a way that a given column can have several non-zero entries in it. Equivalently, the multiply-add operations performed during component-wise matrix multiplication should be replaced by Boolean and-or operations, that is, so that one is working with a ring of characteristic 2. A  well-known theorem states that, for each DFA, there is an equivalent NFA, and vice versa. This implies that the set of languages that can be recognized by DFA's and NFA's are the same; these are the regular languages. In the generalization to QFAs, the set of recognized languages will be different. Describing that set is one of the outstanding research problems in QFA theory. Another generalization that should be immediately apparent is to use a stochastic matrix for the transition matrices, and a probability vector for the state; this gives a probabilistic finite automaton. The entries in  the state vector must be real numbers, positive, and sum to one, in order for the state vector to be interpreted as a probability. The transition matrices must preserve this property: this is why they must be stochastic. Each state vector should be imagined as specifying a point in a simplex; thus, this is a topological automaton, with the simplex being the manifold, and the stochastic matrices being linear automorphisms of the simplex onto itself. Since each transition is (essentially) independent of the previous (if we disregard the distinction between accepted and rejected languages), the PFA essentially becomes a kind  of Markov chain. By contrast, in a QFA, the manifold is complex projective space formula_17, and the transition matrices are unitary matrices. Each point in formula_17 corresponds to a quantum-mechanical probability amplitude or pure state; the unitary matrices can be thought of as governing the time evolution of the system (viz in the Schrödinger picture). The generalization from pure states to mixed states should be straightforward: A mixed state is simply a measure-theoretic probability distribution on formula_17. A worthy point to contemplate is the distributions that result on the manifold during the input of a language. In order  for an automaton to be 'efficient' in recognizing a language, that distribution should be 'as uniform as possible'. This need for uniformity is the underlying principle behind maximum entropy methods: these simply guarantee crisp, compact operation of the automaton. Put in other words, the machine learning methods used to train hidden Markov models generalize to QFAs as well: the Viterbi algorithm and the forward-backward algorithm generalize readily to the QFA. Although the study of QFA was popularized in the work of Kondacs and Watrous in 1997 and later by Moore and Crutchfeld, they were described as early as 1971 , by Ion Baianu. Measure-once automata. Measure-once automata were introduced by Cris Moore and James P. Crutchfield. They may be defined formally as follows. As with an ordinary finite automaton, the quantum automaton is considered to have formula_20 possible internal states, represented in this case by an formula_20-state qubit formula_22. More precisely, the formula_20-state qubit formula_24 is an element of formula_20-dimensional complex projective space, carrying an inner product formula_26 that is the Fubini–Study metric. The state transitions, transition matrices or de Bruijn graphs are represented by a collection of formula_27 unitary matrices formula_7, with one  unitary matrix for each letter formula_6. That is, given an input letter formula_30, the unitary matrix describes the transition of the automaton from its current state formula_22 to its next state formula_32: Thus, the triple formula_34 form a quantum semiautomaton. The accept state of the automaton is given by an formula_27 projection matrix formula_36, so that, given a formula_20-dimensional quantum state formula_22, the probability of formula_22 being in the accept state is The probability of the state machine accepting a given finite input string formula_1 is given by Here, the vector formula_22 is understood to represent the initial state  of the automaton, that is, the state the automaton was in before it started accepting the string input. The empty string formula_44 is understood to be just the unit matrix, so that is just the probability of the initial state being an accepted state. Because the left-action of formula_7 on formula_22 reverses the order of the letters in the string formula_48, it is not uncommon for QFAs to be defined using a right action on the Hermitian transpose states, simply in order to keep the order of the letters the same. A regular language is accepted with probability formula_49  by a quantum finite automaton, if, for all sentences formula_48 in the language, (and a given, fixed initial state formula_22), one has formula_52. Example. Consider the classical deterministic finite automaton given by the state transition table The quantum state is a vector, in bra–ket notation with the complex numbers formula_54 normalized so that The unitary transition matrices are and Taking formula_58 to be the accept state, the projection matrix is As should be readily apparent, if the initial state is the pure state formula_60 or formula_61, then the result of running the machine will be exactly identical to the  classical deterministic finite state machine. In particular, there is a language accepted by this automaton with probability one, for these initial states, and it is identical to the regular language for the classical DFA, and is given by the regular expression: The non-classical behaviour occurs if both formula_63 and formula_64 are non-zero. More subtle behaviour occurs when the matrices formula_65 and formula_66 are not so simple; see, for example, the de Rham curve as an example of a quantum finite state machine acting on the set of all possible finite binary strings. Measure-many automata. Measure-many automata  were introduced by Kondacs and Watrous in 1997. The general framework resembles that of the measure-once automaton, except that instead of there being one projection, at the end, there is a projection, or quantum measurement, performed after each letter is read. A formal definition follows. The Hilbert space formula_67 is decomposed into three orthogonal subspaces In the literature, these orthogonal subspaces are usually formulated in terms of the set formula_69 of orthogonal basis vectors for the Hilbert space formula_67. This set of basis vectors is divided up into subsets formula_71 and formula_72, such that is the linear span of  the basis vectors in the accept set. The reject space is defined analogously, and the remaining space is designated the "non-halting" subspace. There are three projection matrices, formula_74, formula_75 and formula_76, each projecting to the respective subspace: and so on. The parsing of the input string proceeds as follows. Consider the automaton to be in a state formula_22. After reading an input letter formula_30, the automaton will be in the state At this point, a measurement is performed on the state formula_32, using the projection operators formula_36, at which time its wave-function collapses into one of the three  subspaces formula_83 or formula_84 or formula_85. The probability of collapse is given by for the "accept" subspace, and analogously for the other two spaces. If the wave function has collapsed to either the "accept" or "reject" subspaces, then further processing halts. Otherwise, processing continues, with the next letter read from the input, and applied to what must be an eigenstate of formula_76. Processing continues until the whole string is read, or the machine halts. Often, additional symbols formula_88 and $ are adjoined to the alphabet, to act as the left and right end-markers for the string. In the literature , the measure-many automaton is often denoted by the tuple formula_89. Here, formula_69, formula_3, formula_92 and formula_93 are as defined above. The initial state is denoted by formula_94. The unitary transformations are denoted by the map formula_95, so that Relation to quantum computing. As of 2019, most quantum computers are implementations of measure-once quantum finite automata, and the software systems for programming them expose the state-preparation of formula_22, measurement formula_36 and a choice of unitary transformations formula_7, such the controlled NOT gate, the Hadamard transform and other quantum logic gates, directly to the programmer. The primary difference between  real-world quantum computers and the theoretical framework presented above is that the initial state preparation cannot ever result in a point-like pure state, nor can the unitary operators be precisely applied. Thus, the initial state must be taken as a mixed state for some probability distribution formula_102 characterizing the ability of the machinery to prepare an initial state close to the desired initial pure state formula_22. This state is not stable, but suffers from some amount of quantum decoherence over time. Precise measurements are also not possible, and one instead uses positive operator-valued measures to describe  the measurement process. Finally, each unitary transformation is not a single, sharply defined quantum logic gate, but rather a mixture for some probability distribution formula_105 describing how well the machinery can effect the desired transformation formula_7. As a result of these effects, the actual time evolution of the state cannot be taken as an infinite-precision pure point, operated on by a sequence of arbitrarily sharp transformations, but rather as an ergodic process, or more accurately, a mixing process that only concatenates transformations onto a state, but also smears the state over time. There is no quantum analog to  the push-down automaton or stack machine. This is due to the no-cloning theorem: there is no way to make a copy of the current state of the machine, push it onto a stack for later reference, and then return to it. Geometric generalizations. The above constructions indicate how the concept of a quantum finite automaton can be generalized to arbitrary topological spaces. For example, one may take some ("N"-dimensional) Riemann symmetric space to take the place of formula_17. In place of the unitary matrices, one uses the isometries of the Riemannian manifold, or, more generally, some set of  open functions appropriate for the given topological space. The initial state may be taken to be a point in the space. The set of accept states can be taken to be some arbitrary subset of the topological space. One then says that a formal language is accepted by this topological automaton if the point, after iteration by the homeomorphisms, intersects the accept set. But, of course, this is nothing more than the standard definition of an M-automaton. The behaviour of topological automata is studied in the field of topological dynamics. The quantum automaton differs from the topological automaton in  that, instead of having a binary result (is the iterated point in, or not in, the final set?), one has a probability. The quantum probability is the (square of) the initial state projected onto some final state "P"; that is formula_108. But this probability amplitude is just a very simple function of the distance between the point formula_109 and the point formula_110 in formula_17, under the distance metric given by the Fubini–Study metric. To recap, the quantum probability of a language being accepted can be interpreted as a metric, with the probability of accept being unity, if the metric  distance between the initial and final states is zero, and otherwise the probability of accept is less than one, if the metric distance is non-zero. Thus, it follows that the quantum finite automaton is just a special case of a geometric automaton or a metric automaton, where formula_17 is generalized to some metric space, and the probability measure is replaced by a simple function of the metric on that space.