Quantum finite automata using ancilla qubits
Abstract:
We introduce a new model of quantum finite automata. By using
ancilla qubits, it becomes possible to recognize any regular
language with certainty. Some nonregular languages can be
recognized with one-sided unbounded error. We analyze a class
of languages that can be recognized in this model in terms of
a cascade composition of automata. This also allows to treat
the case of an automaton with both classical and quantum states.
ancilla qubits, it becomes possible to recognize any regular
language with certainty. Some nonregular languages can be
recognized with one-sided unbounded error. We analyze a class
of languages that can be recognized in this model in terms of
a cascade composition of automata. This also allows to treat
the case of an automaton with both classical and quantum states.
| Zugehörige Institution(en) am KIT | Fakultät für Informatik – Lehrstuhl Informatik für Ingenieure und Naturwissenschaftler (Lehrstuhl Inf. für Ing. u. Naturwiss.) |
| Publikationstyp | Forschungsbericht/Preprint |
| Publikationsjahr | 2000 |
| Sprache | Englisch |
| Identifikator | ISSN: 1432-7864 urn:nbn:de:swb:90-AAA14520006 KITopen-ID: 1452000 |
| Verlag | Universität Karlsruhe (TH) |
| Umfang | 13 S. |
| Serie | Interner Bericht. Universität Karlsruhe, Fakultät für Informatik ; 15 |