Quantum Finite Automata: A Modern Introduction
Prof. Abuzer Yakaryilmaz. Laboratório Nacional de Computação Científica, Brasil.
Summary
The aim of the course is to give the basics of quantum computation and provide some insights about where the power of quantum computation comes from. In order to teach the basics, we start with possible the simplest computational model, an finite state automaton reading the input as a stream, and we focus on very simple machines having only 2-state (a quantum bit: qubit) on unary alphabets, the computation of which can be geometrically represented on the unit circle on real plane. Based on this model, we provide four different examples showing the superiority of quantum computation over the classical one. Then, we switch to two-way finite state machines that can read the input many times and we provide another simple polynomial time algorithm that solves a problem beyond the capability of the same type of classical machines. Based on this two-way models, we represent how more general quantum operators can be implemented which allow us to simulate any classical operator and forms a basis for further studies in quantum information. After that, we introduce quantum circuit model and present two well-known quantum algorithms: Grovers's search algorithm which brings us a quadratic speed-up and Shor's factoring algorithm which is exponentially faster than any of its known classical counterparts.
The first part of the lecture was previous given in Russia (twice), in Turkey, and recently in Colombia. The material was also published as a chapter:
Quantum finite automata: A modern introduction, A.C.C. Say, A, Yakaryilmaz. Computing with New Resources (Essays Dedicated to Jozef Gruska on the Occasion of His 80th Birthday), LNCS Vol. 8008, pp. 208-222, 2014. (http://arxiv.org/abs/1406.4048)
The second part can be found in any standard introductory textbook to quantum computation. I will also provide my own lecture notes.
Target groups
Computer scientist, mathematicians, and physicists.
- Rough schedule
- Lecture 1: A short review of deterministic finite automata, some basics of probabilistic computation, and basic quantum operators.
- Lecture 2: Four examples showing superiority of quantum finite automata (QFAs) over classical ones.
- Lecture 3: The power of two-way QFAs and advanced quantum operators.
- Lecture 4: Grover search algorithm.
- Lecture 5: Shor's factoring algorithm.
Attendance Examination
The Exam will be take place on Saturday 25th of July.
