Quantum Finite Automata - Example

Example

Consider the classical deterministic finite automaton 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

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

with the complex numbers 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 for the classical DFA, and is given by the regular expression:

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 as an example of a quantum finite state machine acting on the set of all possible finite binary strings.

Read more about this topic:  Quantum Finite Automata

Famous quotes containing the word example:

    “Our intellect is not the most subtle, the most powerful, the most appropriate, instrument for revealing the truth. It is life that, little by little, example by example, permits us to see that what is most important to our heart, or to our mind, is learned not by reasoning but through other agencies. Then it is that the intellect, observing their superiority, abdicates its control to them upon reasoned grounds and agrees to become their collaborator and lackey.”
    —Marcel Proust (1871–1922)