MAS 725 (Topics in Discrete Mathematics II)

Quantum Computing

Hartmut Klauck

Spring 2012



Lecture:  Mo 10:00-12:30,  SPMS TR+9 


About the course:

The logical operations that govern the operations of  computers are based on classical physics. The field of quantum computation explores what happens, when

those operations are instead performed under the rules of quantum mechanics. Now registers holding information can be in quantum superposition,

allowing interference effects and a phenomenon called entanglement. We will cover models of quantum mechanical computation, study

quantum algorithms (and how they can be more efficient than classical algorithms), and the basic properties of quantum information.

Quantum algorithms covered in this course include Shor's algorithm to factor natural numbers efficiently (putting modern public key cryptography at risk) and

Grover's algorithm, which allows to search an unsorted database quadratically faster than any classical algorithm and has wide applicability to other problems.

We will also look at quantum cryptography and communication protocols.


Basic knowledge in probability and linear algebra. No prior knowledge of physics is required.


Lecture 1

Lecture 2

Lecture 3

Lecture 4

Lecture 5

Lecture 6

Lecture 7

Lecture 8


Michael A. Nielsen and Isaac L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, 2000.

Recommended reading:

Ronald de Wolf's lecture notes

Umesh Vazirani's course

John Watrous' course

Scott Aaronson's (more eclectic) course

April 9, 2012,   Hartmut Klauck