Quantum Information and Computation (Summer 2022)

Programs: MSc {ITS, AI, Math, Physics}, CASA PhD Lectures
Lecturer: Michael Walter
Time and Place: Tue 14-16 (Lecture, GD 03/150), Thu 14-16 (Exercises, GABF 05/608)
First meeting: Tue April 5
Credits: 5 CP
Contact time: 2+2 SWS
Language: German or English (depending on audience)
Further Information and Registration: Moodle, VVZ

See here for the latest edition of this course.

Interested in this Course?

  1. If you plan on participating in this course, please kindly sign up on Moodle so that we have an overview of how many people will show up.
  2. Please contact Michael Walter if you have any questions about this course, scheduling conflicts, etc.

Course Description & Tentative Syllabus

This course will give an introduction to quantum information and quantum computation from the perspective of theoretical computer science. We will discuss the mathematical model of quantum bits and circuits, how to generalize computer science concepts to the quantum setting, how to design and analyze quantum algorithms and protocols for a variety of computational problems, and how to prove complexity theoretic lower bounds.

Topics to be covered will likely include:

  • Fundamental axioms of quantum mechanics: from classical to quantum bits
  • Few-qubit protocols: teleportation and no-cloning
  • The power of entanglement: Bell inequalities and CHSH game
  • Quantum circuit model of computation
  • Basic quantum algorithms: Deutsch-Jozsa, Bernstein-Vazirani, Simon
  • Grover’s search algorithm and beyond
  • Quantum Fourier transform and phase estimation
  • Shor’s factoring algorithm
  • Quantum query lower bounds
  • Quantum complexity theory
  • Quantum probability: mixed states, POVM measurements, quantum channels
  • Quantum entropy and Holevo bound
  • Quantum error correction
  • Quantum cryptography
  • Quantum “supremacy”

This course should be of interest to students of computer science, mathematics, physics, and related disciplines (including those who previously followed the Bachelor’s course Quantenalgorithmen by Prof. May). Students interested in a Master’s thesis in quantum information / computing / cryptography / … are particularly encouraged to participate.

If you are participating in this course you might also be interested in our seminar.

Familiarity with linear algebra (in finite dimensions) and probability (with finitely many outcomes) at the level of a first Bachelor’s course; we will briefly remind you of the more difficult bits in class. In addition, some mathematical maturity, since we will discuss precise mathematical statements and rigorous proofs. No background in physics is required!

Literature

  • Handwritten lecture notes (and video recordings of the lectures) will be provided

In addition, the following references can be useful for supplementary reading (the first two in particular served as inspiration for this course):

  • O’Donnell, Quantum Computation and Quantum Information, course material (2018)
  • de Wolf, Quantum Computing: Lecture Notes, arxiv:1907.09415 (2022)
  • Nielsen and Chuang, Quantum Computation and Quantum Information, Cambridge University Press (2010)
  • Mermin, Quantum Computer Science, Cambridge University Press (2007)

Learning outcomes

You will learn fundamental concepts, algorithms, and results in quantum information and computation theory. After successful completion of this course, you will know the mathematical model of quantum information and computation, how to generalize theoretical computer science concepts to the quantum setting, how to design and analyze quantum algorithms and protocols for a variety of computational problems, and how to prove complexity theoretic lower bounds. You will be prepared for an advanced course or a research or thesis project in this area.

Grades and homework

To get credit for this course, you have to pass the final exam.