News
Planning for the rest of the semesterWritten 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 19Written on 17.05.23 by Markus Bläser There will be no lecture Friday May 19. The next lecture will be Tuesday May 23. |
EurographicsWritten 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). 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). 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 groupingWritten 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! |
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