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.
Prerequisites:
Familiarity with basic linear algebra, probability theory, discrete math, algorithms and complexity theory
Material:
Ronald's lecture notes.
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.
Lectures and location:
March 30 - May 22, 2015. Every Monday 15:00-18:45, every Friday 9:00-12:45 (except of course the many official holidays in this period). Various rooms in Science Park (see schedule below).
Homework, exam, and grading:
This is a 6 ECTS course, which comes to roughly 20 hours of work per week.
Each block consists of 2 hours of lectures followed by an exercise session.
There will be homework exercises for each lecture, to be handed in before or at the start of the Friday lecture.
The answers should be in English.
Cooperation is allowed, but everyone has to hand in their own solution set in their own words.
You can hand it in on paper, or email a readable file to Srinivasan (arunacha at cwi dot nl, with cc to rdewolf at cwi dot nl).
Handwritten solutions are fine, as long as they are clearly readable.
If you use LaTeX and want to draw circuits, you can use
qasm2circ,
which is the package used for the Nielsen-Chuang book.
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 the lowest of your six scores.
The final exam 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.
The final grade is determined 40% by the homework-grade and 60% by the final exam.
Course schedule:
- Monday March 30, 15:00-18:45, SP B0.203
Introduction to quantum mechanics and qubits, overview of the course
Chapter 1 of lecture notes
Homework: Exercises 2,3,4,6 of Chapter 1 (to be handed in Friday April 10, before 9:00)
For fun: the two-slit experiment
- Friday April 10, 9:00-12:45, SP A1.04
The circuit model, Deutsch-Jozsa algorithm
Chapter 2 of lecture notes
Homework: Exercises 2,3,4 of Chapter 2 (to be handed in Friday April 17, before 9:00)
- Monday April 13, 15:00-18:45, SP B0.203
Simon's algorithm, quantum Fourier transform
Chapter 3.1, 3.2 and 4.1, 4.4, 4.5 of lecture notes
Homework: Exercises 1,2 of Chapter 3, and 3,4 of Chapter 4 (to be handed in Friday April 17, before 9:00)
- Friday April 17, 9:00-12:45, SP A1.04
Shor's factoring algorithm
Chapter 5.1, 5.2, 5.3 of lecture notes
Homework: Exercises 2,3 of Chapter 5 (to be handed in Friday April 24, before 9:00)
- Monday April 20, 15:00-18:45, SP B0.203
Grover's search algorithm
Chapter 6 of lecture notes
Homework: Exercises 1,3,5 of Chapter 6 (to be handed in Friday April 24, before 9:00)
For fun: Grover search in action
- Friday April 24, 9:00-12:45, SP A1.04
Quantum query lower bounds
Chapter 8 of lecture notes
Homework: Exercises 4,5,6,7 of Chapter 8 (to be handed in Friday May 8, before 9:00)
- Friday May 1, 9:00-12:45, SP G0.05
Quantum complexity theory
Chapter 9 of lecture notes
Homework: Exercises 1,3 of Chapter 9 (to be handed in Friday May 8, before 9:00)
- Friday May 8, 9:00-12:45, SP A1.04
Quantum communication complexity
Chapter 11 of lecture notes
Homework: Exercises 1,3,5,6 of Chapter 11 (to be handed in Monday May 18, before 15:00)
- Monday May 11, 15:00-18:45, SP B0.203
Quantum cryptography
Section 10.1 and Chapter 13 of lecture notes
Homework: Exercises 1,2,4 of Chapter 13 (to be handed in Monday May 18, before 15:00)
- Monday May 18, 15:00-18:45, SP B0.203
Entanglement and non-locality
Chapter 12 of lecture notes
Homework: Exercises 1,3 of Chapter 10, and 1,2,3 of Chapter 12 (to be handed in Friday May 22, before 9:00)
- Friday May 22, 9:00-12:45, SP A1.04
Error-correction and fault-tolerance
Chapter 14 of lecture notes
No homework for this lecture, but you're likely to get an exam-question about it
Friday May 29, 9:00-12:00, final exam in SP F1.02. The exam is "open book", meaning you can bring any kind of paper you want but no electronic devices.
Here's a test exam from 2013.
Added June 1: Here's the exam from May 29, with solutions. If you'd like to know your grade quickly and/or take a look at your exam, email Ronald.
There will be a resit of the exam on Tuesday June 16, 11:00-14:00, room SP B0.204.
If you participate, your grade for the May 29 exam will be canceled and replaced by your grade for the resit (be careful that your final grade could actually go down because of this).
Last update of this page: June 12, 2015.