Quantum finite automaton: Difference between revisions

Revision as of 02:44, 3 May 2018

Latest revision as of 06:31, 14 April 2025

(26 intermediate revisions by 18 users not shown)

Line 1:

{{Short description|Quantum analog of probabilistic automata}}

In [[quantum computing]], '''quantum finite automata''' ('''QFA''') or '''quantum state machines''' are a quantum analog of [[probabilistic automata]] or a [[Markov decision process]]. They are related to [[quantum computer]]s inprovide a similarmathematical fashionabstraction asof [[finite automata]] are related toreal-world [[Turingquantum machinecomputer]]s. 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 chain]]s. QFAs are, in turn, special cases of '''geometric finite automata''' or '''topological finite automata'''.

The automata work by acceptingreceiving a finite-length [[string (computer science)|string]] <math>\sigma=(\sigma_0,\sigma_1,\cdots,\sigma_k)</math> of letters <math>\sigma_i</math> from a finite [[alphabet (computer science)|alphabet]] <math>\Sigma</math>, and assigning to each such string a [[probability]] <math>\operatorname{Pr}(\sigma)</math> indicating the probability of the automaton being in an [[accept state]]; that is, indicating whether the automaton accepted or rejected the string.

The [[formal language|languages]] accepted by QFAs are not the [[regular language]]s of [[deterministic finite automata]], nor are they the [[stochastic language]]s 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 theory|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 matrix|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 <math>\Sigma</math> denote the set of input symbols. For a given input symbol <math>\alpha\in\Sigma</math>, write <math>U_\alpha</math> as the adjacency matrix that describes the evolution of the DFA to its next state. The set <math>\{U_\alpha | \alpha\in\Sigma\}</math> 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 <math>U_\alpha</math> is ''N'' by ''N''-dimensional. The initial state <math>q_0\in Q</math> corresponds to a column vector with a one in the ''q''₀'th row. A general state ''q'' is then a column vector with a one in the ''q'''th row. By [[abuse of notation]], let ''q''₀ and ''q'' also denote these two vectors. Then, after reading input symbols <math>\alpha\beta\gamma\cdots</math> from the input tape, the state of the DFA will be given by <math>q = \cdots U_\gamma U_\beta U_\alpha q_0.</math> The state transitions are given by ordinary [[matrix multiplication]] (that is, multiply ''q''₀ by <math>U_\alpha</math>, ''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 operator]]s and vectors, almost begs for generalization, by replacing the state-vector ''q'' by some general vector, and the matrices <math>\{U_\alpha\}</math> by some general operators. This is essentially what a QFA does: it replaces ''q'' by a [[probabilityunit amplitudevector]], and the <math>\{U_\alpha\}</math> by [[unitary matrix|unitary matrices]]. Other, similar generalizations also become obvious: the vector ''q'' can be some [[probability distribution|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 whichthat can have more than one entry that is non-zero. Such a vector then represents an element of the [[power set]] of ''Q''; itsit’s just an [[indicator function]] on ''Q''. Likewise, the state transition matrices <math>\{U_\alpha\}</math> 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 (mathematics)|ring]] of [[characteristic 2]].

A well-known theorem states that, for each DFA, there is an equivalent NFA, and [[Nondeterministic finite automaton#Equivalence_to_DFA|vice versa]]. This implies that the set of [[formal language|languages]] that can be recognized by DFA's and NFA's are the same; these are the [[regular language]]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]] 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]] <math>\mathbb{C}P^N</math>, and the transition matrices are unitary matrices. Each point in <math>\mathbb{C}P^N</math> corresponds to a quantum-mechanical(pure) [[probabilityquantum amplitude]] or [[purestate|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 state (physics)|mixed states]] should be straightforward: A mixed state is simply a [[measure theory|measure-theoretic]] [[probability distribution]] on <math>\mathbb{C}P^N</math>.

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]]s: these simply guarantee crisp, compact operation of the automaton. Put in other words, the [[machine learning]] methods used to train [[hidden Markov model]]s generalize to QFAs as well: the [[Viterbi algorithm]] and the [[forward-backwardforward–backward algorithm]] generalize readily to the QFA.

