Quantum Algorithms

CPSC 440/640, Course Information, Fall 2016

This course gives a self-contained introduction to quantum algorithms, one of the most exciting recent developments in computer science. We do not expect any background knowledge in quantum computing nor in quantum physics. You should know how to multiply a matrix with a vector, but the most important prerequisite is simply an open mind.

General Information

• You find the syllabus on howdy.
• Questions? Come to my office hours!

Textbook and Lecture Notes

• Required text: Kaye, Laflamme, Mosca: Introduction to Quantum Computing, Oxford University Press, 2007.
• Recommended text: M. Nielson and I. Chuang: Quantum Computation and Quantum Information, Cambridge University Press, 2000 (eletronic copy is available in our library)
• Until you get the textbook, read the lecture notes
• A short summary about continued fractions

Homework and Project

• hw1.pdf hw1.tex
• hw2.pdf hw2.tex
• hw3.pdf hw3.tex
• qcg.tar, a package to typeset quantum circuits (in metapost/LaTeX)
• hw4.pdf hw4.tex (updated)
• alfred.tgz chlg1.alf chlg2.alf chlg3.alf chlg4.alf chlg5.alf
• hw5.pdf hw5.tex
• hw6.pdf hw6.tex

• Project preference proj1.pdf proj1.tex (topics: see perusall, submit on ecampus)
• Intermediate Project Report, November 23, 2:50pm, on ecampus
• Project Report (near final form), December 7, 2:50pm, on ecampus
• Bring/get paper for review in class, December 7
• Review due (email to authors and copy instructor), December 9, 9:00pm
• Project Report (final form), December 11, 10:00pm on ecampus
• Term project slides, December 12, 11:00pm on ecampus
• Checklist for project deliverables

Slides

• Tensor Products
• Controlled Unitary Gates
• Deutsch-Josza Algorithm
• Continued Fractions
• Shor's algorithm
• The Mean King Problem
• The Collision Problem

Schedule

M Aug 29	Introduction, read LN Chapter 1
W Aug 31	Quantum Key Exchange, Quantum States and Gates, LN Chapter 2.1, 2.2
F Sep 02	Quantum Gates, LN Chapter 2.3
M Sep 05	Tensor Products, Quantum Gates, Measurements, LN Chapter 2.4
W Sep 07	Quantum Circuits, Teleportation, LN Chapter 2.5, 3.1, KLM Chapter 5
F Sep 09	Teleportation, LN Chapter 3.1, KLM Chapter 5
M Sep 12	Superdense Coding, Deutsch's Problem, LN Chapter 3.2, KLM Chapter 5
W Sep 14	Deutsch's Problem, Hidden Subgroup Problem, LN Chapter 3.3, KLM Chapter 6
F Sep 16	Deutsch-Josza Algorithm, HW Problems, KLM Chapter 6
M Sep 19	Deutsch-Josza Algorithm, Universality
W Sep 21	Universality, Gates with Multiple Controls, read LN Chapter 4
F Sep 23	Universality, Simulator, read LN Chapter 4
M Sep 26	No class
W Sep 28	Universality, read KLM Chapter 4.3
F Sep 30	Simon's algorithm
M Oct 03	Integer Factorization
W Oct 05	Shor's Algorithm
F Oct 07	Continued Fractions
M Oct 10	Quantum Fourier Transform
W Oct 12	Exam preparation
F Oct 14	A Small Search Algorithm
M Oct 17	Grover's Search Algorithm
W Oct 19	Review
F Oct 21	Midterm
M Oct 24	Exam review
W Oct 26	Mixed states and density operators
F Oct 28	Partial Trace
M Oct 31	Completely Positive Maps
W Nov 02	Quantum Complexity Classes
F Nov 04	Mutually Unbiased Bases
M Nov 07	Mean King Problem
W Nov 09	Quantum Error-Correcting Codes, Shor's code
F Nov 11	CSS Codes
M Nov 14	Stabilizer Codes
W Nov 16	Fault-Tolerant Quantum Computing, Threshold Theorem
F Nov 18	Fault-Tolerant Quantum Gates
M Nov 21	Lower Bounds
W Nov 23	No classes
F Nov 25	No classes
M Nov 28	The Hidden subgroup problem
W Nov 30	The Hidden subgroup problem for Abelian Groups, Graph Isomorphism
F Dec 02	The Collision Problem
M Dec 05	Lower Bounds by Polynomials
W Dec 07	Lower Bounds, Outlook
T Dec 13	Project Presentations, 9:00am-3:00pm, HRBB 302