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.
\sigma=(\sigma0,\sigma1, … ,\sigmak)
\sigmai
\Sigma
\operatorname{Pr}(\sigma)
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.
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
\Sigma
\alpha\in\Sigma
U\alpha
\{U\alpha|\alpha\in\Sigma\}
U\alpha
q0\inQ
\alpha\beta\gamma …
q= … U\gammaU\betaU\alphaq0.
U\alpha
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
\{U\alpha\}
\{U\alpha\}
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
\{U\alpha\}
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.
CPN
CPN
CPN
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.[1] [2]
Measure-once automata were introduced by Cris Moore and James P. Crutchfield.[3] They may be defined formally as follows.
As with an ordinary finite automaton, the quantum automaton is considered to have
N
N
|\psi\rangle
N
|\psi\rangle\inP(CN)
(N-1)
\Vert ⋅ \Vert
The state transitions, transition matrices or de Bruijn graphs are represented by a collection of
N x N
U\alpha
\alpha\in\Sigma
\alpha
|\psi\rangle
|\psi\prime\rangle
|\psi\prime\rangle=U\alpha|\psi\rangle
Thus, the triple
N),\Sigma,\{U | |
(P(C | |
\alpha \vert \alpha\in\Sigma\}) |
The accept state of the automaton is given by an
N x N
P
N
|\psi\rangle
|\psi\rangle
\langle\psi|P|\psi\rangle=\VertP|\psi\rangle\Vert2
The probability of the state machine accepting a given finite input string
\sigma=(\sigma0,\sigma1, … ,\sigmak)
\operatorname{Pr}(\sigma)=\VertP
U | |
\sigmak |
…
U | |
\sigma1 |
U | |
\sigma0 |
|\psi\rangle\Vert2
Here, the vector
|\psi\rangle
\varnothing
\operatorname{Pr}(\varnothing)=\VertP|\psi\rangle\Vert2
is just the probability of the initial state being an accepted state.
Because the left-action of
U\alpha
|\psi\rangle
\sigma
A language over the alphabet
\Sigma
p
|\psi\rangle
\sigma
p\leq\operatorname{Pr}(\sigma)
Consider the classical deterministic finite automaton given by the state transition table
| State Diagram |
The quantum state is a vector, in bra–ket notation
|\psi\rangle=a1|S1\rangle+a2|S2\rangle=\begin{bmatrix}a1\ a2\end{bmatrix}
with the complex numbers
a1,a2
\begin{bmatrix}
* | |
a | |
1 |
* | |
a | |
2 |
\end{bmatrix}\begin{bmatrix}a1\ a2\end{bmatrix}=
*a | |
a | |
1 |
+
*a | |
a | |
2 |
=1
The unitary transition matrices are
U0=\begin{bmatrix}0&1\ 1&0\end{bmatrix}
and
U1=\begin{bmatrix}1&0\ 0&1\end{bmatrix}
Taking
S1
P=\begin{bmatrix}1&0\ 0&0\end{bmatrix}
As should be readily apparent, if the initial state is the pure state
|S1\rangle
|S2\rangle
(1*(01*0)*)*
The non-classical behaviour occurs if both
a1
a2
U0
U1
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.
l{H}Q
l{H}Q=l{H}accept ⊕ l{H}reject ⊕ l{H}non-halting
In the literature, these orthogonal subspaces are usually formulated in terms of the set
Q
l{H}Q
Qacc\subseteqQ
Qrej\subseteqQ
l{H}accept=\operatorname{span}\{|q\rangle:|q\rangle\inQacc\}
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,
Pacc
Prej
Pnon
Pacc:l{H}Q\tol{H}accept
and so on. The parsing of the input string proceeds as follows. Consider the automaton to be in a state
|\psi\rangle
\alpha
|\psi\prime\rangle=U\alpha|\psi\rangle
At this point, a measurement whose three possible outcomes have eigenspaces
l{H}accept
l{H}reject
l{H}non-halting
|\psi\prime\rangle
l{H}accept
l{H}reject
l{H}non-halting
\operatorname{Pr}acc(\sigma)=\VertPacc|\psi\prime\rangle\Vert2,
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
Pnon
\kappa
In the literature, the measure-many automaton is often denoted by the tuple
(Q;\Sigma;\delta;q0;Qacc;Qrej)
Q
\Sigma
Qacc
Qrej
|q0\rangle
\delta
\delta:Q x \Sigma x Q\toC
so that
U\alpha|qi\rangle=
\sum | |
qj\inQ |
\delta(qi,\alpha,qj)|qj\rangle
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
|\psi\rangle
P
U\alpha
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
\rho=\intp(x)|\psix\rangledx
p(x)
|\psi\rangle
U\alpha,=\intp\alpha(x)U\alpha,xdx
p\alpha(x)
U\alpha
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.
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
CPN
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
Pr=\vert\langleP\vert\psi\rangle\vert2
\vertP\rangle
\vert\psi\rangle
CPN
CPN