# Theory @ Tartu

### Theoretical Computer Science

### University of Tartu

# Graduate Studies

In Europe, graduate studies consist of two parts: First you complete an MSc degree, then the PhD. If you don't change topics between MSc and PhD, you can complete all of it (MSc + PhD) in 5 years. Of course, leaving after the MSc is also possible, as is entering the PhD program if you already have a Master's.

## Graduate Study in Computer Science: Quantum Computing Focus

Short presentation on the goals of our quantum computing focus.

A longer, non-technical, presentation about quantum computing based on the example of Grover's unstructured search algorithm.

*(Some arrows omitted to avoid Spaghetti.)*

## Graduate Study in TCS: Courses

## I: First Year Master's — Fall Term

MTAT.03.286: Lecture course (6 ECTS)

### Design and Analysis of Algorithms

**Vitaly Skachek**

*Compulsory for all Computer Science master's students.*

- Minimum spanning tree, network flow algorithms, FFT, simplex algorithms for linear-programming problems, randomized algorithms, approximation algorithms (set cover, knapsack, TSP), rounding technique, primal-dual technique.

MTAT.05.008: Lecture course (6 ECTS)

### Mathematical Foundations of Computer Science

**Dirk Oliver Theis**

- Review of Linear Algebra: (finite) fields, vector spaces, bases, dimension, linear operators, matrices; Jordan normal form.
- Hilbert space (Dirac notation, orthonormal bases, spectral theory of commuting operators, Fourier transform, tensor product, trace), postulates of quantum mechanics, entanglement; no-cloning theorem (= Chapter 2 of Nielsen-Chuang).

## II: First Year Master's — Spring Term

MTAT.07.002: Lecture course (6 ECTS)

### Cryptology I

**Dominique Unruh**

MTAT.07.024: Lecture course (6 ECTS)

### Quantum Cryptography

**Dominique Unruh**

MTAT.05.018: Lecture course (6 ECTS)

### Quantum Computing

**Dirk Oliver Theis**

- Where we are: P ⊆ BPP ⊆ BQP ⊆ PP ⊆ PSPACE; NP ⊆ QMA.
- Quantum gates and circuits; uncompute; QRAM.
- Quantum algorithms: Deutsch-Jozsa, amplitude amplification (Grover), amplitude estimation, quantum Fourier transform, eigenvalue estimation, Simon, Schor (⟶factoring, discrete log), ...

LTAT.00.008: Project (6 ECTS = 3+3)

### Theoretical Informatics Project

**All TCS faculty (Dominique Unruh, Helger Lipmaa, Vitaly Skachek, Dirk Oliver Theis)**

Small project or 2 mini-projects. Can be split over 2 terms. Can be theoretical (=proving theorems) or practical (=writing code). Example areas:

- Quantum programming languages [Theis]
- Quantum crypto [Unruh]
- Crypto [Unruh, Lipmaa]
- Coding Theory [Skachek]

## III: Second Year Master's — Fall Term

MTAT.05.082: Lecture Course (6 ECTS)

### Introduction to Coding Theory

**Vitaly Skachek**

- Communication model, error correction and detection, parameters of the codes, examples of codes, connections to secret sharing and wiretap channel model, Reed-Solomon codes and their decoding.

LTAT.04.005: Project (12 ECTS)

### Research Project in Theoretical Informatics

**All TCS faculty (Dominique Unruh, Helger Lipmaa, Vitaly Skachek, Dirk Oliver Theis)**

Intensive research project in preparation for the Master's thesis. Can be theoretical (=proving theorems) or practical (=writing code).

Student discuss possible topics *directly* with the supervisor(s):

- Cryptography [Unruh, Lipmaa]
- Quantum crypto [Unruh]
- Quantum computing (theoretical) [Theis]
- Quantum software technology (practical) [Theis]
- Blockchain technology [Lipmaa, Skachek]
- Coding theory and information transmission [Skachek]

## Every Term

LTAT.04.004: Seminar (3 ECTS, can be taken 4 times)

### Quantum seminar

**Dominique Unruh, Dirk Oliver Theis**

Each student reads a paper, gives a presentation about it.

MTAT.07.022: Seminar (3 ECTS, can be taken twice)

### Crypto seminar

**Dominique Unruh, Helger Lipmaa, Vitaly Skachek**

## PhD-Level Courses

MTAT.05.123: Lecture Course (6 ECTS)

### Advanced Quantum Algorithms

Starting Fall 2019.

**Dirk Oliver Theis**

- HHL, variants, and applications.
- Quantum machine learning / data analytics algorithms.

MTAT.05.121: Reading course (6 ECTS, can be taken 4 times)

### Advanced Quantum Computer Science

Starting Spring 2019.

**Coordinator: Dirk Oliver Theis**

Advanced PhD-level reading courses on topics such as

- quantum compiler construction / circuit optimization
- quantum complexity theory
- quantum error correction
- quantum neural networks
- distributed quantum computing.

PhD students read, prepare, and present in detail(!!) the content of sequence of research papers. (Master's students just listen.)

MTAT.05.116: Seminar (3 ECTS, can be taken 4 times)

### Algorithms & Theory seminar

PhD-student seminar in quantum computing and related topics. Every semester.

**Dirk Oliver Theis**