Algorithms for Quantum Computing

Seminar in Winter Term 2020/21

Description

Quantum computing is one of the hot trends in computer science, that uses quantum phenomena such as superposition or quantum entanglement to perform computations. Quantum computers use the power of quantum bits or qubits, which can be in more states than the two (binary) states offered by classical computers. This results in strong parallelism, thus quantum computers are believed to be able to quickly solve certain problems that no classical computer could solve in any feasible amount of time.

In this course we will cover algorithms that run on a realistic model of quantum computing.

For introduction, have a look at Google's video on demonstrating quantum supremacy, and read Prof. Scott Aaronson's response to it.

Requirements

We are looking for enthusiastic students who have an interest in quantum algorithms. The papers to be covered are sometimes technical and require basic knowledge of graph theory and complexity theory. The intended audience are Master students, and advanced Bachelor students, of TM (Technomathematik), CS (Computer Science), DS (Data Science), CSE (CS in Engineering).

The amount of ECTS you can acquire for this course depends on your degree program. Please inform us before the start of the course if you want your participation to be graded or ungraded.

Tasks

The seminar will cover a number of topics from the area of quantum algorithms. Each topic will be covered by one student, who will summarise a recent result in a 30-minute presentation and a written report of 5-10 pages.

Setup

The dates of the seminar are to be determined later. There is a maximum number of 10 participants.

Topics

The topics will be assigned to students by taking into account their preferences:

  1. Dynamical Systems Theory and Algorithms for NP-hard Problems
  2. Quantum Speedups for Exponential-Time Dynamic Programming Algorithms
  3. Quantum Speedup for the Minimum Steiner Tree Problem
  4. Clifford algebras meet tree decompositions
  5. Permutation-Based Combinatorial Optimization