CSclub: Лекции Абузер Якарйилмаз (Университет Латвии, Рига)

Написал(а): Антон Коврижных 3 года, 11 месяцев ago

22-24 ноября в рамках CSclub состоятся лекции по основам квантовых вычислений (на английском языке). Лектор - Абузер Якарйилмаз (Университет Латвии, Рига) - приглашен по Программе развития УрФУ, Мероприятие 3.1.

Аннотация лекций:

Day 1 (Lectures 1-2): Introduction
We begin with the basics of quantum computation: qubits, quantum states, amplitudes, unitary operators and measurement. Then, we introduce a very simple quantum finite automaton (QFA) model.
Based on this model, we present two simple quantum algorithms that allow us to save some memories. Then, we introduce a more general QFA model. Based on this model, we define the most general quantum operator "superoperators". Lastly, we give an upper bound for this model that they can recognize only regular languages with bounded error.

Day 2 (Lectures 3-4): Quantum finite automata
We continue with the examination of QFAs in more detail. We give another upper bound proof for general QFAs that they can recognize only nonstochastic languages with unbounded-error. Then, we show that nondeterministic QFAs can be more powerful than their classical counterparts. Lastly, we give some algorithms for two-way QFAs that gives some certain separation results.

Day 3 (Lectures 5-6): Quantum algorithms
We describe famous Grover's search algorithms and then a generic method called "Amplitude amplification" that allows us to obtain a quadratic speedup over several classical algorithms. Then, we present a technique to show a lower bound for quantum search problem.