Quantum finite automata

In quantum computing, quantum finite automata or QFA are a quantum analog of probabilistic automata. They are related to quantum computers in a similar fashion as finite automata are related to Turing machines. 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. QFA's are, in turn, special cases of geometric finite automata or topological finite automata.

The automata work by accepting a finite-length string \sigma=(\sigma_0,\sigma_1,\cdots,\sigma_k) of letters σi from a finite alphabet \Sigma\ni\sigma_i, and assigning to each such string a probability \operatorname{Pr}(\sigma) indicating the probability of the automaton being in an accept state; that is, indicating whether the automaton accepted or rejected the string.

Contents

Measure-once automata

Measure-once automata were introduced by Moore and Crutchfield[1]. They may be defined formally as follows.

As with an ordinary finite automaton, the quantum automaton is considered to have N possible internal states, represented in this case by an N-state qubit |\psi\rangle. More precisely, the N-state qubit |\psi\rangle\in \mathbb {C}P^N is an element of N-dimensional complex projective space, carrying an inner product \Vert\cdot\Vert that is the Fubini-Study metric.

The state transitions, transition matrixes or de Bruijn graphs are represented by a collection of N\times N unitary matrixes Uα, with one unitary matrix for each letter \alpha\in\Sigma. That is, given an input letter α, the unitary matrix describes the transition of the automaton from its current state |\psi\rangle to its next state |\psi^\prime\rangle:

|\psi^\prime\rangle = U_\alpha |\psi\rangle

Thus, the triple (\mathbb {C}P^N,\Sigma,\{U_\alpha\vert\alpha\in\Sigma\}) form a quantum semiautomaton.

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

\langle\psi |P |\psi\rangle = \Vert P |\psi\rangle\Vert^2

The probability of the state machine accepting a given finite input string \sigma=(\sigma_0,\sigma_1,\cdots,\sigma_k) is given by

\operatorname{Pr}(\sigma) = \Vert P U_{\sigma_k} \cdots U_{\sigma_1} U_{\sigma_0}|\psi\rangle\Vert^2

Here, the vector |\psi\rangle is understood to represent the initial state of the automaton, that is, the state the automaton was in before it stated accepting the string input. The empty string \varnothing is understood to be just the unit matrix, so that

\operatorname{Pr}(\varnothing)= \Vert P |\psi\rangle\Vert^2

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

Because the left-action of Uα on |\psi\rangle reverses the order of the letters in the string σ, it is not uncommon for QFA's 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 regular language is accepted with probability p by a quantum finite automaton, if, for all sentences σ in the language, (and a given, fixed initial state |\psi\rangle), one has p<\operatorname{Pr}(\sigma).

Example

Consider the classical deterministic finite state machine given by the state transition table

State Transition Table
  Input
State
1 0
S1 S1 S2
S2 S2 S1
  State Diagram
DFAexample.svg

The quantum state is a vector, in bra-ket notation

|\psi\rangle=a_1 |S_1\rangle + a_2|S_2\rangle = 
\begin{bmatrix} a_1 \\ a_2 \end{bmatrix}

with the complex numbers a1,a2 normalized so that

\begin{bmatrix} a^*_1 \;\; a^*_2 \end{bmatrix} \begin{bmatrix} a_1 \\ a_2 \end{bmatrix} = a_1^*a_1 + a_2^*a_2 = 1

The unitary transition matrices are

U_0=\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}

and

U_1=\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}

Taking S1 to be the accept state, the projection matrix is

P=\begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix}

As should be readily apparent, if the initial state is the pure state |S_1\rangle or |S_2\rangle, 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 for the classical DFA, and is given by the regular expression:

(1^*(01^*0)^*)^* \,\!

The non-classical behaviour occurs if both a1 and a2 are non-zero. More subtle behaviour occurs when the matrices U0 and U1 are not so simple; see, for example, the de Rham curve 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.[2]. 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.

The Hilbert space \mathcal{H}_Q=\mathbb{C}P^N[dubious ] is decomposed into three orthogonal subspaces

\mathcal{H}_Q=\mathcal{H}_\mbox{accept} \oplus \mathcal{H}_\mbox{reject} \oplus \mathcal{H}_\mbox{non-halting}

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

\mathcal{H}_\mbox{accept}=\operatorname{span} \{|q\rangle : |q\rangle \in Q_\mbox{acc} \}

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 and Pnon, each projecting to the respective subspace:

