Contents/conteúdo

Mathematics Department Técnico Técnico

Quantum Computation and Information Seminar  RSS

Sessions

06/03/2009, 15:00 — 16:00 — Room P4.35, Mathematics Building
, 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.

Supported by: Phys-Info (IT), SQIG (IT), CeFEMA and CAMGSD, with funding from FCT, FEDER and EU FP7, specifically through the Doctoral Programme in the Physics and Mathematics of Information (DP-PMI), FCT strategic projects PEst-OE/EEI/LA0008/2013 and UID/EEA/50008/2013, IT project QuSim, project CRUP-CPU CQVibes, the FP7 Coordination Action QUTE-EUROPE (600788), and the FP7 projects Landauer (GA 318287) and PAPETS (323901).

 

Instituto de TelecomunicaçõesCAMGSDFCT7th Framework Programme