The description below concerns the course given in 2001.
Click here for the 2002, 2003 and 2004 courses.

University of Amsterdam
Course: Quantum Computing
Harry Buhrman and Ronald de Wolf



Content

This course deals with the new field of quantum computation, which is computation based on quantum mechanical principles. The course is taught from a computer science perspective. It will explain the model of quantum computation, and will cover the main quantum algorithms and complexity results as well as some elements of quantum information theory.

Lectures and instruction

The lectures are held each Monday, 14:15-16:00 in P.014 (Plantage Muidergracht 24), and Friday, 15:15-17:00 in NP.401 (Nieuwe Achtergracht 170).
NB: Due to requests of some of the participants in the course, the Friday-lectures start an hour later than the study guide says.
Most of the Monday-lectures will be taught by Harry Buhrman, most of the Friday-lectures by Ronald de Wolf. The Friday-lectures are meant to work out and illustrate the Monday-lectures; some exercises will be made in class then. First lectures take place on September 11 (Monday) and 15 (Friday).

Credit

The course is valued at 7 credit points, which officially corresponds to 280 hours of work (roughly 20 hours per week). There will be a mid-term exam, covering the first 5 weeks, and a final exam. Those who pass the mid-term will only have to do the second half of the final exam, in which case the grade for the course will be the average of the grades for the mid-term and the final. Those who fail the mid-term will need to do the complete final exam.

Exams

All exams are of the "open book" type, meaning that you can bring the book, notes etc. to the exam.
Time and place of the mid-term: Friday October 27, 14:00-17:00, Room NP.401.
Time and place of the final exam: Thursday December 14, 13:30-16:30, Room C.206.
Time and place of the re-examination: Thursday February 22, 13:30-16:30, Room P.017.
There will not be a second plenary re-examination. Instead, every one is entitled to one individual oral examination in the period until August 2001. (Send e-mail to rdewolf@cwi.nl or buhrman@cwi.nl if you want to make an appointment.)

Textbook

The textbook for the course is: The book will appear September 2000 and can for instance be ordered from amazon.com. We will cover parts of this book and will probably hand out some additional material as well.

Course schedule and course material

  1. (11-9) Introduction (quantum mechanics, complexity theory, linear algebra).
    Friday's lecture notes and exercises (with one solution).
    Book: 1.1, 1.2, 1.3, 2.1, 2.2.1-5
  2. (18-9) Quantum gates, circuits, simple algorithms (Deutsch-Jozsa, Bernstein-Vazirani).
    Friday's exercises.
    Book: 1.4, 4.1, 4.2, 4.3, 4.4, 4.5
  3. (25-9) Simon's algorithm.
    Friday's exercises (with one solution).
    Book: none
  4. (2-10) Shor's algorithm for factoring and its application to breaking current cryptography like RSA.
    An introduction to Shor's algorithm.
    Rivest's survey of cryptography (including RSA) from the 1990 Handbook of Theoretical Computer Science.
    Book: 5.1, 5.2, 5.3, Appendix 5
  5. (9-10) Grover's search algorithm and its applications.
    Friday's exercises.
    Book: 6.1, 6.2, 6.3, 6.4, 6.5, 6.6
  6. (16-10) Lower bounds on quantum algorithms in the black-box model.
    The paper by Beals, Buhrman, Cleve, Mosca, de Wolf, Quantum lower bounds by polynomials, FOCS 1998.
    Friday's summary and exercises.
    Book: 6.7

    Friday, October 27, 14:00-17:00, Room NP.401: Mid-term exam for weeks 1-5 (no lectures this week)

  7. (30-10) Some quantum information theory (no-cloning, teleportation, dense coding, density matrices).
    On friday we discuss among others the mid-term exam.
    Book: 1.3.5-7, 2.3, 2.4
  8. (6-11) Quantum communication complexity.
    Harry Buhrman's survey paper on quantum communication complexity.
    Friday's lecture notes and exercises.
    Book: none
  9. (13-11) Quantum cryptography.
    NB: this week no lecture on Friday 17.
    Book: 12.6
  10. (20-11) Quantum error-correcting codes and fault-tolerant computing. Future prospects...
    Friday's exercises.
    Book: 10.1, 10.2, 10.3, 10.4, 10.6.1

    Thursday December 14, 13:30-16:30, Room C.206: Final exam.

Further reading

The following books contain most of the required background knowledge from complexity theory and linear algebra: Most research papers in quantum computing can be downloaded from the quantum physics section of the Los Alamos preprint archive. Similar courses have been/are being given by John Preskill and Umesh Vazirani.


Last update of this page: February 2, 2005.
Questions about the course? Send e-mail to rdewolf@cwi.nl or buhrman@cwi.nl.