Quantum Algorithms

CPSC 440/640, Course Information, Fall 2014

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

• Syllabus
• 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

Homework and Project

• hw1.tex hw1.pdf
• hw2.tex hw2.pdf
• hw3.tex hw3.1 hw3.pdf
• hw4.tex hw4.pdf alfred.tgz test files: test-gate.alf test-measure.alf
• hw5.tex hw5.pdf
• Project Selection
• Project Report 1, Nov 09
• Project Report 2, Nov 14
• Project Report 3, Dec 03
• Paper Review, Dec 05
• Final Project Report, Dec 09

Slides

• qbits.key qbits.pdf
• BB84.key BB84.pdf
• tensor_products.key tensor_products.pdf
• teleportation.key teleportation.pdf
• teleportation2.key teleportation2.pdf
• superdense.key superdense.pdf
• boolean.key boolean.pdf
• deutsch.key deutsch.pdf
• controlledU.key controlledU.pdf
• multiplecontrols.key multiplecontrols.pdf
• simon1.key simon1.pdf
• simon2.key simon2.pdf
• shor1.key shor1.pdf
• shor2.key shor2.pdf
• Continued Fractions

Schedule

M Sep 01	Introduction
W Sep 03	Quantum Key Distribution
F Sep 05	Quantum Circuits
M Sep 08	Quantum Gates
W Sep 10	Tensor Products, Quantum Gates, Measurements
F Sep 12	Teleportation
M Sep 15	Dirac notation, Linear Functionals, Bell Measurements
W Sep 17	Teleportation of n+1 Quantum Bits, Superdense Coding
F Sep 19	Deutsch's Algorithm
M Sep 22	Quantum Gates, Parametrization of Unitaries
W Sep 24	Controlled Unitaries, Gates with Several Controls
F Sep 26	Quantum Gates, Universality
M Sep 29	Universality
W Oct 01	Simon's Problem
F Oct 03	Homework Problems
M Oct 06	Simon's Problem
W Oct 08	Shor's Algorithm
F Oct 10	Shor's Algorithm
M Oct 13	Shor's Algorithm, Continued Fractions
W Oct 15	Shor's Algorithm, Quantum Fourier Transforms, Review
F Oct 17	Midterm
M Oct 20	Solution of Midterm exam
W Oct 22	Grover search
F Oct 24	Grover search
M Oct 27	Lower bound for query complexity of quantum search
W Oct 29	Lower bound for query complexity of quantum search
F Oct 31	Quantum Fourier Transform
M Nov 03	Phase Estimation
W Nov 05	Phase Estimation
F Nov 07	Density Matrices
M Nov 10	Quantum Walks
W Nov 12	Quantum Walks
F Nov 14	Quantum Walks
M Nov 17	Quantum Complexity Classes
W Nov 19	Quantum Error-Correcting Codes
F Nov 21	Quantum Error-Correcting Codes
M Nov 24	Quantum Error-Correcting Codes
W Nov 26	Fault-Tolerant Quantum Computing
F Nov 28	No class
M Dec 01	The Threshold Theorem
W Dec 03	Project Presentations, Team 1, Team 2
F Dec 05	Project Presentations, Team 3, Team 4
M Dec 08	Project Presentations, Team 5, Team 6
W Dec 10	Time noon-3:00pm, Project Presentations, Team 7-11