Inquantum computing,quantum finite automata (QFA) orquantum state machines are a quantum analog ofprobabilistic automata or aMarkov decision process. They provide a mathematical abstraction of real-worldquantum computers. Several types of automata may be defined, includingmeasure-once andmeasure-many automata. Quantum finite automata can also be understood as the quantization ofsubshifts of finite type, or as a quantization ofMarkov chains. QFAs are, in turn, special cases ofgeometric finite automata ortopological finite automata.

The automata work by receiving a finite-lengthstring${\displaystyle \sigma =({\sigma }_0,{\sigma }_1,\cdots ,{\sigma }_k)}$ of letters${\displaystyle {\sigma }_i}$ from a finitealphabet${\displaystyle \mathrm{\Sigma }}$, and assigning to each such string aprobability${\displaystyle \mathrm{Pr}(\sigma )}$ indicating the probability of the automaton being in anaccept state; that is, indicating whether the automaton accepted or rejected the string.

Thelanguages accepted by QFAs are not theregular languages ofdeterministic finite automata, nor are they thestochastic languages ofprobabilistic finite automata. Study of thesequantum languages remains an active area of research.

There is a simple, intuitive way of understanding quantum finite automata. One begins with agraph-theoretic interpretation ofdeterministic finite automata (DFA). A DFA can be represented as adirected 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 ofadjacency matrices, with one matrix for each input symbol. In this case, the list of possible DFA states is written as acolumn 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 bymatrix 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${\displaystyle \mathrm{\Sigma }}$ denote the set of input symbols. For a given input symbol${\displaystyle \alpha \in \mathrm{\Sigma }}$, write${\displaystyle U_{\alpha }}$ as the adjacency matrix that describes the evolution of the DFA to its next state. The set${\displaystyle \{U_{\alpha }|\alpha \in \mathrm{\Sigma }\}}$ then completely describes the state transition function of the DFA. LetQ represent the set of possible states of the DFA. If there areN states inQ, then each matrix${\displaystyle U_{\alpha }}$ isN byN-dimensional. The initial state${\displaystyle q_0\in Q}$ corresponds to a column vector with a one in theq₀'th row. A general stateq is then a column vector with a one in theq'th row. Byabuse of notation, letq₀ andq also denote these two vectors. Then, after reading input symbols${\displaystyle \alpha \beta \gamma \cdots }$ from the input tape, the state of the DFA will be given by${\displaystyle q=\cdots U_{\gamma }{U}_{\beta }{U}_{\alpha }{q}_0.}$ The state transitions are given by ordinarymatrix multiplication (that is, multiplyq₀ by${\displaystyle U_{\alpha }}$,etc.); the order of application is 'reversed' only because we follow the standard notation oflinear algebra.

The above description of a DFA, in terms oflinear operators and vectors, almost begs for generalization, by replacing the state-vectorq by some general vector, and the matrices${\displaystyle \{U_{\alpha }\}}$ by some general operators. This is essentially what a QFA does: it replacesq by aunit vector, and the${\displaystyle \{U_{\alpha }\}}$ byunitary matrices. Other, similar generalizations also become obvious: the vectorq can be somedistribution on amanifold; the set of transition matrices becomeautomorphisms of the manifold; this defines a topological finite automaton. Similarly, the matrices could be taken as automorphisms of ahomogeneous 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 thenon-deterministic finite automaton (NFA). In this case, the vectorq is replaced by a vector that can have more than one entry that is non-zero. Such a vector then represents an element of thepower set ofQ; it’s just anindicator function onQ. Likewise, the state transition matrices${\displaystyle \{U_{\alpha }\}}$ 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 aring ofcharacteristic 2.

A well-known theorem states that, for each DFA, there is an equivalent NFA, andvice versa. This implies that the set oflanguages that can be recognized by DFA's and NFA's are the same; these are theregular 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 astochastic matrix for the transition matrices, and aprobability vector for the state; this gives aprobabilistic 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 asimplex; 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 ofMarkov chain.

