University of Amsterdam course, Spring 2011 semester
Lecturer: Ronald de Wolf (CWI and ILLC)
Teaching assistant: Giannicola Scarpa (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 computer science perspective but should be accessible for physicists as well.
Familiarity with basic linear algebra, probability theory, discrete math, algorithms and complexity theory
Ronald's lecture notes.
You can also consult the following three sets of slides from an earlier mini-course:
Those who want to read more (much more...) can consult the standard textbook in this area:
- Michael A. Nielsen and Isaac L. Chuang,
Quantum Computation and Quantum Information, Cambridge University Press, 2000.
Tuesdays 15:00-18:00, starting February 1, 2011
Location: week 5-11 in Science Park G2.13, week 13-20 in Science Park D1.162
Homework, exam, and grading:
This is a 6 ECTS course, which comes to roughly 10 hours of work per week.
There will be homework exercises every week, to be handed in before or at the start of the next lecture.
The answers should be in English.
You can hand it in on paper, or email a readable file to Giannicola (G.Scarpa at cwi dot nl, with cc to rdewolf at cwi dot nl).
Cooperation is allowed, but everyone has to hand in their own solution set in their own words.
If you use LaTeX and want to draw circuits, you can use
which is the package used for the Nielsen-Chuang book.
But handwritten solutions are fine too, as long as they are clearly readable.
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.
The final grade is determined by the average homework-grade (1/2 of the final grade), a midterm exam (1/4 of the final grade) and the final exam (1/4).
- [Feb 1] Introduction to quantum mechanics and qubits, overview of the course
Chapter 1 of lecture notes
- [Feb 8] The circuit model, Deutsch-Jozsa algorithm
Chapter 2 of lecture notes
- [Feb 15] Simon's algorithm
Chapter 3 of lecture notes
- [Feb 22] The (quantum) Fourier transform
Chapter 4 of lecture notes
- [Mar 1] Shor's algorithm
Chapter 5 of lecture notes
- [Mar 8] Grover's algorithm
Chapter 6 of lecture notes
Grover search in action
- [Mar 15] Quantum random walk algorithms
Chapter 7 of lecture notes
[Mar 21] 15:00-18:00, midterm exam in D1.116, about the first 7 weeks.
The midterm is "open book", meaning you can bring any kind of paper you want (but no electronic devices)
- [Mar 29] Quantum query lower bounds
Chapter 8 of lecture notes
- [Apr 5] Quantum complexity theory
Chapter 9 of lecture notes
- [Apr 12] Quantum encodings, with a non-quantum application
Chapter 10 of lecture notes
- [Apr 19] Quantum communication complexity
Chapter 11 of lecture notes
- [Apr 26] Entanglement and non-locality
Chapter 12 of lecture notes
- [May 3] Quantum cryptography
Chapter 13 of lecture notes
- [May 10] Error-correction and fault-tolerance
Chapter 14 of lecture notes
- [May 17] Summary of the course, some perspective, physical implementations
No lecture notes (but you could have a look at this paper by David DiVincenzo). No homework
[May 25] 16:00-19:00, final exam in A1.10 (NB: this is a Wednesday, not a Tuesday).
The exam is "open book", meaning you can bring any kind of paper you want (but no electronic devices).
There will be two versions: one covering the whole course and one covering only lectures 8-14.
The first option means your grade for the midterm won't be counted and the final determines half of your overall grade
(you can take this option if you didn't like your midterm grade).
In the second option the midterm and final each determine a quarter of your overall grade.
In both cases, the homework grade determines the other half of the overall grade.
Last update of this page: May 14, 2011.