Department of Computer Science AGH and IBM Software Laboratory in Krakow invite to Krakow Quantum Informatics Seminar (KQIS)
•    understand and discuss current problems in quantum informatics,
•    discuss new quantum computing technologies,
•    exchange ideas and research results,
•    integrate information across different research teams,
•    build a community around quantum informatics.
Venue:  via Internet, Webex

Tuesday, 13th of October, 2020, 9:30-11:00

Marcin Kuta - Department of Computer Science, Faculty of Computer Science, Electronics and Telecommunications AGH University of Science and Technology

Topic: 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 [1].

This talk will present different types of Quantum Finite Automata, their modes of work, relations between them and hierarchy of languages they generate [2]. Next, the talk will present a library [3] 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.


[1] 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)

[2] Lippa, G., Makieła, K., Kuta, M.: Simulations of quantum finite automata. In: International Conference on Computational Science, ICCS 2020,  Amsterdam, The Netherlands (2020)

[3] Lippa, G., Makieła, K., Simulator of quantum finite automata (in Polish), Bachelor Thesis, AGH University of Science and Technology, Kraków, Poland (2020)

  • 3 weeks, 4 days ago