[Todos] CURSO: Quantum Finite Automata: A Modern Introduction

[Irene Loiseau]

En el marco de la ECI 2015 (Escuela de Ciencias Informáticas) que se 
llevará a cabo en el Depto. de Computación de la FCEN-UBA del 20 al 25 
de Julio de 2015
se dictará el siguiente curso:

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.


------------------------------------------------
Mas detalles en http://www.dc.uba.ar/eci

La inscripción a los cursos de  la ECI 2015 se realizará del 8 de junio 
al 17 de julio.

Consultas a eci2015 en dc.uba.ar

-- 
Irene Loiseau
Departamento de Computación
Facultad de Ciencias Exactas y Naturales
Universidad de Buenos Aires