Home	Contact	Short CV	Publications	Activities	Students	Teaching	Links

	Serge Fehr	Cryptology Group

Quantum Computing (Fall 2023)

• Lecturer: Serge Fehr (serge.fehr@cwi.nl)
• Teaching Assistant: Yu-Hsuan Huang (yu-hsuan.huang@cwi.nl)

Time and Place

• The course takes place on Thursday afternoon from 13:15 to 15:00 in Snellius 402.

Course 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 it. In the first part of the course, the basic mathematical theory for describing "quantum information'' and studying its behavior is introduced. 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 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.

List of topics that are covered: quantum states, measurements, Bloch sphere, control operations, 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: Basic knowledge of linear algebra over the complex numbers, basic probability theory, and some basic group theory.

Lecture Notes

Note that the full document covers this course on "Quantum Computing" as well as another course on "Quantum Information Theory". Relevant for this course are Chapter 0 (Preliminaries) - actually, mainly 0.1, 0.2 and 0.5 - and Chapter 1 to 4, which will be made available below, part by part.

• Title page
• Table of content (subject to changes)
• Chapter 0 - Preliminaries
• Chapter 1 - The State Vector Formalism
• Chapter 2 - Multipartite Quantum Systems
• Chapter 3 - Foundations of Quantum Computing
• Chapter 4 - (More) Quantum Algorithms Based on the Fourier Transform

Exercise Sets and Schedule

• Exercise Set 1, due September 21. Here you find the solutions.
• Exercise Set 2, due October 5. Here you find the solutions.
• Exercise Set 3, due October 19. Here you find the solutions.
• Exercise Set 4, due November 9. Here you find the solutions.
• Exercise Set 5, due December 7. Here you find the solutions.

Homework Exercises

• There will be 4 or 5 sets of homework exercises; the exact schedule for these exercises will be announced during class as well as on the website here. The exercises will not be graded, but the rule is that sufficiently many of the exercises need to be solved sufficiently well in order to be admitted to the final exam. Working in small groups is allowed, but every student has to write - and not copy-paste! - his/her own individual answer sheet.
• The answer sheet has to be handed in electronically by e-mail to the TA in pdf format, either typeset (e.g. using LaTeX) or neatly hand-written and scanned/photographed. Also, please format the file name as QC_PS[#problem set]_[FirstLastNames]_[student id].pdf. Model solutions to the exercises will be made available.

Examination and Grade

• The final examination will be in the form of an oral exam, which will take place January 8 or 9. The precise schedule has been announced by email. If you think you are eligible for the exam but have not been informed by email about your precise time slot, then please reach out to the lecturer immediately.
• Please be aware that according to (new) regulations, students need to be registered for the course in order to be admitted to the exam, and the (then automatically generated) registration for the exam must be confirmed by the student. Otherwise, the grade will not be processed and will not appear in uSis.

Consultation

• The lecturer is available for questions on Thursday mornings (10:00 h to 12:00 h, room 230) on a walk-in basis, and of course during the break and right after the lecture. Otherwise, he can be reached by email.
• For technical questions regarding the exercises, please email the teaching assistant.

CWI DISCLAIMER