News
17.05.2023

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

EurographicsDue to Eurographics being held in Saarbrücken: The lecture on Tuesday will be in E2.5 SR3 (U 11). The tutorial on Wednesday will be... Read more Due to Eurographics being held in Saarbrücken: The lecture on Tuesday will be in E2.5 SR3 (U 11). 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)

25.04.2023

Team groupingis open until Friday, Apr 28, in the evening... 
25.04.2023

Room for tutorial changed!The room for the tutorial is HS003 in E1.3, not HS001! I am sorry for the confusion! 
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 ChurchTuring thesis), which states that "'Reasonable' machines can simulate each other within a polynomially bounded overhead in time and a constantfactor 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 NPcompleteness) 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:
 Ronald de Wolf, Quantum Computing: Lecture Notes, arXiv:1907.09415
 Course notes by Scott Aaronson
 Course notes by Ryan O'Donnell

Michael A. Nielsen and Isaac L. Chuang, Quantum Computing and Information, Cambridge University Press