Quantum Finite Automata - Measure-once Automata

Measure-once Automata

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

As with an ordinary finite automaton, the quantum automaton is considered to have possible internal states, represented in this case by an -state qubit . More precisely, the -state qubit is an element of -dimensional complex projective space, carrying an inner product that is the Fubini-Study metric.

The state transitions, transition matrixes or de Bruijn graphs are represented by a collection of unitary matrixes, 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 of the automaton is given by an projection matrix, 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 stated 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 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 by a quantum finite automaton, if, for all sentences in the language, (and a given, fixed initial state ), one has .