# 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.

### How to apply

If you want to specialize in quantum computing, and if you haven't done that already, contact us about:

- The possibility of additional scholarship (only for QC, in addition to the ones listed here — requires an interview (skype));
- The possibility of getting your application fee reimbursed.

Contact: `graduatestudies<at>theory.cs.ut.ee`

*(Some arrows omitted to avoid Spaghetti.)*

### Application process

**From within Estonia:** https://www.ut.ee/et/sisseastumine/mag/oppekavad/informaatika

**From outside of Estonia**

- Go to estonia.dreamapply.com/courses/course/362-msc-computer-science.
- Click on "Apply Now" and then on "Become an Applicant"
- Write down you applicant access code!
- Enter your data.
- Upload scanned copies of your documents (transcripts, diplomas, etc, as described in the text).
- Write a Motivation Letter. It is
**very important not to copy-paste**any part of the motivation letter: it is electronically checked against internet sources, and automatically rejected if even a small portion of it is copy-pasted from the internet. Better a crappy motivation letter than copy-pasting parts of it!!!! - In the motivation letter,
**say that you want to specialize in Quantum Computer Science**. In addition to that, you may also give the name of a professor who you would like to work with. Explain a little why you find quantum computing exciting (that should be easy to do, given the jaw-dropping progress that has been made on the hardware side over the last 12 months, and the promise of exponential speedup for many tasks in data analytics, machine learning, and many other fields (name some)). Don't worry too much about the motivation letter:**the important thing is that you do not copy anything from the internet into your motivation letter**. - Spell-check the motivation letter carefully!
- In the "Other" page, under the "Dora Plus Scholarship heading", click that you qualify and that you want to apply.
- The "Checklist" has only a subset of the things you need. Read the text for the other pages carefully.
- Once you're sure that everything is complete, click on "Submit".
- Complete the "remaining tasks" (among them is sending certified copies of documents by regular mail -- it's ok to do that a few days after March 15).

## 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), ...
- More quantum algorithms: HHL, Swap test, ...

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 software engineering [Theis]
- QASM, Q#; other quantum programming languages.
- Quantum computer software architectures, compilers, embedded domain-specific languages; Microsoft Visual Studio Quantum Development Kit, QISKit.
- Specific challenges of near-term gate based devices (mapping, optimizing, ...)
- Group project.

- 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**