Calendar

Abbreviations

BQP = bounded-error, quantum, polynomial time
BBBV = Bennett, Bernstein, Brassard, Vazirani
PH = polynomial hierarchy
QMA = quantum Merlin-Arthur
QIP = quantum interactive proof

LEC # TOPICS KEY DATES
1 Quantum basics  
2 More quantum basics  
3 Quantum circuits  
4 BQP and classical friends Problem set 1 out
5 Quantum algorithms: Deutsch-Jozsa  
6 Quantum algorithms: Simon's algorithm  
7 Shor's algorithm and the hidden subgroup problem  
8 Hidden subgroup problem and Grover's algorithm

Problem set 1 due

Problem set 2 out

9 Grover's algorithm and BBBV  
10 Quantum query complexity lower bounds  
11 More quantum query complexity  
12 Query complexity and the collision problem

Problem set 2 due

Problem set 3 out

13 The collision problem Project out
14 BQP vs. PH and QMA  
15 QMA  
16 QMA and variants  
17 QIP

Problem set 3 due

Project proposal due

18 PostBQP Problem set 4 out
19 Closed timelike curves  
20 BQP/qpoly  
21 Quantum communication complexity Problem set 4 due
22 More quantum communication complexity  
23 Classical simulation  
24 Grab bag  
25 Student project presentations  
26 Student project presentations (cont.) Project report due