- Homework 1, due Tuesday September 15, 11:59pm
- Homework 2, due Tuesday September 22, 11:59pm
- Homework 3, due Tuesday October 6, 11:59pm
- Homework 4, due Tuesday October 27, 11:59pm
- Homework 5, due Tuesday November 24, 11:59pm
- Homework 6, due Wednesday December 9, 11:59pm

All scribe notes in a single PDF

*Quantum computation*

- Lecture 01 -- Introduction to the Quantum Circuit Model (all source files, zipped)
- Lecture 02 -- Quantum Math Basics
- Lecture 03 -- The Power of Entanglement
- Lecture 04 -- Grover's Algorithm
- Lecture 05 -- Quantum Query Model Basics
- Lecture 06 -- Boolean Fourier Analysis and Simon's Problem
- Lecture 07 -- Quantum Fourier Transform over Z
_{N} - Lecture 08 -- Period Finding
- Lecture 09 -- Shor's Algorithm
- Lecture 10 -- The Hidden Subgroup Problem
- Lecture 11 -- Quantum Query Lower Bounds: The Polynomial Method
- Lecture 12 -- Lower Bounds for Element-Distinctness and Collision
- Lecture 13 -- Quantum Query Lower Bounds: The Adversary Method
- Lecture 14 -- Reichardt's Theorem I: Definition of Span Programs
- Lecture 15 -- Reichardt's Theorem II: Evaluation of Span Programs

- Lecture 16 -- Mixed States and General Measurements
- Lecture 17 -- Discriminating Two Quantum States
- Lecture 18 -- Quantum Information Theory and Holevo's Bound
- Lecture 19 -- Quantum Channels and Finishing Holevo's Bound
- Lecture 20 -- The Pretty Good Measurement
- Lecture 21 -- The HSP via the PGM
- Lecture 22 -- Introduction to Quantum Tomography

This course will be an introduction to quantum computation and quantum information theory, from the perspective of theoretical computer science. Topics to be covered will likely include:

- The quantum circuit model of computation
- Basic quantum algorithms like Deutsch-Josza, Simon, and Grover
- Shor's factoring algorithm
- Quantum entanglement, teleportation, and Bell inequalities
- Quantum Fourier transforms and the hidden subgroup problem
- Quantum query complexity, span programs, and the adversary method
- Density matrices, state discrimination, tomography
- Von Neumann entropy and Holevo's bound
- Quantum nonlocal games, interactive proofs, and PCP

**Prerequisites**

A strong undergraduate background in linear algebra (e.g., CMU's 21-341), discrete probability (e.g., CMU's 15-359), and theory of computation (e.g., CMU's 15-251). No background in physics is required. We anticipate the course will be of interest to students working in computer science, mathematics, or physics.

**Evaluation**

Evaluation will be based on 6--8 homework assignments and 2 lecture note scribings.

**Suggested text and lecture notes to look at**

- Nielsen and Chuang textbook
- Aaronson course
- Ambainis course (hit the second button, labeled "Pieslēgties kā viesim")
- Bacon course
- Childs course
- Cleve course
- Kempe course
- van Melkebeek course
- Montanaro course
- Preskill notes
- Razborov course
- Reichardt course
- Shor course
- Vazirani course
- Vidick course
- Watrous courses
- Wolf course
- de Wolf course