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 |