Quantum finite automata

From Wikipedia, the free encyclopedia

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 Failed to parse (Cannot write to or create math output directory): \sigma=(\sigma_0,\sigma_1,\cdots,\sigma_k)

of letters Failed to parse (Cannot write to or create math output directory): \sigma_i
from a finite alphabet Failed to parse (Cannot write to or create math output directory): \Sigma\ni\sigma_i

, and assigning to each such string a probability Failed to parse (Cannot write to or create math output directory): \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 1 Measure-once automata 2 Example 3 Measure-many automata 4 Geometric generalizations 5 See also 6 References

[edit] 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 Failed to parse (Cannot write to or create math output directory): N

possible internal states, represented in this case by an Failed to parse (Cannot write to or create math output directory): N

-state qubit Failed to parse (Cannot write to or create math output directory): |\psi\rangle . More precisely, the Failed to parse (Cannot write to or create math output directory): N -state qubit Failed to parse (Cannot write to or create math output directory): |\psi\rangle\in \mathbb {C}P^N

is an element of Failed to parse (Cannot write to or create math output directory): N

-dimensional complex projective space, carrying an inner product Failed to parse (Cannot write to or create math output directory): \Vert\cdot\Vert

that is the Fubini-Study metric. 

The state transitions, transition matrixes or de Bruijn graphs are represented by a collection of Failed to parse (Cannot write to or create math output directory): N\times N

unitary matrixes Failed to parse (Cannot write to or create math output directory): U_\alpha

, with one unitary matrix for each letter Failed to parse (Cannot write to or create math output directory): \alpha\in\Sigma . That is, given an input letter Failed to parse (Cannot write to or create math output directory): \alpha , the unitary matrix describes the transition of the automaton from its current state Failed to parse (Cannot write to or create math output directory): |\psi\rangle

to its next state Failed to parse (Cannot write to or create math output directory): |\psi^\prime\rangle

Failed to parse (Cannot write to or create math output directory): |\psi^\prime\rangle = U_\alpha |\psi\rangle

Thus, the triple Failed to parse (Cannot write to or create math output directory): (\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 Failed to parse (Cannot write to or create math output directory): N\times N

projection matrix Failed to parse (Cannot write to or create math output directory): P

, so that, given a Failed to parse (Cannot write to or create math output directory): N -dimensional quantum state Failed to parse (Cannot write to or create math output directory): |\psi\rangle , the probability of Failed to parse (Cannot write to or create math output directory): |\psi\rangle

being in the accept state is

Failed to parse (Cannot write to or create math output directory): \langle\psi |P |\psi\rangle = \Vert P |\psi\rangle\Vert^2

The probability of the state machine accepting a given finite input string Failed to parse (Cannot write to or create math output directory): \sigma=(\sigma_0,\sigma_1,\cdots,\sigma_k)

is given by 

Failed to parse (Cannot write to or create math output directory): \operatorname{Pr}(\sigma) = \Vert P U_{\sigma_k} \cdots U_{\sigma_1} U_{\sigma_0}|\psi\rangle\Vert^2

Here, the vector Failed to parse (Cannot write to or create math output directory): |\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 Failed to parse (Cannot write to or create math output directory): \varnothing
is understood to be just the unit matrix, so that 

Failed to parse (Cannot write to or create math output directory): \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 Failed to parse (Cannot write to or create math output directory): U_\alpha

on Failed to parse (Cannot write to or create math output directory): |\psi\rangle
reverses the order of the letters in the string Failed to parse (Cannot write to or create math output directory): \sigma

, 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 Failed to parse (Cannot write to or create math output directory): p

by a quantum finite automaton, if, for all sentences Failed to parse (Cannot write to or create math output directory): \sigma
in the language, (and a given, fixed initial state Failed to parse (Cannot write to or create math output directory): |\psi\rangle

), one has Failed to parse (Cannot write to or create math output directory): p<\operatorname{Pr}(\sigma) .

[edit] 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

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

Failed to parse (Cannot write to or create math output directory): |\psi\rangle=a_1 |S_1\rangle + a_2|S_2\rangle = \begin{bmatrix} a_1 \\ a_2 \end{bmatrix}

with the complex numbers Failed to parse (Cannot write to or create math output directory): a_1,a_2

normalized so that

Failed to parse (Cannot write to or create math output directory): \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

Failed to parse (Cannot write to or create math output directory): U_0=\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}

and

Failed to parse (Cannot write to or create math output directory): U_1=\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}

Taking Failed to parse (Cannot write to or create math output directory): S_1

to be the accept state, the projection matrix is

Failed to parse (Cannot write to or create math output directory): P=\begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix}

As should be readily apparent, if the initial state is the pure state Failed to parse (Cannot write to or create math output directory): |S_1\rangle

