Voraussichtlich im Sommersemester 2011 kann die Vorlesung wieder angeboten werden.
Survey
During the past two decades several completely new applications of quantum physics at the edge between computer science and the new area of quantum information theory have been discovered. These are based on the observation that certain genuine quantum properties of single or few quantum particles open the way to technologies not amenable to classical physics.
Certainly, one of the most exciting discoveries in this field has been the observation that there do exist algorithms based on ``quantum hardware'' which can solve certain algorithmic problems efficiently in contrast to traditional computers. Therefore, doubts have been cast on a fundamental thesis of theoretical informatics, the so-called Strong Church-Turing Thesis, which states that ``Any model of computation can be simulated on a probabilistic Turing machine with at most a polynomial increase in the number of elementary operations required'' (cited from the textbook ``Quantum Computation and Quantum Information'' by Nielsen and Chuang, p. 140) So, the model independence of computational complexity as claimed in this thesis appears not to be true and the expected speed-up in executing algorithms on quantum systems seems to falsify this thesis.
In this lecture an introduction into the field of quantum algorithms will be given. After a brief informal description of some physical effects which exhibit quantum properties the mathematical basis of the theory will be presented in a fairly elementary way. The state space of the systems considered here is a complex vector space with an inner product, a Hilbert-space, which can be assumed to be finite dimensional in the context of this lecture.
The Deutsch-Jozsa algorithm gives first useful insights into the field of quantum algorithms, because it can easily be understood and analyzed. Shor's algorithm for efficiently factorizing large integers is still the most prominent among many other algorithms, which have been found so far. This algorithm will be presented and analyzed in some detail with a careful separation into its quantum and classical parts (e.g. order-finding, Quantum Fourier Transform, continued fractions algorithm), which are also useful in other quantum algorithms. Some of these more recent algorithms can also be discussed depending on the time available.
Formulating algorithms requires some sort of notation. Pseudo-code and conventional mathematical notations are suitable for persons but, in general, not sufficiently concise for the use by automata (compiler). Therefore, quantum programming languages (QPLs) have been designed, which support the development of quantum algorithms and quantum programs. In combination with a classical simulator they can be used to run quantum programs on a conventional PC, although usually not efficiently. The lecture concludes with a brief survey on QPLs in general and a detailed discussion of a specific example.
The lecture does not require any prior knowledge of quantum physics.
The lecture will be given in German or in English.