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.

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.

1 Measure-once automata
2 Example
3 Measure-many automata
4 Quantum Markov chain
5 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 $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$

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)$ .

[edit] Example

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

**State Transition Table**
Input State	1	0
S₁	S₁	S₂
S₂	S₂	S₁

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 $a 1, a 2$ 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 trasnsition matrices are

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

and

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

Taking $S 1$ to be the accept state, the projection matrix is

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

As should be readily appearant, 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^*01^*)^* \,\!$

The non-classical behaviour occurs if both $a 1$ and $a 2$ are non-zero. More subtle behaviour occurs when the matricies $U 0$ and $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 $\mathcal{H}_Q=\mathbb{C}P^N$ 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, $P acc$ , $P rej$ and $P non$ , 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 sring 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 $P non$ . Processng 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;Σ;δ; q 0; Q acc; Q rej)$ . Here, $Q$ , $Σ$ , $Q acc$ and $Q rej$ 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$

[edit] Quantum Markov chain

The quantum Markov chain is a reformulation of the ideas of a classical Markov chain, replacing the classical definitions of probability with quantum probability. Very roughly, the theory of a quantum Markov chain resembles that of a measure-many automaton, with some important substitutions: the initial state is to be replaced by a density matrix, and the projection operators are to be replaced by positive operator valued measures.

More precisely, a quantum Markov chain is a pair $(E,ρ)$ with $ρ$ a density matrix and $E$ a quantum channel such that

$E:\mathcal{B}\otimes\mathcal{B}\to\mathcal{B}$

is a completely positive trace-preserving map, and $\mathcal{B}$ a C^*-algebra of bounded operators. The pair must obey the quantum Markov condition, that

$\operatorname{Tr} \rho (b_1\otimes b_2) = \operatorname{Tr} \rho E(b_1, b_2)$

for all $b_1,b_2\in \mathcal{B}$ .

[edit] References

^ C. Moore, J. Crutchfield, "Quantum automata and quantum grammars", Theoretical Computer Science, 237 (2000) pp 257-306.
^ A. Kondas 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