15-859BB: Quantum Computation and Information 2015

• 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

• Lecture 23 -- BQP
• Lecture 24 -- QMA
• Lecture 25 -- QMA(2)
• Lecture 26 -- QIP and QMIP

• 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