Quantum Computing (UvA course code 5334QUCO8Y)

University of Amsterdam and Mastermath course, Spring 2018 semester

Lecturer: Ronald de Wolf (CWI and ILLC)
Teaching assistants: Andras Gilyen and Joran van Apeldoorn (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 mathematical and theoretical computer science perspective, but should be accessible for physicists as well.

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.

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:

February 5 - May 14 2018. Every Monday 14:00-16:45, at Amsterdam Science Park. First 8 weeks in SP F1.02, last 6 weeks in SP A1.04.
Each Monday block consists of 2 hours of lectures followed by an exercise session.

Homework:

This is an 8 ECTS course over 14 weeks, plus a final exam, which comes to roughly 13 hours of work per week. There will be homework exercises for each lecture, to be handed in before the start of the next lecture, i.e., next Monday 14:00, in person or by email to Andras Gilyen: gilyen at cwi dot nl, with cc to rdewolf at cwi dot nl (please start the email subject with [QCHW]). This is a hard deadline: if you arrive late for the lecture you cannot hand in homework anymore, similarly if you send it by an email that arrives after 14:00. If you have questions about the homework exercises or the lectures, email Ronald. The answers should be in English. Handwritten solutions or emailed scans thereof are fine, as long as they are clearly readable. If you're emailing your solutions, please send a (moderately-sized) pdf, not separate images; the contrast should be sufficient so that it's still readable after printing ("CamScanner" is a decent app for this). Cooperation among students is allowed, but everyone has to hand in their own solution set in their own words. To get some idea of the level of detail required for your homework solutions, you can have a look at the solutions to the 2015 and 2017 exams, near the bottom of this page. Do NOT post the homework questions and/or anwers online. If you use LaTeX and want to draw circuits, you could consider using qcircuit or qasm2circ, which is the package used for the Nielsen-Chuang book.

Exam and grading:

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 exam (June 4) 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. Your grade for the exam should be at least 5.0 in order to pass the course. There's the possibility for a re-sit on July 2. The final grade is determined 40% by the homework-grade and 60% by the final exam. In accordance with the Mastermath rules, the final grade will be rounded to the nearest integer (also for Master of Logic students).

Preliminary course schedule:

  1. Monday February 5, 14:00-16:45
    Introduction to quantum mechanics and qubits, overview of the course
    Chapter 1 of lecture notes
    Homework: Exercises 1,5,6,8 of Chapter 1 (to be handed in by Monday Feb 12, before 14:00)

  2. Monday February 12, 14:00-16:45
    The circuit model, Deutsch-Jozsa algorithm
    Chapter 2 of lecture notes
    Homework: Exercises 2,3,8,10 of Chapter 2 (to be handed in by Monday Feb 19, before 14:00)

  3. Monday February 19, 14:00-16:45
    Simon's algorithm
    Chapter 3 of lecture notes
    Homework: Exercises 2,3,4 of Chapter 3 (to be handed in by Monday Feb 26, before 14:00)

  4. Monday February 26, 14:00-16:45
    Quantum Fourier transform
    Chapter 4 of lecture notes
    Homework: Exercises 3,4,5 of Chapter 4 (to be handed in by Monday March 5, before 14:00)

  5. Monday March 5, 14:00-16:45
    Shor's factoring algorithm
    Chapter 5 of lecture notes
    Homework: Exercises 1,2,3 of Chapter 5 (to be handed in by Monday March 12, before 14:00)

  6. Monday March 12, 14:00-16:45
    Grover's search algorithm
    Chapter 7 of lecture notes
    Homework: Exercises 1,4,7 of Chapter 7 (to be handed in by Monday March 19, before 14:00)
    Grover search in action

  7. Monday March 19, 14:00-16:45
    Quantum query lower bounds
    Chapter 9 of lecture notes
    Homework: Exercises 3,4,6,8 of Chapter 9 (to be handed in by Monday March 26, before 14:00)

  8. Monday March 26, 14:00-16:45
    Quantum complexity theory
    Chapter 10 of lecture notes
    Homework: Exercises 1,2,3 of Chapter 10 (to be handed in by Monday April 9, before 14:00)

    Monday April 2, no class (Easter Monday)

  9. Monday April 9, 14:00-16:45 NB: as of today we're in A1.04
    Quantum encodings, with a non-quantum application
    Chapter 11 of lecture notes
    Homework: Exercises 1,2,3,4 of Chapter 11 (to be handed in by Monday April 16, before 14:00)

  10. Monday April 16, 14:00-16:45
    Quantum communication complexity
    Chapter 12 of lecture notes
    Today we will also have a vote for the topics of the last 2 weeks. Possibilities: Hidden subgroup problem (Ch 6), Quantum walk algorithms (Ch 8), Entanglement and non-locality (Ch 13), Hamiltonian simulation and the HHL algorithm (chapter to be written), QMA and the local Hamiltonian problem (chapter to be written)
    Homework: Exercises 3,4,8,10 of Chapter 12 (to be handed in by Monday Apr 23, before 14:00)

  11. Monday April 23, 14:00-16:45
    Quantum cryptography
    Chapter 14 of lecture notes
    Homework: Exercises 1,2,3,4 of Chapter 14 (to be handed in by Monday April 30, before 14:00)

  12. Monday April 30, 14:00-16:45
    Error-correction and fault-tolerance
    Chapter 15 of lecture notes
    Homework: Exercises 3,5,6,7 of Chapter 15 (to be handed in Monday May 7, before 14:00)

  13. Monday May 7, 14:00-16:45
    First elective topic: Hidden Subgroup Problem
    Chapter 6 of lecture notes
    NB: if you're not familiar with basic group theory and representation theory, then I recommend you read the first parts of Chapter 6 before the lecture.
    Homework: Exercises 2,3,5 of Chapter 6 (to be handed in Monday May 14, before 14:00)

  14. Monday May 14, 14:00-16:45
    Second elective topic: Entanglement and Non-locality
    Chapter 13 of lecture notes
    No homework for this lecture, but you're likely to get an exam-question about it.


  15. Monday June 4, 14:00-17:00
    Final exam (open book: all paper is allowed, no electronics)
    Location REC A1.02 (this is on UvA Roeterseilandcampus, Nieuwe Achtergracht 166; not Science Park)
    If you want to practice, here are the exams from 2015 and 2017, with solutions.
    Update June 5: here is the 2018 exam, with solutions.

  16. Monday July 2, 14:00-17:00
    Re-sit of the exam (open book: all paper is allowed, no electronics)
    Location SP B0.208
    If you want to take the resit: let Ronald know by email, at least one day in advance. If you take the resit, the earlier exam-grade will be nullified and replaced by the resit-grade. Be aware that this could actually worsen your grade, or even make you fail the course if your resit-grade is <5.0.
Last update of this page: June 5, 2018