Zapraszamy na Krakow Quantum Informatics Seminar organizowane wspólnie przez Katedrę Informatyki AGH i IBM Software Lab Kraków. Spotkanie odbędzie się we wtorek 13.10.2020 w godzinach 9:30-11:00 via Internet, Webex https://ibm.webex.com/meet/tomasz.stopa
Marcin Kuta - Department of Computer Science, Faculty of Computer Science, Electronics and Telecommunications AGH University of Science and Technology
Temat: Quantum finite automata and their simulations
Finite automata are real models of computers, which have only limited amount of memory. They have been proposed more than sixty years ago. Since then they been quite well recognized and approached from various perspectives, including algebra and logics. The picture for the theory of quantum automata and languages generated by them is less clear, and various important problems remain open .
This talk will present different types of Quantum Finite Automata, their modes of work, relations between them and hierarchy of languages they generate . Next, the talk will present a library  to simulate different kinds of quantum finite automata on a classical computer and will show experiments measuring time complexity of the simulation. Examples of library usage will also be demonstrated. Finally, possible directions of development will be indicated.
 Qiu, D., Li, L., Mateus, P., Gruska, J.: Quantum finite automata. In: Wang, J. (ed.) Handbook of Finite State Based Models and Applications, pp. 113--144 (2012)
 Lippa, G., Makieła, K., Kuta, M.: Simulations of quantum finite automata. In: International Conference on Computational Science, ICCS 2020, Amsterdam, The Netherlands (2020)
 Lippa, G., Makieła, K., Simulator of quantum finite automata (in Polish), Bachelor Thesis, AGH University of Science and Technology, Kraków, Poland (2020)