Quantum automata: An overview

Quantum state machines are introduced. Amplitudes of computational paths, computational bases, superposition states, and evolution operators;are discussed. The main part of the paper develops a theory of quantum automata and their slightly more general versions, q-automata. Quantum languages and eta-quantum languages, 0 less than or equal to eta < 1, are studied. A method is given for reducing the size of the state space. Functions that can be realized as probability maps for q-automata are characterized. Quantum gates are discussed. A quantum pumping lemma is employed to show that there are regular languages that are not eta-quantum 0 less than or equal to eta < 1. The paper closes with a list of open problems.