Although the study of QFA was popularized in the work of Kondacs and Watrous in 1997<ref name="Kondacs"/> and later by Moore and Crutchfeld,<ref name="Moore"/> they were described as early as 1971, by [[Ion Baianu]].<ref>I. BainauBaianu, "[http://cogprints.org/3674/1/ORganismic_supercategories_and_qualitative_dynamics_of_systems_final3.pdf Organismic Supercategories and Qualitative Dynamics of Systems]" (1971), Bulletin of Mathematical Biophysics, '''33''' pp.339-354.</ref><ref>I. Baianu, "Categories, Functors and Quantum Automata Theory" (1971). The 4th Intl. Congress LMPS, August-Sept.1971</ref>

==Measure-once automata==

Measure-once automata were introduced by [[Cris Moore]] and [[James P. Crutchfield]].<ref name="Moore">C. Moore, J. Crutchfield, "Quantum automata and quantum grammars", ''[[Theoretical Computer Science (journal)|Theoretical Computer Science]]'', '''237''' (2000) pp 275-306.</ref> They may be defined formally as follows.

As with an ordinary [[finite automaton]], the quantum automaton is considered to have <math>N</math> possible internal states, represented in this case by an <math>N</math>-state [[qubitQubit#Qudits_and_qutrits|qudit]] <math>|\psi\rangle</math>. More precisely, the <math>N</math>-state qubitqudit <math>|\psi\rangle\in P(\mathbb {C}P^N)</math> is an element of <math>(N-1)</math>-dimensional [[complex projective space]], carrying an [[inner product]] <math>\Vert\cdot\Vert</math> that is the [[Fubini–Study metric]].

The [[state transition]]s, [[Stochastic matrix|transition matrices]] or [[de Bruijn graph]]s are represented by a collection of <math>N\times N</math> [[unitary matrixmatrices]]es <math>U_\alpha</math>, with one unitary matrix for each letter <math>\alpha\in\Sigma</math>. That is, given an input letter <math>\alpha</math>, the unitary matrix describes the transition of the automaton from its current state <math>|\psi\rangle</math> to its next state <math>|\psi^\prime\rangle</math>:

:<math>|\psi^\prime\rangle = U_\alpha |\psi\rangle</math>

Thus, the triple <math>(P(\mathbb {C}P^N),\Sigma,\{U_\alpha\;\vert\;\alpha\in\Sigma\})</math> form a [[quantum semiautomaton]].

The [[accept state]] of the automaton is given by an <math>N\times N</math> [[projection matrix]] <math>P</math>, so that, given a <math>N</math>-dimensional quantum state <math>|\psi\rangle</math>, the probability of <math>|\psi\rangle</math> being in the accept state is

Line 51 ⟶ 52:

Because the left-action of <math>U_\alpha</math> on <math>|\psi\rangle</math> reverses the order of the letters in the string <math>\sigma</math>, 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 [[regularformal language|language]] over the alphabet <math>\Sigma</math> is accepted with probability <math>p</math> by a quantum finite automaton, if(and a given, forfixed allinitial sentencesstate <math>|\sigmapsi\rangle</math> in the language), (and a givenif, fixedfor initialall statesentences <math>|\psi\ranglesigma</math>) in the language, one has <math>p<\leq\operatorname{Pr}(\sigma)</math>.

==Example==

Line 103 ⟶ 104:

Measure-many automata were introduced by Kondacs and Watrous in 1997.<ref name="Kondacs">{{citation

| last1 = Kondacs | first1 = A.

| last2 = Watrous | first2 = J. | authorlinkauthor2link = John Watrous (computer scientist)

| contribution = On the power of quantum finite state automata

| pages = 66–75

Line 113 ⟶ 114:

:<math>\mathcal{H}_Q=\mathcal{H}_\text{accept} \oplus \mathcal{H}_\text{reject} \oplus \mathcal{H}_\text{non-halting}</math>

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

:<math>\mathcal{H}_\text{accept}=\operatorname{span} \{|q\rangle : |q\rangle \in Q_\text{acc} \}</math>

Line 125 ⟶ 126:

:<math>|\psi^\prime\rangle =U_\alpha |\psi\rangle</math>

At this point, a measurement iswhose performedthree onpossible theoutcomes statehave eigenspaces <math>|\psi^mathcal{H}_\primetext{accept}</math>, <math>\ranglemathcal{H}_\text{reject}</math>, using<math>\mathcal{H}_\text{non-halting}</math> theis projectionperformed operatorson the state <math>P|\psi^\prime\rangle</math>, at which time its wave-function collapses into one of the three subspaces <math>\mathcal{H}_\text{accept}</math> or <math>\mathcal{H}_\text{reject}</math> or <math>\mathcal{H}_\text{non-halting}</math>. The probability of collapse to the "accept" subspace is given by

:<math>\operatorname{Pr}_\text{acc} (\sigma) = \Vert P_\text{acc} |\psi^\prime\rangle \Vert^2,</math>

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

:<math>\delta:Q\times \Sigma \times Q \to \mathbb{C}</math>

Line 139 ⟶ 140:

so that

:<math>U_\alpha |q_1q_i\rangle = \sum_{q_2q_j\in Q} \delta (q_1q_i, \alpha, q_2q_j) |q_2q_j\rangle </math>

== Relation to quantum computing ==

As of 2019, most [[quantum computer]]s are implementations of measure-once quantum finite automata, and the software systems for programming them expose the state-preparation of <math>|\psi\rangle</math>, measurement <math>P</math> and a choice of unitary transformations <math>U_\alpha</math>, such the [[controlled NOT gate]], the [[Hadamard transform]] and other [[quantum logic gate]]s, 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]], nor can the unitary operators be precisely applied. Thus, the initial state must be taken as a [[mixed quantum state|mixed state]]

:<math>\rho = \int p(x) |\psi_x\rangle dx</math>

for some probability distribution <math>p(x)</math> characterizing the ability of the machinery to prepare an initial state close to the desired initial pure state <math>|\psi\rangle</math>. 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 [[POVM|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

:<math>U_{\alpha, (\rho)}=\int p_\alpha(x) U_{\alpha,x} dx</math>

for some probability distribution <math>p_\alpha(x)</math> describing how well the machinery can effect the desired transformation <math>U_\alpha</math>.

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 (physics)|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.

==Geometric generalizations==

The above constructions indicate how the concept of a quantum finite automaton can be generalized to arbitrary [[topological space]]s. For example, one may take some (''N''-dimensional) [[Riemann symmetric space]] to take the place of <math>\mathbb{C}P^N</math>. In place of the unitary matrices, one uses the [[isometry|isometries]] of the Riemannian manifold, or, more generally, some set of [[open function]]s 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]] 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 [[semiautomaton|M-automaton]]. The behaviour of topological automata is studied in the field of [[topological 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 state ''P''; that is <math>\boldmathbf{Pr} = \vert \langle P\vert \psi\rangle \vert^2</math>. But this [[probability amplitude]] is just a very simple function of the distance between the point <math>\vert P\rangle</math> and the point <math>\vert \psi\rangle</math> in <math>\mathbb{C}P^N</math>, under the distance [[metric (mathematics)|metric]] given by the [[Fubini–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 a '''geometric automaton''' or a '''metric automaton''', where <math>\mathbb{C}P^N</math> is generalized to some [[metric space]], and the probability measure is replaced by a simple function of the metric on that space.

==See also==

* [[Quantum Markov chain]]

* [[Blum–Shub–Smale machine]]

* [http://www.buzwordsalad.com Langton's ant] wave equation.

* [[Real computer]]

==References==

<references/>

==Notes==

* {{springer|author=L. Accardi|title=Quantum stochastic processes|id=Q/q076330}} ''(Provides an intro to quantum Markov chains.)''

{{reflist}}

* Alex Brodsky, Nicholas Pippenger, [http://xxx.lanl.gov/abs/quant-ph/9903014 "Characterization of 1-way Quantum Finite Automata"], ''SIAM Journal on Computing'' '''31'''(2002) pp 1456–1478.

* Vincent D. Blondel, Emmanual Jeandel, Pascal Koiran and Natacha Portier, "Decidable and Undecidable Problems about Quantum Automata", ''SIAM Journal on Computing'' '''34''' (2005) pp 1464–1473.

{{quantum computing}}

[[Category:Quantum information theory]]

[[Category:Finite-state automatamachines]]