University of Amsterdam and Mastermath course, Spring 2019 semester
Lecturer: Ronald de Wolf (CWI and ILLC)
Teaching assistants: Joran van Apeldoorn in the first half of the course, Andras Gilyen in the second half (both are PhD students at 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 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.
NB: Make sure you have the latest version of the lecture notes, which has 17 chapters.
Lectures and location:
February 4 - May 27, 2019. Every Monday 10:00-12:45, at Amsterdam Science Park. First 7 weeks in room G2.10, thereafter in C1.112.
Each Monday block consists of 2 hours of lectures followed by an exercise session.
Mastermath records the lectures:
here's the link, with password yjD3
Homework:
This is an 8 ECTS course over 16 weeks, plus a final exam, which comes to roughly 13 hours of work per week.
There will be homework exercises for each lecture.
- The homework needs to be handed in before the start of the next lecture, i.e., the next Monday 10:00, in person or by email to homeworkquantumcomputing@gmail.com. This is a hard deadline: if you arrive late for the lecture, then you cannot hand in homework anymore, similarly if you send it by an email that arrives after 10:00.
- The answers should be in English. Handwritten solutions or emailed scans thereof are fine, as long as they are clearly readable. If you're emailing your solutions, please send a (moderately-sized) pdf attachment, not separate images (nor a url); the contrast should be sufficient so that it's still readable after printing ("CamScanner" is a decent app for this).
- Cooperation among students is allowed, but everyone has to hand in their own solution set in their own words. Do not share files before the homework deadline, and never put the solutions online. Plagiarism will not be tolerated.
- Note that Appendix C has hints for some of the exercises, indicated by (H). If the hint gives you some facts (for instance that there exists an efficient classical algorithm for testing if a given number is prime) then you can use these facts in your answer without proving/deriving these facts themselves.
- If you have questions about the homework or the lectures, email Ronald (rdewolf@cwi.nl).
- You can pick up your graded homework in subsequent lectures.
To get some idea of the level of detail required for your homework solutions, you can have a look at the solutions to the 2015, 2017, and 2018 exams, near the bottom of this page.
If you use LaTeX and want to draw circuits, you could consider using
qcircuit
or
qasm2circ,
which is the package used for the Nielsen-Chuang book.
Here are our notes with general feedback on the homework, incl. some model solutions. These notes will be updated every week, so check them regularly.
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 week. 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 24) 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 July 15.
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.
Course schedule:
- Monday February 4, 10:00-12:45 (room G2.10)
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
Homework: Exercises 1,5,6,8 of Chapter 1 (to be handed in by Monday Feb 11, 10:00)
- Monday February 11, 10:00-12:45
The circuit model, Deutsch-Jozsa algorithm
Chapter 2 of lecture notes
Homework: Exercises 4,5,8 of Chapter 2 (to be handed in by Monday Feb 18, before 10:00)
- Monday February 18, 10:00-12:45
Simon's algorithm
Chapter 3 of lecture notes
Homework: Exercises 2,3,4 of Chapter 3 (to be handed in by Monday Feb 25, before 10:00)
- Monday February 25, 10:00-12:45
Quantum Fourier transform
Chapter 4 of lecture notes
Homework: Exercises 1,3,4 of Chapter 4 (to be handed in by Monday March 4, before 10:00)
- Monday March 4, 10:00-12:45
Shor's factoring algorithm
Chapter 5 of lecture notes
Homework: Exercises 2,3 of Chapter 5 (to be handed in by Monday March 11, before 10:00)
- Monday March 11, 10:00-12:45
Grover's search algorithm
Chapter 7 of lecture notes
Homework: Exercises 1,3,7 of Chapter 7 (to be handed in by Monday March 18, before 10:00)
Grover search in action
- Monday March 18, 10:00-12:45
Hamiltonian simulation
Chapter 9 of lecture notes (until Sec 9.3.1)
Homework: Exercises 2,4,6 of Chapter 9 (to be handed in by Monday March 25, before 10:00)
- Monday March 25, 10:00-12:45 (NB: room switch to C1.112)
The HHL algorithm
Remainder of Chapter 9, and Chapter 10 of lecture notes
Homework: Exercises 7,8 of Chapter 9, and Exercise 1 of Chapter 10 (to be handed in by Monday April 1 before 10:00)
- Monday April 1, 10:00-12:45
Quantum query lower bounds
Chapter 11 of lecture notes
Homework: Exercises 3,5,7,8 of Chapter 11 (to be handed in by Monday April 8, before 10:00)
- Monday April 8, 10:00-12:45
Quantum complexity theory
Chapter 12 of lecture notes
Homework: Exercises 2,3 of Chapter 12 (to be handed in by Monday April 29, before 10:00)
Monday April 15, no class (canceled)
Monday April 22, no class (Easter Monday)
- Monday April 29, 10:00-12:45
Quantum encodings, with a non-quantum application
Chapter 13 of lecture notes
Homework: Exercises 1,2,4 of Chapter 13 (to be handed in by Monday May 6, before 10:00)
- Monday May 6, 10:00-12:45
Quantum communication complexity
Chapter 14 of lecture notes
Homework: Exercises 6,8,10 of Chapter 14 (to be handed in by Monday May 13, before 10:00)
- Monday May 13, 10:00-12:45
Quantum cryptography
Chapter 16 of lecture notes
Homework: Exercises 3,4,6,7 of Chapter 16 (to be handed in by Monday May 20, before 10:00)
If you want to learn more: here's an online Quantum Cryptography course by Thomas Vidick and Stephanie Wehner
- Monday May 20, 10:00-12:45
Elective topic 1: Entanglement and non-locality
Chapter 15 of lecture notes
Homework: Exercises 1,4,5 of Chapter 15 (to be handed in by Monday May 27, before 10:00)
- Monday May 27, 10:00-12:45
Elective topic 2: Error-correction and fault-tolerance
Chapter 17 of lecture notes
No homework for this week, but there will probably be a related question on the exam
- Monday June 24, 10:00-13:00
Final exam (open book: all paper is allowed, no electronics)
Location: REC C1.04 (Roeterseiland)
If you want to practice, here are the exams from 2015, 2017, and 2018, with solutions.
Here is the 2019 exam, with solutions.
- Monday July 15, 10:00-13:00
Re-sit of the exam (open book: all paper is allowed, no electronics)
Location: Science Park B0.207
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 24, 2019