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.
Grades and homework:
Your final grade will be determined 40% by homework and 60% by a final 3-hour exam on June 14 (with the possibility of a re-sit of the exam on July 5). 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, due before the start of the next lecture at 10am (these are hard deadlines). You can write down your solutions, scan them using an app like CamScanner, and upload them as one file on the ELO website via the "Homework" assignments I 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:
February 8 - May 17, 2021. Every Monday 10:00-12:45, online.
Each Monday block consists of 2x45 minutes of video lectures (from the 2019 edition of this course) and a live 45-minute exercise session every Monday at 11:00-11:45 on Zoom (see the link on the Mastermath page).
The video lectures are
here, with password yjD3.
Because the lecture notes have been updated in the last 2 years, the numbering of a few of the exercises (and even some of the later chapters) mentioned in the videos might be slightly out of date. The vimeo link also has recordings of a 3rd-hour exercise session for every week; these are not part of this year's course, though feel free to watch these too if you find them useful.
- Monday February 8, 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
Video Lecture 1 (1/3 and 2/3)
Exercise session via Zoom at 11am (the Zoom link is on the ELO website), where we did Exercises 1.3 and 1.6 from the lecture notes.
- Monday February 15, 10:00-12:45
The circuit model, Deutsch-Jozsa algorithm
Chapter 2 of lecture notes
Video Lecture 2 (1/3 and 2/3)
Exercise session via Zoom at 11am (the Zoom link is on the ELO website), where we did Exercises 2.5 and 2.11 from the lecture notes.
Homework set 1 due (upload in ELO before 10am): Exercises 2,5,9,11,13 from Chapter 1
- Monday February 22, 10:00-12:45
Simon's algorithm
Chapter 3 of lecture notes
Video Lecture 3 (1/3 and 2/3)
Exercise session via Zoom at 11am (the Zoom link is on the ELO website), where we did Exercises 3.2 and 3.5 from the lecture notes.
- Monday March 1, 10:00-12:45
Quantum Fourier transform
Chapter 4 of lecture notes
Video Lecture 4 (1/3 and 2/3)
Exercise session via Zoom at 11am (the Zoom link is on the ELO website), where we did Exercises 4.1 and 4.3 from the lecture notes.
Homework set 2 due (upload in ELO before 10am): Exercises 2,8,9 from Chapter 2 and Exercises 1,3,4 from Chapter 3
- Monday March 8, 10:00-12:45
Shor's factoring algorithm
Chapter 5 of lecture notes
Video Lecture 5 (1/4, 2/4 and 2/4)
Exercise session via Zoom at 11am (the Zoom link is on the ELO website), where we used Shor to factor N=20 (see "Selected exercises" file)
- Monday March 15, 10:00-12:45
Grover's search algorithm
Chapter 7 of lecture notes
Video Lecture 6 (1/3 and 2/3)
Exercise session via Zoom at 11am (the Zoom link is on the ELO website), where we did Ex 10 of Ch 7. You can see its solution as part of the exam of 2015 near the bottom of this page
Homework set 3 due (upload in ELO before 10am): Exercises 2,4,5 from Chapter 4 and Exercises 2,3 from Chapter 5
- Monday March 22, 10:00-12:45
Hamiltonian simulation
Chapter 9 of lecture notes (until Sec 9.3.1)
Video Lecture 7 (1/3 and 2/3)
Exercise session via Zoom at 11am (the Zoom link is on the ELO website), where we did Ex 4 of Ch 9. You can see its solution in the "selected exercises" file.
- Monday March 29, 10:00-12:45
The HHL algorithm
Remainder of Chapter 9, and Chapter 10 of lecture notes
Video Lecture 8 (1/3 and 2/3)
Exercise session via Zoom at 11am (the Zoom link is on the ELO website), where we did Ex 10 of Ch 9 (see the "selected exercises" file) and used HHL to solve a system ABx=b
Homework set 4 due (upload in ELO before 10am): Exercises 1,6,8,9 from Chapter 7 and Exercises 6,7 from Chapter 9
Monday April 5, no class (Easter Monday)
- Monday April 12, 10:00-12:45
Quantum query lower bounds
Chapter 11 of lecture notes
Exercise session via Zoom at 11am (the Zoom link is on the ELO website), where we did Ex 5 and 6 of Ch 11
Video Lecture 9 (1/3 and 2/3)
- Monday April 19, 10:00-12:45
Quantum complexity theory
Chapter 12 of lecture notes
Video Lecture 10 (1/4, 2/4 and 3/4)
Exercise session via Zoom at 11am (the Zoom link is on the ELO website), where we analyzed how bounded-error quantum algorithms can be used as subroutines inside other bounded-error quantum algorithms
Homework set 5 due (upload in ELO before 10am): Exercise 8 from Chapter 9, Exercise 1 from Chapter 10, and Exercises 3,7,9 from Chapter 11
- Monday April 26, 10:00-12:45
Quantum encodings, with a non-quantum application
Chapter 14 of lecture notes
Video Lecture 11 (1/3 and 2/3)
Exercise session via Zoom at 11am (the Zoom link is on the ELO website), where we did Ex 2 of Ch 14
- Monday May 3, 10:00-12:45
Quantum communication complexity
Chapter 15 of lecture notes
Video Lecture 12 (1/4, 2/4 and 3/4)
Exercise session via Zoom at 11am (the Zoom link is on the ELO website), where we did Ex 2 of Ch 15
Homework set 6 due (upload in ELO before 10am): Exercise 2,3 from Chapter 12, and Exercises 3,4,5 from Chapter 14
- Monday May 10, 10:00-12:45
Entanglement and non-locality
Chapter 16 of lecture notes
Video Lecture 14 (1/3 and 2/3)
Exercise session via Zoom at 11am (the Zoom link is on the ELO website), where we chose the topic of the final lecture and did Ex 3 of Ch 16
- Monday May 17, 10:00-12:45
Student's choice: Quantum cryptography
Chapter 17 of lecture notes
Video Lecture 13 (1/3 and 2/3)
Exercise session via Zoom at 11am (the Zoom link is on the ELO website), where we did Ex 5,6 of Ch 17
Homework set 7 due (upload in ELO before 10am): Exercise 4,5,7,11 from Chapter 15, and Exercises 5,6 from Chapter 16
There won't be homework about Chapter 17, but you can expect a related question on the exam
Monday May 24, no class (Pentecost)
- Monday June 14, 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
Here are the exams from 2015, 2017, 2018, 2019,
2020,
and 2021, with solutions.
- Monday July 5, 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 14, 2021