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