Lecturer: Ronald de Wolf (CWI and ILLC)

Teaching assistants: Andras Gilyen (CWI) and Joran van Apeldoorn (CWI)

Those who want to read more (much more...) can consult the standard textbook in this area:

Michael A. Nielsen and Isaac L. Chuang,

Each Monday block consists of 2 hours of lectures followed by an exercise session.

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 12) 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 (there's the possibility for a re-examination on July 3). 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).

- Monday February 6, 14:00-16:45

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 by Monday Feb 13, before 14:00)

- Monday February 13, 14:00-16:45

The circuit model, Deutsch-Jozsa algorithm

Chapter 2 of lecture notes

**Homework**: Exercises 2,4,5,7,11 of Chapter 2 (to be handed in by Monday Feb 20, before 14:00)

Exercise 7 is a bit tricky; the solution is given in the 2015 exam, near the bottom of this page

- Monday February 20, 14:00-16:45

Simon's algorithm

Chapter 3 of lecture notes

**Homework**: Exercises 1,2,3 of Chapter 3 (to be handed in by Monday Feb 27, before 14:00)

In Ex 2: for consistency with the notation of the chapter, you can assume the input is numbered (x_0,...,x_{N-1}) instead of (x_1,...,x_N)

There's a typo in 3.a: "n-qubit state" should be "N-qubit state" (sorry!)

- Monday February 27, 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 6, before 14:00)

- Monday March 6, 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 13, before 14:00)

- Monday March 13, 14:00-16:45

Grover's search algorithm

Chapter 6 of lecture notes

**Homework**: Exercises 2,4,5 of Chapter 6 (to be handed in by Monday March 20, before 14:00)

For fun: Grover search in action

- Monday March 20, 14:00-16:45

Quantum walk algorithms

Chapter 7 of lecture notes

To avoid the degenerate case delta=0, assume the graph on which the algorithm walks is not bipartite

**Homework**: Exercises 1,2,3 of Chapter 7 (to be handed in by Monday March 27, before 14:00)

NB: you can solve Ex 3 without actually using *quantum* walks; you may assume the number of clauses of the formula is at most some polynomial in n

- Monday March 27, 14:00-16:45
**(NB: as of today, we'll be in room G4.15)**

Quantum query lower bounds

Chapter 8 of lecture notes

**Homework**: Exercises 2,6,7,8 of Chapter 8 (to be handed in by Monday April 3, before 14:00)

- Friday April 3, 14:00-16:45

Quantum complexity theory

Chapter 9 of lecture notes

**Homework**: Exercises 1,2,3 of Chapter 9 (to be handed in by Monday April 10, before 14:00)

In Ex 2, "efficient" means using time that's at most polynomial in S.

Today we will also vote about the topic for the last lecture. Possible topics are: (1) Hidden Subgroup Problem, (2) Hamiltonian simulation and the HHL-algorithm for systems of linear equations, (3) QMA and the local Hamiltonian problem, (4) the general adversary bound. Winner: Hidden Subgroup Problem

- Monday April 10, 14:00-16:45

Quantum encodings, with a non-quantum application

Chapter 10 of lecture notes

**Homework**: Exercises 1,2,4 of Chapter 10 (to be handed in by Monday April 24, before 14:00)

Monday April 17, no class (Easter Monday)

- Monday April 24, 14:00-16:45

Quantum communication complexity

Chapter 11 of lecture notes

**Homework**: Exercises 3,6,8 of Chapter 11 (to be handed in by Monday May 1, before 14:00)

- Monday May 1, 14:00-16:45

Entanglement and non-locality

Chapter 12 of lecture notes

**Homework**: Exercises 2,3,4 of Chapter 12 (to be handed in by Monday May 8, before 14:00)

The 2nd part of the hint at 4d is wrong. Instead you can use:

for all Hermitian matrices D and E, and unit vector |\psi>, we have <\psi| D\otimes E |\psi> <= ||D\otimes E || = ||D||\cdot ||E||, where ||D|| denotes the operator norm of D.

- Monday May 8, 14:00-16:45

Quantum cryptography

Chapter 13 of lecture notes

**Homework**: Exercises 1,2,3,4 of Chapter 13 (to be handed in Monday May 15, before 14:00)

To clarify Ex 1.a: the first basis vector corresponds to outcome 0, the second basis vector to outcome 1. And 1.c: if two angles are possible (for instance because we treat -|-> and |-> as the same state), then take the one that's smallest in absolute value.

The online Quantum Cryptography course by Vidick and Wehner

Christian Schaffner is offering a MoL June project on quantum cryptography

- Monday May 15, 14:00-16:45

Error-correction and fault-tolerance

Chapter 14 of lecture notes

**Homework**: Exercises 3,5,6 of Chapter 14 (to be handed in Monday May 22, before 14:00)

- Monday May 22, 14:00-16:45

Hidden Subgroup Problem

Extra chapter of the lecture notes

NB: if you're not familiar with basic group theory, then I recommend you read the new chapter before the lecture.

No homework for this lecture, but you're likely to get an exam-question about it.

- Monday June 12, 14:00-17:00

Final exam (open book: all paper is allowed, no electronics)

IWO-Tentamenzalen (exam-rooms) 4.04B (Geel), Meibergdreef 29, 1105AZ Amsterdam-Zuidoost

If you want to practice, here's the exam from 2015, with solutions.

Update June 13: here's yesterday's exam, with solutions.

- Monday July 3, 14:00-17:00

Re-sit of the exam (open book: all paper is allowed, no electronics)

SP A1.10

If you want to take the resit: let Ronald know by email, at least one day in advance. If you take the resit, your final grade will be 40% homework-grade + 60% resit-grade (rounded to the nearest integer).

Last update of this page: June 13, 2017