Quantum Finite Automata - Measure-many Automata

Measure-many Automata

Measure-many automata were introduced by Kondacs and Watrous in 1997. 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 is decomposed into three orthogonal subspaces

In the literature, these orthogonal subspaces are usually formulated in terms of the set of orthogonal basis vectors for the Hilbert space . This set of basis vectors is divided up into subsets and, such that

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

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

At this point, a measurement is performed on the state, using the projection operators, at which time its wave-function collapses into one of the three subspaces or or . The probability of collapse is given by

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 . 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 . Here, and are as defined above. The initial state is denoted by . The unitary transformations are denoted by the map ,

so that