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 of letters from a finite alphabet , and assigning to each such string a probability 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 labelled 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, a 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 denote the set of input symbols. For a given input symbol , write as the adjacency matrix that describes the evolution of the DFA to its next state. The set 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 is N by N-dimensional. The initial state corresponds to a column vector with a one in the q0'th row. A general state q is then a column vector with a one in the qth row. By abuse of notation, let q0 and q also denote these two vectors. Then, after reading input symbols from the input tape, the state of the DFA will be given by The state transitions are given by ordinary matrix multiplication (that is, multiply q0 by , 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 by some general operators. This is essentially what a QFA does: it replaces q by a unit vector, and the 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 that can have more than one entry that is non-zero. Such a vector then represents an element of the power set of Q; it’s just an indicator function on Q. Likewise, the state transition matrices 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 so that the semantics are kept intact.
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 to the regular languages. 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 , and the transition matrices are unitary matrices. Each point in corresponds to a (pure) quantum-mechanical 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 .
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.I. Baianu, "Organismic Supercategories and Qualitative Dynamics of Systems" (1971), Bulletin of Mathematical Biophysics, 33 pp.339-354.I. Baianu, "Categories, Functors and Quantum Automata Theory" (1971). The 4th Intl. Congress of Logic, Methodology and Philosophy of Science, August-Sept.1971
Measure-once automata Measure-once automata were introduced by Cris Moore and James P. Crutchfield.C. Moore, J. Crutchfield, "Quantum automata and quantum grammars", Theoretical Computer Science, 237 (2000) pp 275-306. They may be defined formally as follows.
As with an ordinary finite automaton, the quantum automaton is considered to have possible internal states, represented in this case by an -level qudit . More precisely, the -level qudit is an element of -dimensional complex projective space, carrying an inner product that is the Fubini–Study metric.
The state transitions, transition matrices or de Bruijn graphs are represented by a collection of unitary matrices , with one unitary matrix for each letter . That is, given an input letter , the unitary matrix describes the transition of the automaton from its current state to its next state :
Thus, the triple form a quantum semiautomaton.
The accept state of the automaton is given by an projection matrix , so that, given a -dimensional quantum state , the probability of being in the accept state is
The probability of the state machine accepting a given finite input string is given by
Here, the vector 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 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 on reverses the order of the letters in the string , 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 language over the alphabet is accepted with probability by a quantum finite automaton (and a given, fixed initial state ), if, for all sentences in the language, one has .
Example Consider the classical deterministic finite automaton given by the state transition table + State Transition Table InputState 1 0 S1 S1 S2 S2 S2 S1 State Diagram
The quantum state is a vector, in bra–ket notation
with the complex numbers normalized so that
The unitary transition matrices are
and
Taking to be the accept state, the projection matrix is
As should be readily apparent, if the initial state is the pure state or , 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 and are non-zero. More subtle behaviour occurs when the matrices and 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 is decomposed into three orthogonal subspaces
In the literature, these orthogonal subspaces are usually formulated in terms of the set of orthogonal basis vectors for the Hilbert space . This set of basis vectors is divided up into subsets and , such that
is the linear span of the basis vectors in the accept set. The reject space is defined analogously, and the orthogonal complement of all the accept and reject vectors is designated the non-halting subspace. There are three projection matrices, , and , 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 . After reading an input letter , the automaton will be in the state
At this point, a measurement whose three possible outcomes have eigenspaces , , is performed on the state , at which time its wave-function collapses into one of the three subspaces or or . The probability of collapse to the "accept" subspace is given by
and analogously for the other two spaces.