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 have been omitted for the sake of making it look nice. :)

(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).

Link to course page

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

Example Study Plans

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