Quantum Information and Computation (Winter 2022/23)

Programs: BSc {CS, ITS, Math, Physics}, MSc {ITS, AI, Math, Physics}
Lecturer: Michael Walter
TAs: Cedric Brügmann and Anurudh Peduri
Time and Place: Wed 10-12 (Lecture, MC 1.30+31), Wed 14-16 (Exercises, MC 1.30+31)
First meeting: Wed Oct 12
Credits: 5 CP
Contact time: 2+2 SWS
Language: English
Further Information and Registration: Moodle, VVZ

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. Already know quantum computing? If so, you might be rather interested in our MSc course on Quantum Cryptography!
  3. Please contact us 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 theoretical 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:

  • Fundamentals of quantum computing: from classical to quantum bits, quantum states and operations
  • The power of quantum entanglement: nonlocal games
  • Entanglement as a resource: superdense coding and teleportation
  • Quantum circuit model of computation
  • Quantum computing with oracles: Deutsch-Jozsa, Bernstein-Vazirani, Simon
  • Quantum Fourier transform and phase estimation
  • Shor’s factoring algorithm
  • Grover’s search algorithm and beyond: how to solve SAT on a quantum computer?
  • From no cloning to quantum money: a peek at quantum cryptography
  • A glimpse of some more advanced topic, e.g. quantum complexity theory, quantum probability, quantum communication, error correcting codes, quantum supremacy, advanced quantum algorithms, more quantum cryptography, learning, lower bounds, …

This course should be of interest to students of computer science, mathematics, physics, and related disciplines. Students interested in a Bachelor’s or Master’s project in quantum information, computing, cryptography, etc are particularly encouraged to participate.

Familiarity with linear algebra, discrete probability, and theoretical computer science, each at the level of a first BSc course; we will briefly remind you of the more difficult bits in class. Some experience with precise mathematical statements and rigorous proofs (since we’ll see many of those in the course). No background in physics is required.

Literature

Lecture notes and video recordings of the lectures will be provided.

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

  • O’Donnell, Quantum Computation and Quantum Information, course material available online (2018)
  • de Wolf, Quantum Computing: Lecture Notes, available online (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. After successful completion of this course, you will know the theoretical model of quantum information and computation, 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. 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 (which will be written or oral, depending on the number of participants) and participate successfully in the exercises.