By contrast, in a QFA, the manifold iscomplex projective space${\displaystyle \mathbb{C}{P}^N}$, and the transition matrices are unitary matrices. Each point in${\displaystyle \mathbb{C}{P}^N}$ corresponds to a (pure)quantum-mechanical state; the unitary matrices can be thought of as governing the time evolution of the system (viz in theSchrödinger picture). The generalization from pure states tomixed states should be straightforward: A mixed state is simply ameasure-theoreticprobability distribution on${\displaystyle \mathbb{C}{P}^N}$.

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 behindmaximum entropy methods: these simply guarantee crisp, compact operation of the automaton. Put in other words, themachine learning methods used to trainhidden Markov models generalize to QFAs as well: theViterbi algorithm and theforward–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, byIon Baianu.^[3][4]

Measure-once automata were introduced byCris Moore andJames P. Crutchfield.^[2] They may be defined formally as follows.

As with an ordinaryfinite automaton, the quantum automaton is considered to have${\displaystyle N}$ possible internal states, represented in this case by an${\displaystyle N}$-statequdit${\displaystyle |\psi ⟩}$. More precisely, the${\displaystyle N}$-state qudit${\displaystyle |\psi ⟩\in P({\mathbb{C}}^N)}$ is an element of${\displaystyle (N-1)}$-dimensionalcomplex projective space, carrying aninner product${\displaystyle \Vert \cdot \Vert }$ that is theFubini–Study metric.

Thestate transitions,transition matrices orde Bruijn graphs are represented by a collection of${\displaystyle N\times N}$unitary matrices${\displaystyle U_{\alpha }}$, with one unitary matrix for each letter${\displaystyle \alpha \in \mathrm{\Sigma }}$. That is, given an input letter${\displaystyle \alpha }$, the unitary matrix describes the transition of the automaton from its current state${\displaystyle |\psi ⟩}$ to its next state${\displaystyle |{\psi }^{\mathrm{\prime }}⟩}$:

${\displaystyle |{\psi }^{\mathrm{\prime }}⟩=U_{\alpha }|\psi ⟩}$

Thus, the triple${\displaystyle (P({\mathbb{C}}^N),\mathrm{\Sigma },\{U_{\alpha }|\alpha \in \mathrm{\Sigma }\})}$ form aquantum semiautomaton.

Theaccept state of the automaton is given by an${\displaystyle N\times N}$projection matrix${\displaystyle P}$, so that, given a${\displaystyle N}$-dimensional quantum state${\displaystyle |\psi ⟩}$, the probability of${\displaystyle |\psi ⟩}$ being in the accept state is

${\displaystyle ⟨\psi |P|\psi ⟩=\Vert P|\psi ⟩{\Vert }^2}$

The probability of the state machine accepting a given finite input string${\displaystyle \sigma =({\sigma }_0,{\sigma }_1,\cdots ,{\sigma }_k)}$ is given by

${\displaystyle \mathrm{Pr}(\sigma )=\Vert P{U}_{{\sigma }_k}\cdots U_{{\sigma }_1}{U}_{{\sigma }_0}|\psi ⟩{\Vert }^2}$

Here, the vector${\displaystyle |\psi ⟩}$ 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${\displaystyle \varnothing }$ is understood to be just the unit matrix, so that

${\displaystyle \mathrm{Pr}(\varnothing )=\Vert P|\psi ⟩{\Vert }^2}$

is just the probability of the initial state being an accepted state.

Because the left-action of${\displaystyle U_{\alpha }}$ on${\displaystyle |\psi ⟩}$ reverses the order of the letters in the string${\displaystyle \sigma }$, it is not uncommon for QFAs to be defined using a right action on theHermitian transpose states, simply in order to keep the order of the letters the same.

