Study of these quantum languages remains an active area of research.
One begins with a graph-theoretic interpretation of deterministic finite automata (DFA).
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.
); the order of application is 'reversed' only because we follow the standard notation of linear algebra.
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.
Such a vector then represents an element of the power set of Q; it’s just an indicator function on Q.
A well-known theorem states that, for each DFA, there is an equivalent NFA, and vice versa.
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.
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).
A worthy point to contemplate is the distributions that result on the manifold during the input of a language.
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[1] and later by Moore and Crutchfeld,[2] they were described as early as 1971, by Ion Baianu.
, the unitary matrix describes the transition of the automaton from its current state
by a quantum finite automaton (and a given, fixed initial state
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
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
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.
This state is not stable, but suffers from some amount of quantum decoherence over time.
Finally, each unitary transformation is not a single, sharply defined quantum logic gate, but rather a mixture for some probability distribution
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.
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.
The above constructions indicate how the concept of a quantum finite automaton can be generalized to arbitrary topological spaces.
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 set of accept states can be taken to be some arbitrary subset of the topological space.