Seminário de Computação e Informação Quântica 

06/03/2009, 15:00 — 16:00 — Sala P4.35, Pavilhão de Matemática
Daowen Qiu, SQIG-IT

Decidability of equivalence between quantum finite automata and some pending questions

Quantum finite automata (QFAs) are the simplest quantum computing models with finite memory, as finite automata in classical theory of computation. Indeed, QFAs also have close connection to classical finite automata, such as group finite automata. Decidability of equivalence between computing models is of importance, and it has been investigated for probabilistic automata since 1970's. In this talk, we recall related progress concerning QFAs, and in particular, we report some of our results achieved concerning QFAs. We mainly introduce the results of how to decide the equivalence between one-way measure-once QFAs, between one-way measure-many QFAs, and between multi-letter QFAs. Also, we address some existing problems to be solved. In light of these results we might see some essential differences between classical and quantum computing to some extent. In addition, there are still many basic problems to be solved in QFAs.