News

Planning for the rest of the semester

Written on 11.07.23 (last change on 11.07.23) by Markus Bläser

There is no tutorial on Wednesday, July 12.

There is no lecture on Friday, July 14.

The last lecture is on Tuesday, July 18.

The last tutorial is on Wednesday, July 19

Lecture July 7 was cancelled ...

Written on 07.07.23 by Markus Bläser

... due to lack of participants. See you on Tuesday!

No lecture on Friday May 19

Written on 17.05.23 by Markus Bläser

There will be no lecture Friday May 19. The next lecture will be Tuesday May 23.

Eurographics

Written on 08.05.23 by Markus Bläser

Due to Eurographics being held in Saarbrücken:

The lecture on Tuesday will be in E2.5 SR3 (U 11).
https://www.uni-saarland.de/standort/saarbruecken/lageplan/gebaeude/e25.html
This lecture will not be recorded, unfortunately.

The tutorial on Wednesday will be in the regular room (E1.3,… Read more

Due to Eurographics being held in Saarbrücken:

The lecture on Tuesday will be in E2.5 SR3 (U 11).
https://www.uni-saarland.de/standort/saarbruecken/lageplan/gebaeude/e25.html
This lecture will not be recorded, unfortunately.

The tutorial on Wednesday will be in the regular room (E1.3, HS003)

The lecture on Friday will be in the regular room (E1.3, HS001)

 

Team grouping

Written on 25.04.23 by Markus Bläser

is open until Friday, Apr 28, in the evening...

Room for tutorial changed!

Written on 25.04.23 by Markus Bläser

The room for the tutorial is HS003 in E1.3, not HS001! I am sorry for the confusion!

Show all

Quantum Complexity

The computer that we use today, like Turing machines, are based on classical physics. Operations are limited by locality, that is, all effects are local, and can be only in one state at the time.  Quantum systems behave differently.  They can be in a superposition of many different states at the same time and can exhibit interference effects.

In 1994, Peter Shor invented a polynomial time quantum algorithm that factors integers. This probably violates the invariance thesis by Cees F. Slot and Peter van Emde Boas (an efficient variant of the Church-Turing thesis), which states that "'Reasonable' machines can simulate each other within a polynomially bounded overhead in time and a constant-factor overhead in space." This means that either quantum computers are not 'reasonable' or that something interesting is going on.

We will study these problems from the perspective of theoretical computer science: Quantum bits will be vectors living on the unit sphere and quantum operations will be unitary maps.

 

Time and Date:

  • Tuesday, 14:15 - 16:00, E1.3 HS001
  • Friday, 14:15 - 16:00, E1.3 HS001
  • First lecture: Friday, April 14
     

Tutorials:

  • Tutorial: Wednesday, 14:15 to 16:00, E1.3 HS003 (exception on May 3: HS002)

 

Assignments:

There will be weekly assignments. To be admitted to the exam, you have to achieve half the points in the assignments. You can submit assignments in groups of up to three persons.

 

Exams:

There will be oral exams at the end of the semester.

 

Prerequisites:

  • "Grundzüge der Theoretischen Informatik" or equivalent (Introduction to computability and the theory of NP-completeness) is highly recommended.
  • Good knowledge of linear algebra is mandatory. We will introduce tensor products, though.
  • We do not assume that you attended the "Complexity Theory" core lecture, but it might be helpful.

 

Literature:

Here is a selection of references:

 

Privacy Policy | Legal Notice
If you encounter technical problems, please contact the administrators.