Alanguage over the alphabet${\displaystyle \mathrm{\Sigma }}$ is accepted with probability${\displaystyle p}$ by a quantum finite automaton (and a given, fixed initial state${\displaystyle |\psi ⟩}$), if, for all sentences${\displaystyle \sigma }$ in the language, one has${\displaystyle p\le \mathrm{Pr}(\sigma )}$.

Consider the classicaldeterministic finite automaton given by thestate transition table

State Transition Table   Input State 1 0 S1 S1 S2 S2 S2 S1

State Diagram

The quantum state is a vector, inbra–ket notation

${\displaystyle |\psi ⟩=a_1|S_1⟩+a_2|S_2⟩=\left[\begin{array}{c}{a}_1\\ a_2\end{array}\right]}$

with thecomplex numbers${\displaystyle a_1,a_2}$ normalized so that

${\displaystyle \left[\begin{array}{c}{a}_1^{\ast }{a}_2^{\ast }\end{array}\right]\left[\begin{array}{c}{a}_1\\ a_2\end{array}\right]=a_1^{\ast }{a}_1+a_2^{\ast }{a}_2=1}$

The unitary transition matrices are

and

Taking${\displaystyle S_1}$ to be the accept state, the projection matrix is

As should be readily apparent, if the initial state is the pure state${\displaystyle |S_1⟩}$ or${\displaystyle |S_2⟩}$, 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 theregular language for the classical DFA, and is given by theregular expression:

${\displaystyle (1^{\ast }({01}^{\ast }0{)}^{\ast }{)}^{\ast }}$

The non-classical behaviour occurs if both${\displaystyle a_1}$ and${\displaystyle a_2}$ are non-zero. More subtle behaviour occurs when the matrices${\displaystyle U_0}$ and${\displaystyle U_1}$ are not so simple; see, for example, thede Rham curve as an example of a quantum finite state machine acting on the set of all possible finite binary strings.

Measure-many automata were introduced by Kondacs and Watrous in 1997.^[1] 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, orquantum measurement, performed after each letter is read. A formal definition follows.

TheHilbert space${\displaystyle {\mathcal{H}}_Q}$ is decomposed into threeorthogonal subspaces

${\displaystyle {\mathcal{H}}_Q={\mathcal{H}}_{\text{accept}}\oplus {\mathcal{H}}_{\text{reject}}\oplus {\mathcal{H}}_{\text{non-halting}}}$

In the literature, these orthogonal subspaces are usually formulated in terms of the set${\displaystyle Q}$ of orthogonal basis vectors for the Hilbert space${\displaystyle {\mathcal{H}}_Q}$. This set of basis vectors is divided up into subsets${\displaystyle Q_{\text{acc}}\subseteq Q}$ and${\displaystyle Q_{\text{rej}}\subseteq Q}$, such that

${\displaystyle {\mathcal{H}}_{\text{accept}}=\mathrm{span}\{|q⟩:|q⟩\in Q_{\text{acc}}\}}$

is thelinear span of the basis vectors in the accept set. The reject space is defined analogously, and the remaining space is designated thenon-halting subspace. There are three projection matrices,${\displaystyle P_{\text{acc}}}$,${\displaystyle P_{\text{rej}}}$ and${\displaystyle P_{\text{non}}}$, each projecting to the respective subspace:

${\displaystyle P_{\text{acc}}:{\mathcal{H}}_Q\to {\mathcal{H}}_{\text{accept}}}$

and so on. The parsing of the input string proceeds as follows. Consider the automaton to be in a state${\displaystyle |\psi ⟩}$. After reading an input letter${\displaystyle \alpha }$, the automaton will be in the state

${\displaystyle |{\psi }^{\mathrm{\prime }}⟩=U_{\alpha }|\psi ⟩}$

