(Spring 2019) CS 440/640 - Quantum Algorithms

Schedule (subject to change)

Week Date Topic Reading & Note
1 M,01/14 Intro (by Dr. Klappenecker)
Review: linear algebra and probability
Read the intro slides PDF
Study materials on Piazza
HW1 out (see below)
due 01/28/2019
  W,01/16 QIP’19, class cancelled Suggested: Aaronson Lecture
watch videos by M. Nielsen
2 M,01/21 MLK day, no class  
  W,01/23 Qubit, unitary operation, measurement Watrous Lec1 PDF
KLM Chapter 1,3.1,3.2
3 M,01/28 tensor product, multiple qubits Watrous Lec2 PDF
KLM 3.3,3.4
HW1 due, HW2 out
  W,01/30 Reversible computation, quantum circuit Watrous Lec7 PDF
KLM 1.5,4
4 M,02/04 Partial measurement
Superdense coding
Watrous Lec3 PDF
KLM 5.1
  W,02/06 Teleportation
Deutsch’s algorithm
Guest Lecturer: Ben Hamlin
Watrous Lec4 PDF
KLM 5.2,6.3
5 M,02/11 Deutsch-Josza algorithms Watrous Lec5 PDF
KLM 6.4
  W,02/13 Simon’s Algorithm Watrous Lec6 PDF
KLM 6.5
6 M,02/18
Phase estimation
Watrous Lec8 PDF
Vazirani Lec12 PDF
  W,02/20 Phase estimation cont’d
quantum Fourier transform
Watrous Lec9 PDF
KLM 7.1
7 M,02/25 Order finding Watrous Lec10 PDF
KLM 7.3
  W,02/27 Quantum factorization algorithm Watrous Lec11 PDF
Vazirani Lec8 PDF
8 M,03/04 Grover’s algorithm Watrous Lec12 PDF
KLM 8.1
  W,03/06 Grover’s algorithm, cont’d Watrous Lec13 PDF
KLM 8.2
BBBV97
9 M,03/11 Spring Break  
  W,03/13 Spring Break  
10 M,03/18 Density operators, mixed states
general quantum operations
Watrous Lec14 PDF
KLM 3.5
  W,03/20 Take-home midterm  
11 M,03/25 Partial trace, POVM Watrous Lec15 PDF
KLM 3.5
  W,03/27 Entropy, Quantum compression
Holevo’s bound
Vazirani Lec13 PDF
Vazirani Lec17 PDF
12 M,04/01 Quantum error correction Watrous Lec16 (CSS codes) PDF
KLM 10.1,10.2
  W,04/03 Quantum error correction, cont’d Watrous Lec17 (CSS codes) PDF
KLM 10.4,10.5
13 M,04/08 Quantum computational complexity Watrous Lec22 PDF
  W,04/10 Quantum fault-tolerance Vazirani Lec21 PDF
KLM 10.3,10.6
14 M,04/15 Selected Topics  
  W,04/17 Selected Topics  
15 M,04/22 Project presentation  
  W,04/24 Project presentation  
16 M,04/29 Project presentation  
  W,05/01 Reading day, no class  

Quantum compression
Holevo’s bound | Vazirani Lec17 PDF|

Assignments

  • Homework 1 [PDF,TEX], due 01/28/2019, before class.
  • Homework 2 [PDF,TEX], due 02/13/2019, before class.
  • Homework 3 [PDF,TEX], due 03/06/2019, before class.
  • Homework 4 [PDF,TEX], due xx/xx/2019, before class.
  • Homework 5 [PDF,TEX], due xx/xx/2019, before class.
  • Midterm Exam [PDF,TEX], due 03/20/2019, 11:59pm AoE.