(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 xx/xx/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 Partial measurement
reversible computation, quantum circuit
Watrous Lec3 PDF, Lec7 PDF
KLM Chapter 4
4 M,02/04 Superdense coding
Teleportation
Watrous Lec3 PDF, Lec4 PDF
  W,02/06 AIM Workshop, class cancelled  
5 M,02/11 Deutsch & Deutsch-Josza algorithms Watrous Lec5 PDF
  W,02/13 Simon’s Algorithm Watrous Lec PDF
6 M,02/18 Simon’s Algorithm cont’d
phase estimation
Watrous Lec8 PDF
Vazirani Lec12 PDF
  W,02/20 Phase estimation cont’d
quantum Fourier transform
Watrous Lec9 PDF
7 M,02/25 Order finding Watrous Lec10 PDF
  W,02/27 Quantum factorization algorithm Watrous Lec11 PDF
Vazirani Lec8 PDF
8 M,03/04 Grover’s algorithm Watrous Lec12 PDF
  W,03/06 Grover’s algorithm, cont’d Watrous Lec13 PDF
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 Quantum error correction Watrous Lec16 PDF
KLM 10.1,10.2
11 M,03/25 Quantum error correction, cont’d Watrous Lec17 (CSS codes) PDF
KLM 10.4,10.5
  W,03/27 Quantum fault-tolerance Vazirani Lec21 PDF
KLM 10.3,10.6
12 M,04/01 Entropy Vazirani Lec13 PDF
  W,04/03 Quantum compression
Holevo’s bound
Vazirani Lec17 PDF
13 M,04/08 Quantum computational complexity Watrous Lec22 PDF
  W,04/10 Selected Topics  
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  

Assignments

  • Homework 1 [PDF,TEX], due 01/28/2019, before class.
  • Homework 2 [PDF,TEX], due xx/xx/2019, before class.
  • Homework 3 [PDF,TEX], due xx/xx/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 xx/xx/2019, before class.