At this point, a measurement whose three possible outcomes have eigenspaces${\displaystyle {\mathcal{H}}_{\text{accept}}}$,${\displaystyle {\mathcal{H}}_{\text{reject}}}$,${\displaystyle {\mathcal{H}}_{\text{non-halting}}}$ is performed on the state${\displaystyle |{\psi }^{\mathrm{\prime }}⟩}$, at which time its wave-function collapses into one of the three subspaces${\displaystyle {\mathcal{H}}_{\text{accept}}}$ or${\displaystyle {\mathcal{H}}_{\text{reject}}}$ or${\displaystyle {\mathcal{H}}_{\text{non-halting}}}$. The probability of collapse to the "accept" subspace is given by

${\displaystyle {\mathrm{Pr}}_{\text{acc}}(\sigma )=\Vert P_{\text{acc}}|{\psi }^{\mathrm{\prime }}⟩{\Vert }^2,}$

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${\displaystyle P_{\text{non}}}$. Processing continues until the whole string is read, or the machine halts. Often, additional symbols${\displaystyle \kappa }$ 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${\displaystyle (Q;\mathrm{\Sigma };\delta ;q_0;Q_{\text{acc}};Q_{\text{rej}})}$. Here,${\displaystyle Q}$,${\displaystyle \mathrm{\Sigma }}$,${\displaystyle Q_{\text{acc}}}$ and${\displaystyle Q_{\text{rej}}}$ are as defined above. The initial state is denoted by${\displaystyle |q_0⟩}$. The unitary transformations are denoted by the map${\displaystyle \delta }$,

${\displaystyle \delta :Q\times \mathrm{\Sigma }\times Q\to \mathbb{C}}$

so that

${\displaystyle U_{\alpha }|q_i⟩=\sum _{q_j\in Q}\delta (q_i,\alpha ,q_j)|q_j⟩}$

As of 2019, mostquantum computers are implementations of measure-once quantum finite automata, and the software systems for programming them expose the state-preparation of${\displaystyle |\psi ⟩}$, measurement${\displaystyle P}$ and a choice of unitary transformations${\displaystyle U_{\alpha }}$, such thecontrolled NOT gate, theHadamard transform and otherquantum 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-likepure state, nor can the unitary operators be precisely applied. Thus, the initial state must be taken as amixed state

${\displaystyle \rho =\int p(x)|{\psi }_x⟩dx}$

for some probability distribution${\displaystyle p(x)}$ characterizing the ability of the machinery to prepare an initial state close to the desired initial pure state${\displaystyle |\psi ⟩}$. This state is not stable, but suffers from some amount ofquantum decoherence over time. Precise measurements are also not possible, and one instead usespositive 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

${\displaystyle U_{\alpha ,(\rho )}=\int p_{\alpha }(x)U_{\alpha ,x}dx}$

for some probability distribution${\displaystyle p_{\alpha }(x)}$ describing how well the machinery can effect the desired transformation${\displaystyle 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 anergodic process, or more accurately, amixing process that only concatenates transformations onto a state, but also smears the state over time.

There is no quantum analog to thepush-down automaton orstack machine. This is due to theno-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 arbitrarytopological spaces. For example, one may take some (N-dimensional)Riemann symmetric space to take the place of${\displaystyle \mathbb{C}{P}^N}$. In place of the unitary matrices, one uses theisometries of the Riemannian manifold, or, more generally, some set ofopen 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 aformal language is accepted by thistopological 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 anM-automaton. The behaviour of topological automata is studied in the field oftopological 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 stateP; that is${\displaystyle \mathbf{P}\mathbf{r}=|⟨P|\psi ⟩{|}^2}$. But thisprobability amplitude is just a very simple function of the distance between the point${\displaystyle |P⟩}$ and the point${\displaystyle |\psi ⟩}$ in${\displaystyle \mathbb{C}{P}^N}$, under the distancemetric given by theFubini–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 ageometric automaton or ametric automaton, where${\displaystyle \mathbb{C}{P}^N}$ is generalized to somemetric space, and the probability measure is replaced by a simple function of the metric on that space.

• Quantum Markov chain
• Blum–Shub–Smale machine
• Real computer

• Quantum information theory
• Finite-state machines

• Articles with short description
• Short description matches Wikidata