P\mbox{acc}:\mathcal{H}_Q \to \mathcal{H}_\mbox{accept}

and so on. The parsing of the input string proceeds as follows. Consider the automaton to be in a state |\psi\rangle. After reading an input letter α, the automaton will be in the state

|\psi^\prime\rangle =U_\alpha |\psi\rangle

At this point, a measurement is performed on the state |\psi^\prime\rangle, using the projection operators P, at which time its wave-function collapses into one of the three subspaces \mathcal{H}_\mbox{accept} or \mathcal{H}_\mbox{reject} or \mathcal{H}_\mbox{non-halting}. The probability of collapse is given by

\operatorname{Pr}_\mbox{acc} (\sigma) = \Vert P_\mbox{acc} |\psi^\prime\rangle \Vert^2

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 Pnon. 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 meaure-many automaton is often denoted by the tuple (Q;Σ;δ;q0;Qacc;Qrej). Here, Q, Σ, Qacc and Qrej are as defined above. The initial state is denoted by |\psi\rangle=|q_0\rangle. The unitary transformations are denoted by the map δ,

\delta:Q\times \Sigma \times Q \to \mathbb{C}

so that

U_\alpha |q_1\rangle = \sum_{q_2\in Q} \delta (q_1, \alpha, q_2) |q_2\rangle

Geometric generalizations

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 \mathbb{C}P^N. 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 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 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 \bold{Pr} = \vert \langle P\vert \psi\rangle \vert^2. But this probability amplitude is just a very simple function of the distance between the point \vert P\rangle and the point \vert \psi\rangle in \mathbb{C}P^N, under the distance 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 \mathbb{C}P^N is generalized to some metric space, and the probability measure is replaced by a simple function of the metric on that space.

See also

References

  1. ^ C. Moore, J. Crutchfield, "Quantum automata and quantum grammars", Theoretical Computer Science, 237 (2000) pp 275-306.
  2. ^ Kondacs, A.; Watrous, J. (1997), "On the power of quantum finite state automata", Proceedings of the 38th Annual Symposium on Foundations of Computer Science, pp. 66–75 

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Quantum cellular automata — (QCA) refers to any one of several models of quantum computation, which have been devised in analogy to conventional models of cellular automata introduced by von Neumann. It may also refer to quantum dot cellular automata, which is a proposed… …   Wikipedia

  • Automata theory — Automata is defined as a system where energy, information and material is transformed, transmitted and used for performing some function without the direct participation of man .In theoretical computer science, automata theory is the study of… …   Wikipedia

  • Finite state machine — A finite state machine (FSM) or finite state automaton (plural: automata ) or simply a state machine, is a model of behavior composed of a finite number of states, transitions between those states, and actions. A finite state machine is an… …   Wikipedia

  • Finite-state machine — State machine redirects here. For infinite state machines, see State transition system. For fault tolerance methodology, see State machine replication. SFSM redirects here. For the Italian railway company, see Circumvesuviana. A finite state… …   Wikipedia

  • Quantum gate — A quantum gate or quantum logic gate is a basic quantum circuit operating on a small number of qubits. They are the analogues for quantum computers to classical logic gates for conventional digital computers. Quantum logic gates are reversible,… …   Wikipedia

  • Quantum dot cellular automaton — Quantum Dot Cellular Automata (sometimes referred to simply as quantum cellular automata, or QCA) Any device designed to represent data and perform computation, regardless of the physics principles it exploits and materials used to build it, must …   Wikipedia

  • automata theory — Body of physical and logical principles underlying the operation of any electromechanical device (an automaton) that converts information input in one form into another, or into some action, according to an algorithm. Norbert Wiener and Alan M.… …   Universalium

  • Subshift of finite type — In mathematics, subshifts of finite type are used to model dynamical systems, and in particular are the objects of study in symbolic dynamics and ergodic theory. They also describe the set of all possible sequences executed by a finite state… …   Wikipedia

  • Two-way deterministic finite automaton — In computer science, a two way deterministic finite automaton (2DFA) is an abstract machine, a generalized version of the deterministic finite automaton (DFA) which can revisit characters already processed. As in a DFA, there are a finite number… …   Wikipedia

  • QFA — Quantum Finite Automata (Computing » General) **** Qeshm Free Area (Governmental) **** Qeshm Free Area (Regional) * Quality Fitness in Ayrshire (Community » Sports) * Quantum Financial Advisors, Inc. (Business » Firms) * Quest For Al Qa eda… …   Abbreviations dictionary

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.