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
An alphabet is a standardized set of basic written graphemes (called letters) that represent the phonemes of certain spoken languages. Not all writing systems represent language in this way; in a syllabary, each character represents a syllab ...
, and assigning to each such string a
probability
Probability is the branch of mathematics concerning numerical descriptions of how likely an event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and 1, where, roughly speakin ...
indicating the probability of the automaton being in an
accept state
A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number o ...
; that is, indicating whether the automaton accepted or rejected the string.
The
languages accepted by QFAs are not the
regular language
In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...
s of
deterministic finite automata
In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state automa ...
, 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
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
interpretation of
deterministic finite automata
In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state automa ...
(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
In mathematics, particularly in linear algebra, matrix multiplication is a binary operation that produces a matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the s ...
.
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 ''q''
0'th row. A general state ''q'' is then a column vector with a one in the ''qth row. By
abuse of notation
In mathematics, abuse of notation occurs when an author uses a mathematical notation in a way that is not entirely formally correct, but which might help simplify the exposition or suggest the correct intuition (while possibly minimizing errors a ...
, let ''q''
0 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
In mathematics, particularly in linear algebra, matrix multiplication is a binary operation that produces a matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the s ...
(that is, multiply ''q''
0 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
probability amplitude
In quantum mechanics, a probability amplitude is a complex number used for describing the behaviour of systems. The modulus squared of this quantity represents a probability density.
Probability amplitudes provide a relationship between the qu ...
, 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
In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of mapping the object to itself while preserving all of its structure. The set of all 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
In automata theory, a finite-state machine is called a deterministic finite automaton (DFA), if
* each of its transitions is ''uniquely'' determined by its source state and input symbol, and
* reading an input symbol is required for each state tr ...
(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
In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is post ...
of ''Q''; its 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, that is, so that one is working with a
ring
Ring may refer to:
* Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry
* To make a sound with a bell, and the sound made by a bell
:(hence) to initiate a telephone connection
Arts, entertainment and media Film and ...
of
characteristic 2.
A well-known theorem states that, for each DFA, there is an equivalent NFA, and
vice versa
References
Additional references
*
*
{{Latin phrases
Lists of Latin phrases, V
ca:Locució llatina#V
da:Latinske ord og vendinger#V
fr:Liste de locutions latines#V
id:Daftar frasa Latin#V
it:Locuzioni latine#V
nl:Lijst van Latijns ...
. This implies that the set of
languages that can be recognized by DFA's and NFA's are the same; these are the
regular language
In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...
s. 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
In mathematics, a stochastic matrix is a square matrix used to describe the transitions of a Markov chain. Each of its entries is a nonnegative real number representing a probability. It is also called a probability matrix, transition matrix, ...
for the transition matrices, and a
probability vector
In mathematics and statistics, a probability vector or stochastic vector is a vector with non-negative entries that add up to one.
The positions (indices) of a probability vector represent the possible outcomes of a discrete random variable, and ...
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
In mathematics, complex projective space is the projective space with respect to the field of complex numbers. By analogy, whereas the points of a real projective space label the lines through the origin of a real Euclidean space, the points of a ...
, and the transition matrices are unitary matrices. Each point in
corresponds to a quantum-mechanical
probability amplitude
In quantum mechanics, a probability amplitude is a complex number used for describing the behaviour of systems. The modulus squared of this quantity represents a probability density.
Probability amplitudes provide a relationship between the qu ...
or
pure state
In quantum physics, a quantum state is a mathematical entity that provides a probability distribution for the outcomes of each possible measurement on a system. Knowledge of the quantum state together with the rules for the system's evolution in t ...
; the unitary matrices can be thought of as governing the time evolution of the system (viz in the
Schrödinger picture
In physics, the Schrödinger picture is a formulation of quantum mechanics in which the state vectors evolve in time, but the operators (observables and others) are mostly constant with respect to time (an exception is the Hamiltonian which may ...
). 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 method
The principle of maximum entropy states that the probability distribution which best represents the current state of knowledge about a system is the one with largest entropy, in the context of precisely stated prior data (such as a proposition ...
s: these simply guarantee crisp, compact operation of the automaton. Put in other words, the
machine learning
Machine learning (ML) is a field of inquiry devoted to understanding and building methods that 'learn', that is, methods that leverage data to improve performance on some set of tasks. It is seen as a part of artificial intelligence.
Machine ...
methods used to train
hidden Markov model
A hidden Markov model (HMM) is a statistical Markov model in which the system being modeled is assumed to be a Markov process — call it X — with unobservable ("''hidden''") states. As part of the definition, HMM requires that there be an o ...
s generalize to QFAs as well: the
Viterbi algorithm
The Viterbi algorithm is a dynamic programming algorithm for obtaining the maximum a posteriori probability estimate of the most likely sequence of hidden states—called the Viterbi path—that results in a sequence of observed events, especiall ...
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, "Categories, Functors and Quantum Automata Theory" (1971). The 4th Intl.Congress LMPS, 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
A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number o ...
, the quantum automaton is considered to have
possible internal states, represented in this case by an
-state
qubit
In quantum computing, a qubit () or quantum bit is a basic unit of quantum information—the quantum version of the classic binary bit physically realized with a two-state device. A qubit is a two-state (or two-level) quantum-mechanical system, ...
. More precisely, the
-state qubit
is an element of
-dimensional
complex projective space
In mathematics, complex projective space is the projective space with respect to the field of complex numbers. By analogy, whereas the points of a real projective space label the lines through the origin of a real Euclidean space, the points of a ...
, carrying an
inner product
In mathematics, an inner product space (or, rarely, a Hausdorff pre-Hilbert space) is a real vector space or a complex vector space with an operation called an inner product. The inner product of two vectors in the space is a scalar, often ...
that is the
Fubini–Study metric
In mathematics, the Fubini–Study metric is a Kähler metric on projective Hilbert space, that is, on a complex projective space CP''n'' endowed with a Hermitian form. This metric was originally described in 1904 and 1905 by Guido Fubini and Edu ...
.
The
state transition
State may refer to:
Arts, entertainment, and media Literature
* ''State Magazine'', a monthly magazine published by the U.S. Department of State
* ''The State'' (newspaper), a daily newspaper in Columbia, South Carolina, United States
* ''Our S ...
s,
transition matrices or
de Bruijn graph
In graph theory, an -dimensional De Bruijn graph of symbols is a directed graph representing overlaps between sequences of symbols. It has vertices, consisting of all possible sequences of the given symbols; the same symbol may appear multiple ...
s 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
A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number o ...
of the automaton is given by an
projection matrix
In statistics, the projection matrix (\mathbf), sometimes also called the influence matrix or hat matrix (\mathbf), maps the vector of response values (dependent variable values) to the vector of fitted values (or predicted values). It describes t ...
, 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
In mathematics, the conjugate transpose, also known as the Hermitian transpose, of an m \times n complex matrix \boldsymbol is an n \times m matrix obtained by transposing \boldsymbol and applying complex conjugate on each entry (the complex co ...
states, simply in order to keep the order of the letters the same.
A
regular language
In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...
is accepted with probability
by a quantum finite automaton, if, for all sentences
in the language, (and a given, fixed initial state
), one has
.
Example
Consider the classical
deterministic finite automaton
In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state autom ...
given by the
state transition table
State may refer to:
Arts, entertainment, and media Literature
* ''State Magazine'', a monthly magazine published by the U.S. Department of State
* ''The State'' (newspaper), a daily newspaper in Columbia, South Carolina, United States
* ''Our S ...
The quantum state is a vector, in
bra–ket notation
:
with the
complex number
In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the fo ...
s
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
In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...
for the classical DFA, and is given by the
regular expression
A regular expression (shortened as regex or regexp; sometimes referred to as rational expression) is a sequence of characters that specifies a search pattern in text. Usually such patterns are used by string-searching algorithms for "find" ...
:
:
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
In mathematics, a de Rham curve is a certain type of fractal curve named in honor of Georges de Rham.
The Cantor function, Cesàro curve, Minkowski's question mark function, the Lévy C curve, the blancmange curve, and Koch curve are all spe ...
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
In quantum physics, a measurement is the testing or manipulation of a physical system to yield a numerical result. The predictions that quantum physics makes are in general probabilistic. The mathematical tools for making predictions about what ...
, 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 remaining space 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 is performed on the state
, using the projection operators
, at which time its wave-function collapses into one of the three subspaces
or
or
. 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
. Processing continues until the whole string is read, or the machine halts. Often, additional symbols
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
. Here,
,
,
and
are as defined above. The initial state is denoted by
. The unitary transformations are denoted by the map
,
:
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
, measurement
and a choice of unitary transformations
, such the
controlled NOT gate
In computer science, the controlled NOT gate (also C-NOT or CNOT), controlled-''X'' gate'','' controlled-bit-flip gate, Feynman gate or controlled Pauli-X is a quantum logic gate that is an essential component in the construction of a gate-bas ...
, the
Hadamard transform
The Hadamard transform (also known as the Walsh–Hadamard transform, Hadamard–Rademacher–Walsh transform, Walsh transform, or Walsh–Fourier transform) is an example of a generalized class of Fourier transforms. It performs an orthogonal ...
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
In quantum physics, a quantum state is a mathematical entity that provides a probability distribution for the outcomes of each possible measurement on a system. Knowledge of the quantum state together with the rules for the system's evolution in t ...
, nor can the unitary operators be precisely applied. Thus, the initial state must be taken as a
mixed state
:
for some probability distribution
characterizing the ability of the machinery to prepare an initial state close to the desired initial pure state
. 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
describing how well the machinery can effect the desired transformation
.
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 In physics, the no-cloning theorem states that it is impossible to create an independent and identical copy of an arbitrary unknown quantum state, a statement which has profound implications in the field of quantum computing among others. The theore ...
: 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 space
In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called po ...
s. For example, one may take some (''N''-dimensional)
Riemann symmetric space to take the place of
. In place of the unitary matrices, one uses the
isometries
In mathematics, an isometry (or congruence, or congruent transformation) is a distance-preserving transformation between metric spaces, usually assumed to be bijective. The word isometry is derived from the Ancient Greek: ἴσος ''isos'' mea ...
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
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of sy ...
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 In mathematics, topological dynamics is a branch of the theory of dynamical systems in which qualitative, asymptotic properties of dynamical systems are studied from the viewpoint of general topology.
Scope
The central object of study in topol ...
.
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
. But this probability amplitude is just a very simple function of the distance between the point
and the point
in
, under the distance
metric
Metric or metrical may refer to:
* Metric system, an internationally adopted decimal system of measurement
* An adjective indicating relation to measurement in general, or a noun describing a specific type of measurement
Mathematics
In mathem ...
given by the
Fubini–Study metric
In mathematics, the Fubini–Study metric is a Kähler metric on projective Hilbert space, that is, on a complex projective space CP''n'' endowed with a Hermitian form. This metric was originally described in 1904 and 1905 by Guido Fubini and Edu ...
. 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
is generalized to some
metric space
In mathematics, a metric space is a set together with a notion of '' distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general set ...
, and the probability measure is replaced by a simple function of the metric on that space.
See also
*
Quantum Markov chain In mathematics, the quantum Markov chain is a reformulation of the ideas of a classical Markov chain, replacing the classical definitions of probability with quantum probability.
Introduction
Very roughly, the theory of a quantum Markov chain rese ...
Notes
{{quantum computing
Quantum information theory
Finite automata