| Date | Topic | Supplements | |
|---|---|---|---|
| Mon | Jan 8 | intro to query complexity: notes | sec. 1, 3 of survey |
| Wed | Jan 10 | intro to query complexity | sec. 2, 3 of Assadi notes, sec. 3.3 of survey |
| Fri | Jan 12 | Homework 1 posted: pdf | |
| Mon | Jan 15 | Grover's algorithm: notes | |
| Wed | Jan 17 | No class: inclement weather | |
| Mon | Jan 22 | basic design principles: notes | see references in notes |
| Wed | Jan 24 | time and query complexity: notes | see references in notes |
| Mon | Jan 29 | kSAT and SETH; collision | classical-to-quantum circuit conversion, Beame notes |
| Wed | Jan 31 | directed-STCON in hypercube | paper |
| Mon | Feb 5 | Simon's problem: quantum upper bound | exploring Simon's algorithm with Daniel Simon |
| Wed | Feb 7 | Simon's problem: classical lower bound: notes | de Wolf notes |
| Mon | Feb 12 | period finding in Z: notes | sec. 3.3 of Jozsa notes, Shor's story |
| Mon | Feb 12 | Homework 2 posted: pdf | |
| Wed | Feb 14 | period finding in Z and factoring | sec. 3.3 of Jozsa notes, Shor's story |
| Mon | Feb 19 | No class: mid-term break | |
| Wed | Feb 21 | No class: mid-term break | |
| Mon | Feb 26 | factoring | sec. 3.3 of Jozsa notes, sec. 5.1 of Montanaro notes |
| Wed | Feb 28 | HSP: definitions, mixed quantum states | ch. 10 of [AMC] |
| Mon | Mar 4 | HSP: query complexity | ch. 10 of [AMC] |
| Wed | Mar 6 | HSP: query complexity; dihedral HSP | ch. 10, 13 of [AMC] |
| Mon | Mar 11 | dihedral HSP; element distinctness (ED) | ch. 13, ch. 19.1 of [AMC] |
| Wed | Mar 13 | amplitude amplification on ED; quantum walk | ch. 19.1, ch. 17.1-17.2 of [AMC] |
| Mon | Mar 18 | quantum walk | ch. 17.3 of [AMC] |
| Wed | Mar 20 | quantum walk, quantum phase estimation | ch. 17.4 of [AMC], sec. 6 of Montanaro notes |
| Mon | Mar 25 | quantum walk for OR and ED | ch. 18.1-18.2, ch. 19 of [AMC] |
| Mon | Mar 25 | Homework 3 posted: pdf | |
| Wed | Mar 27 | adversary method | ch. 22 of [AMC] |
| Mon | Apr 1 | No class: Easter Monday | |
| Wed | Apr 3 | adversary method; divide and conquer | ch. 22 of [AMC]; paper |
| Mon | Apr 8 | Hamiltonian simulation, block encoding, QSP | sec. 6 of Jozsa notes, ch. 27 of [AMC] |
| Wed | Apr 10 | QSP | ch. 27 of [AMC] |
| Mon | Apr 15 | Homework 4 posted: pdf | |
This is a graduate-level topics course in quantum computation but assumes no prior knowledge of quantum information. The main focus will be on quantum algorithms and introducing open research problems.
Tentative list of topics:
Prior knowledge of quantum information is not a prerequisite. The main prerequisites are linear algebra (e.g., MATH 223, MATH 307, or CPSC 302) and mathematical maturity (e.g., from taking a third-year math course). Some prior knowledge of probability, group theory, analysis of algorithms, discrete math, optimization, or quantum mechanics is helpful but could also be picked up during the course.
The primary reference for this course is a set of excellent lecture notes on quantum algorithms by Andrew Childs: [AMC].
|
|