Quantum Computing (UvA course code 5334QUCO8Y)

University of Amsterdam and Mastermath course, Spring 2022 semester

Lecturer: Ronald de Wolf (CWI and ILLC)
Teaching assistants: Yanlin Chen (CWI) and Galina Pass (UvA)

Registration is through the Mastermath website, not through your own university.

Contents of the course:

Today's computers---both in theory (Turing machines) and practice (PCs and smart phones)---are based on classical physics. However, modern quantum physics tells us that the world behaves quite differently. A quantum system can be in a superposition of many different states at the same time, and can exhibit interference effects during the course of its evolution. Moreover, spatially separated quantum systems may be entangled with each other and operations may have "non-local" effects because of this. Quantum computation is the field that investigates the computational power and other properties of computers based on quantum-mechanical principles. Its main building block is the qubit which, unlike classical bits, can take both values 0 and 1 at the same time, and hence affords a certain kind of parallelism. The laws of quantum mechanics constrain how we can perform computational operations on these qubits, and thus determine how efficiently we can solve a certain computational problem. Quantum computers generalize classical ones and hence are at least as efficient. However, the real aim is to find computational problems where a quantum computer is much more efficient than classical computers. For example, Peter Shor in 1994 found a quantum algorithm that can efficiently factor large integers into their prime factors. This problem is generally believed to take exponential time on even the best classical computers, and its assumed hardness forms the basis of much of modern cryptography (particularly the widespread RSA system). Shor's algorithm breaks all such cryptography. A second important quantum algorithm is Grover's search algorithm, which searches through an unordered search space quadratically faster than is possible classically. In addition to such algorithms, there is a plethora of other applications: quantum cryptography, quantum communication, simulation of physical systems, and many others.
The course is taught from a mathematical and theoretical computer science perspective, but should be accessible for physicists as well. This is a theory course, no programming is involved.

Prerequisites:

Familiarity with basic linear algebra, probability theory, discrete math, algorithms, all at the level of a first Bachelor's course. Also general mathematical maturity: knowing how to write down a proof properly and completely. Beware: The expected level of rigour and precision in homework and exam is a bit higher than what is typically expected in physics courses.

Material:

Ronald's lecture notes.
If you have trouble with the material, you could have a look at the first few chapters of Nielsen and Chuang's Quantum Computation and Quantum Information, which takes a slower pace.

Grades and homework:

Your final grade will be determined 40% by homework and 60% by a final 3-hour exam in June (with the possibility of a re-sit of the exam a few weeks late). It's a general rule of Mastermath courses that you need an exam grade of at least 5.0 and a final grade of at least 5.5 to pass the course. Also, the final grade will be rounded to the nearest integer.
There will be 7 homework sets. You can write down your solutions, scan them using an app like CamScanner, and upload them as one file on the ELO website before the deadline via the "Homework" assignments I will set up there. Your homework grade will be determined by the best 5 of your 7 homework grades, so no big problem if you mess up or skip 1 or 2 of the homeworks. This also covers cases where you might not be able to hand in a particular homework on time for whatever reason, so please don't ask me for extra time or special treatment regarding the homework.

Lectures and location:

Starting Feb 7: every Monday 10:00-12:45, Amsterdam Science Park room C0.110. Each Monday block consists of 2x45 minutes of oral lectures and a 45-minute exercise session. Teaching will be live on location when allowed (as it is now). A student-assistant will make video recordings of each lecture, which will be made available some time after the lecture. If covid hits again, or something else goes wrong, plan B will be to fall back on the recordings of the 2019 edition of the course. There won't be a live stream, and I would encourage people to attend in person as much as possible to interact with me and other students, ask questions during the lectures etc.

The videorecordings are at https://vimeo.com/showcase/9241142 with password 98rT
  1. Monday February 7, 10:00-12:45
    Introduction to quantum mechanics and qubits, overview of the course
    Chapter 1 of lecture notes. Also make sure you know the material in Appendices A and B

  2. Monday February 14, 10:00-12:45
    The circuit model, Deutsch-Jozsa algorithm
    Chapter 2 of lecture notes
    Homework set 1 due (upload in ELO before 9:55am): Exercises 2,4,5,7,12 from Chapter 1

  3. Monday February 21, 10:00-12:45
    Simon's algorithm
    Chapter 3 of lecture notes

  4. Monday February 28, 10:00-12:45
    Quantum Fourier transform
    Chapter 4 of lecture notes
    Homework set 2 due (upload in ELO before 9:55am): Exercises 3,6,9 from Chapter 2 and Ex 2,3,4 from Chapter 3

  5. Monday March 7, 10:00-12:45
    Shor's factoring algorithm
    Chapter 5 of lecture notes

  6. Monday March 14, 10:00-12:45
    Grover's search algorithm
    Chapter 7 of lecture notes
    Homework set 3 due (upload in ELO before 9:55am): Exercises 1,3,4 from Chapter 4 and Ex 1,2,3 from Chapter 5

  7. Monday March 21, 10:00-12:45
    Quantum walks
    Chapter 8 of lecture notes

  8. Monday March 28, 10:00-12:45
    Hamiltonian simulation
    Chapter 9.1-3 of lecture notes
    Homework set 4 due (upload in ELO before 9:55am): Exercises 1,4,7,10 from Chapter 7 and Ex 1,4 from Chapter 8

  9. Monday April 4, 10:00-12:45
    Finishing Hamiltonian simulation, and the HHL algorithm
    Chapter 9.4 and Chapter 10 of lecture notes

    Homework set 5 due on Sunday April 10 (upload in ELO before 11:59pm): Exercises 2,6,8,9 from Chapter 9 and Ex 1,3 from Chapter 10
  10. Monday April 11, 10:00-12:45
    Quantum query lower bounds
    Chapter 11 of lecture notes

    Monday April 18, no class (Easter Monday)

  11. Monday April 25, 10:00-12:45
    Quantum complexity theory
    Chapter 12 of lecture notes

    Homework set 6 due on Sunday May 1 (upload in ELO before 11:59pm): Exercises 3,5,7,9 from Chapter 11 and Ex 2,4 from Chapter 12
  12. Monday May 2, 10:00-12:45
    Quantum encodings, with a non-quantum application
    Chapter 14 of lecture notes

  13. Monday May 9, 10:00-12:45
    Quantum communication complexity
    Chapter 15 of lecture notes

  14. Monday May 16, 10:00-12:45
    Quantum cryptography
    Chapter 17 of lecture notes

    Homework set 7 due on Sunday May 22 (upload in ELO before 11:59pm): Exercises 2,7 from Chapter 14, Ex 2,5,11 from Chapter 15, and Ex 4,5 from Chapter 17
  15. Monday May 23, 10:00-12:45
    Quantum machine learning
    Newly written chapter


    Monday June 13, 10:00-13:00, final exam, REC A0.03 (Roeterseiland Amsterdam). Here is the exam, with solutions

    Monday July 4, 10:00-13:00, re-sit of exam, SP C1.110 (Science Park Amsterdam). Here is the re-sit exam, with solutions

    If you want to practise: here are the exams from 2015, 2017, 2018, 2019, 2020, and 2021, with solutions.
Last update of this page: July 4, 2022