Description
It is well known that quantum computers (if/when they become available) will greatly outperform classical computers on certain computational problems. The most prominent example is Shor's quantum algorithm for factoring integers, which threatens most of the cryptography in use.
In this course, we give an introduction to quantum computing and to the mathematics behind. In the first part of the course, the basic mathematical theory for describing "quantum information" and studying its behavior is introduced, and some peculiar properties, like the no-cloning theorem and entanglement, are discussed. The second part briefly addresses the basic theory of quantum computation, like how to formalize what a quantum algorithm is and how to measure its complexity, but then the main goal is to introduce and rigorously analyze various quantum algorithms, and to understand (to some extent) their "common denominator". The algorithms discussed range from the early simple examples by Deutsch etc., but also include the more sophisticated algorithms that are relevant for the design of the next generation of cryptographic schemes, like Grover's and Shor's algorithm. On the way, it will be necessary to briefly look into representation theory of finite groups and into the theory of continued fractions.
Topics that are covered: quantum states, measurements, Bloch sphere, Naimark's Dilation Theorem, no-cloning, entanglement, quantum teleportation, quantum circuits, universal gate sets, example quantum algorithms (Deutsch, Deutsch-Jozsa, Bernstein-Vazirani, Simon), Grover search, quantum Fourier transform, period finding, hidden subgroup problem, Shor's algorithm.
Prerequisites
Prior knowledge of quantum mechanics is not necessary; familiarity with complex numbers and linear algebra is sufficient.
Course Material
Lecture notes will be handed out; no additional literature is necessary.
Examination
The examination will be in the form of an oral exam after the semester.