Quantum Computing (5314QUCO6Y)

University of Amsterdam course, Spring 2013 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.

Prerequisites:

Familiarity with basic linear algebra, probability theory, discrete math, algorithms and complexity theory

Material:

Ronald's lecture notes.
An updated version prepared after the end of the course with some clarifications (note that the numbering of exercises has changed).

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:

7 weeks, 2+4 hours per week. Week 6-12: Mondays 11:00-13:00 in SP D1.110 and Thursdays 15:00-19:00 in SP G0.05. The last two hours on Thursday are for exercises and homework.

Homework, exam, and grading:

This is a 6 ECTS course, which comes to roughly 20 hours of work per week. There will be homework exercises once a week, to be handed in before or at the start of the Thursday 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 Giannicola (G.Scarpa 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 seven scores. The final grade is determined 40%-60% by the homework-grade and the final exam.

Course schedule:

  1. [Feb 4] Introduction to quantum mechanics and qubits, overview of the course
    Chapter 1 of lecture notes
    Homework: Chapter 1, Exercises 1,2,3 (hand in Feb 7)
    The two-slit experiment
  2. [Feb 7] The circuit model, Deutsch-Jozsa algorithm
    Chapter 2 of lecture notes
    Homework: Chapter 2, Exercises 2,4,5,7,8 (hand in Feb 14)
  3. [Feb 11] Simon's algorithm
    Chapter 3 of lecture notes
    Homework: Chapter 3, Exercises 1,3 (hand in Feb 14)
  4. [Feb 14] Quantum Fourier transform
    Chapter 4 of lecture notes
    Homework: Chapter 4, Exercises 1,3,4 (hand in Feb 21)
  5. [Feb 18] Shor's algorithm
    Chapter 5 of lecture notes
    Homework: Chapter 5, Exercises 1,2,4 (hand in Feb 21)
  6. [Feb 21] Grover's algorithm
    Chapter 6 of lecture notes
    Homework: Chapter 6, Exercises 1,2,3,4 (hand in Feb 28)
    Grover search in action
  7. [Feb 25] Quantum random walk algorithms
    Chapter 7 of lecture notes
    Homework: Chapter 7, Exercises 1,2 (hand in Feb 28)
  8. [Feb 28] Quantum cryptography [taught by Giannicola Scarpa]
    Chapter 13 of lecture notes
    Homework: Chapter 13, Exercises 2,4 (hand in Mar 7)
  9. [March 4] Quantum query lower bounds
    Chapter 8 of lecture notes
    Homework: Chapter 8, Exercises 1,2,3,4 (hand in Mar 7)
  10. [March 7] Quantum complexity theory
    Chapter 9 of lecture notes
    Homework: Chapter 9, Exercises 1,2,3 (hand in Mar 14)
  11. [March 11] Quantum encodings, with a non-quantum application
    Chapter 10 of lecture notes
    Homework: Chapter 10, Exercises 2,3,4 (hand in Mar 14)
  12. [March 14] Quantum communication complexity
    Chapter 11 of lecture notes
    Homework: Chapter 11, Exercises 1,2,4 (hand in Mar 21)
  13. [March 18] Entanglement and non-locality
    Chapter 12 of lecture notes
    Homework: Chapter 12, Exercises 1,2,3 (hand in Mar 21)
  14. [March 21] Error-correction and fault-tolerance
    Chapter 14 of lecture notes
    No homework, but probably one exam-question will be about quantum error-correction

    [March 28] 13:00-16:00, final exam in SP G2.10. The exam is "open book", meaning you can bring any kind of paper you want but no electronic devices.
Last update of this page: March 28, 2013.