or Failed to parse (Cannot write to or create math output directory): |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:

Failed to parse (Cannot write to or create math output directory): (1^*(01^*0)^*)^* \,\!

The non-classical behaviour occurs if both Failed to parse (Cannot write to or create math output directory): a_1

and Failed to parse (Cannot write to or create math output directory): a_2
are non-zero. More subtle behaviour occurs when the matrices Failed to parse (Cannot write to or create math output directory): U_0
and Failed to parse (Cannot write to or create math output directory): U_1
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.

[edit] 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 Failed to parse (Cannot write to or create math output directory): \mathcal{H}_Q=\mathbb{C}P^N ^{[dubious – discuss]} is decomposed into three orthogonal subspaces

Failed to parse (Cannot write to or create math output directory): \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 Failed to parse (Cannot write to or create math output directory): Q

of orthogonal basis vectors for the Hilbert space Failed to parse (Cannot write to or create math output directory): \mathcal{H}_Q

. This set of basis vectors is divided up into subsets Failed to parse (Cannot write to or create math output directory): Q_\mbox{acc} \subset Q

and Failed to parse (Cannot write to or create math output directory): Q_\mbox{rej} \subset Q

, such that

Failed to parse (Cannot write to or create math output directory): \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, Failed to parse (Cannot write to or create math output directory): P_\mbox{acc} , Failed to parse (Cannot write to or create math output directory): P_\mbox{rej}

and Failed to parse (Cannot write to or create math output directory): P_\mbox{non}

, each projecting to the respective subspace:

Failed to parse (Cannot write to or create math output directory): P\mbox{acc}:\mathcal{H}_Q \to \mathcal{H}_\mbox{accept}

and so on. The parsing of the input sring proceeds as follows. Consider the automaton to be in a state Failed to parse (Cannot write to or create math output directory): |\psi\rangle . After reading an input letter Failed to parse (Cannot write to or create math output directory): \alpha , the automaton will be in the state

Failed to parse (Cannot write to or create math output directory): |\psi^\prime\rangle =U_\alpha |\psi\rangle

At this point, a measurement is performed on the state Failed to parse (Cannot write to or create math output directory): |\psi^\prime\rangle , using the projection operators Failed to parse (Cannot write to or create math output directory): P , at which time its wave-function collapses into one of the three subspaces Failed to parse (Cannot write to or create math output directory): \mathcal{H}_\mbox{accept}

or Failed to parse (Cannot write to or create math output directory): \mathcal{H}_\mbox{reject}
or Failed to parse (Cannot write to or create math output directory): \mathcal{H}_\mbox{non-halting}

. The probability of collapse is given by

Failed to parse (Cannot write to or create math output directory): \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 Failed to parse (Cannot write to or create math output directory): P_\mbox{non} . Processng continues until the whole string is read, or the machine halts. Often, additional symbols Failed to parse (Cannot write to or create math output directory): \kappa

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 Failed to parse (Cannot write to or create math output directory): (Q;\Sigma; \delta; q_0; Q_\mbox{acc}; Q_\mbox{rej}) . Here, Failed to parse (Cannot write to or create math output directory): Q , Failed to parse (Cannot write to or create math output directory): \Sigma , Failed to parse (Cannot write to or create math output directory): Q\mbox{acc}

and Failed to parse (Cannot write to or create math output directory): Q\mbox{rej}
are as defined above. The initial state is denoted by Failed to parse (Cannot write to or create math output directory): |\psi\rangle=|q_0\rangle

. The unitary transformations are denoted by the map Failed to parse (Cannot write to or create math output directory): \delta ,

Failed to parse (Cannot write to or create math output directory): \delta:Q\times \Sigma \times Q \to \mathbb{C}

so that

Failed to parse (Cannot write to or create math output directory): U_\alpha |q_1\rangle = \sum_{q_2\in Q} \delta (q_1, \alpha, q_2) |q_2\rangle

[edit] 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 Failed to parse (Cannot write to or create math output directory): \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 Failed to parse (Cannot write to or create math output directory): \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 Failed to parse (Cannot write to or create math output directory): \vert P\rangle

and the point Failed to parse (Cannot write to or create math output directory): \vert \psi\rangle
in Failed to parse (Cannot write to or create math output directory): \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 Failed to parse (Cannot write to or create math output directory): \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.

[edit] See also

• Quantum Markov chain

[edit] References

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

• L. Accardi (2001), "Quantum stochastic processes", in Hazewinkel, Michiel, Encyclopaedia of Mathematics, Kluwer Academic Publishers, ISBN 978-1556080104  (Provides an intro to quantum Markov chains.)
• Alex Brodsky, Nicholas Pipenger, "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.