Quantum Computing (UvA course code 5334QUCO8Y)

University of Amsterdam and Mastermath course, Spring 2020 semester

Lecturer: Ronald de Wolf (CWI and ILLC)
Teaching assistant: Philip Verduyn Lunel (CWI)

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.

This course will complement Maris Ozols and Michael Walter's course on Quantum Information Theory that's taught on Monday afternoon. Neither course requires the other, but students interested in writing a thesis in quantum computation/information are encouraged to follow both.

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.

Material:

Ronald's lecture notes.

Lectures and location:

February 3 - May 25, 2019. Every Monday 10:00-12:45, at Amsterdam Science Park, D1.111.
Each Monday block consists of 2 hours of lectures followed by a 1-hour exercise session.
Video recordings can be found on https://vimeo.com/showcase/6711192
password: yktT
Due to the corona virus, the later lectures will be from video recordings from 2019, see course schedule below.

Homework:

This is an 8 ECTS course over 14 weeks, plus a final exam, which comes to roughly 14 hours of work per week. There will be weekly or biweekly sets of homework exercises.

Exam and grading:

Each homework set will get a grade between 1 and 10; if you don't hand it in you'll score a 1 for that set. When determining the average grade for the homework, we will ignore your two lowest scores. This is also meant to cover cases of illness etc.; in general we won't allow extensions for homework submission.
The final exam (June 8) will be open book, meaning you can bring the lecture notes, your own notes, homework, and any other papers you want, but no electronic devices. Your grade for the exam should be at least 5.0 in order to pass the course. There's the possibility for a re-sit of the exam on June 29. The final grade is determined for 60% by the final exam (or the re-sit if you take it) and 40% by the homework-grade. In accordance with the Mastermath rules, the final grade will be rounded to the nearest integer, also for Master of Logic students.

Preliminary course schedule (updated because of the corona virus!):

We will start with 6 lectures about quantum algorithms, followed by 2 lectures about complexity theory and 3 lectures about distributed settings. Then 2 lectures about Hamiltonian simulation and the HHL algorithm. The topic of the last lecture will be decided by a student-vote midway through the semester.
  1. Monday February 3, 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 10, 10:00-12:45
    The circuit model, Deutsch-Jozsa algorithm
    Chapter 2 of lecture notes
    Homework set 1 due: Exercises 1,4,7,9,11 from Chapter 1

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

  4. Monday February 24, 10:00-12:45
    Quantum Fourier transform
    Chapter 4 of lecture notes
    Homework set 2 due: Exercises 3,5,8 from Chapter 2 and Exercises 1,3,4 from Chapter 3

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

  6. Monday March 9, 10:00-12:45
    Grover's search algorithm
    Chapter 7 of lecture notes
    Grover search in action
    Homework set 3 due: Exercises 1,3,4 from Chapter 4 and Exercises 2,3 from Chapter 5

  7. Monday March 16, 10:00-12:45. No physical lecture due to corona. Instead watch the video of lecture 9 from 2019 (password yjD3)
    Quantum query lower bounds
    Chapter 11 of lecture notes

  8. Monday March 23, 10:00-12:45. No physical lecture due to corona. Instead watch the video of lecture 10 from 2019 (password yjD3)
    Quantum complexity theory
    Chapter 12 of lecture notes
    Homework set 4 due via pdf-attachment to email: Exercises 3,4,7 from Chapter 7 and Exercises 3,7,9 from Chapter 11

  9. Monday March 30, 10:00-12:45. No physical lecture due to corona. Instead watch the video of lecture 11 from 2019 (password yjD3)
    Quantum encodings, with a non-quantum application
    Chapter 13 of lecture notes

  10. Monday April 6, 10:00-12:45. No physical lecture due to corona. Instead watch the video of lecture 12 from 2019 (password yjD3)
    Quantum communication complexity
    Chapter 14 of lecture notes
    Homework set 5 due via pdf-attachment to email: Exercises 2,3 from Chapter 12 and Exercises 1,2,4 from Chapter 13

    Monday April 13, no class (Easter Monday)

  11. Monday April 20, 10:00-12:45. No physical lecture due to corona. Instead watch the video of lecture 13 from 2019 (password yjD3)
    Quantum cryptography
    Chapter 16 of lecture notes

    Monday April 27, no class (King's Day)

    Monday May 4, no class (Commemoration of the dead)

  12. Monday May 11, 10:00-12:45. No physical lecture due to corona. Instead watch the video of lecture 7 from 2019 (password yjD3)
    Hamiltonian simulation
    Chapter 9 of lecture notes (until Sec 9.3.1)
    Homework set 6 due via pdf-attachment to email: Exercises 2,5,10 from Chapter 14 and Exercises 4,5,6 from Chapter 16

  13. Monday May 18, 10:00-12:45. No physical lecture due to corona. Instead watch the video of lecture 8 from 2019 (password yjD3)
    The HHL algorithm
    Remainder of Chapter 9, and Chapter 10 of lecture notes

  14. Monday May 25, 10:00-12:45. No physical lecture due to corona. Instead watch the video of lecture 14 from 2019 (password yjD3)
    Elective topic: Entanglement and non-locality
    Chapter 15 of lecture notes
    Homework set 7 due via pdf-attachment to email: Exercises 4,6,7,8 from Chapter 9 and Exercise 1 from Chapter 10
    Note: no homework corresponding to this last lecture about Ch 15, but there will probably be a related question on the exam


  15. Monday June 8, 10:00-13:00
    Final exam (open book: all paper is allowed, no electronics other than what is needed for downloading the questions & uploading your answers)
    Location: online
    If you want to practice, here are the exams from 2015, 2017, 2018, and 2019, with solutions.
    Here is the 2020 exam, with solutions.

  16. Monday June 29, 10:00-13:00
    Re-sit of the exam (open book: all paper is allowed, no electronics other than what is needed for downloading the questions & uploading your answers)
    Location: online
    If you want to take the re-sit: let Ronald know by email, at least one day in advance. If you take the re-sit, the earlier exam-grade will be nullified and replaced by the re-sit-grade. Be aware that this could actually worsen your grade, or even make you fail the course if your re-sit grade is <5.0. Your homework grade will still count for 40%.

Last update of this page: June 8, 2020