Introduction to Quantum Computation (Summer 2012)

Instructor: François Le Gall
Place: Friday, 10:30 - 12:00, Room 102 of Science Building Number 7
Tentative schedule: 4/6, 4/13, 4/20, 4/27, 5/11, 5/18, 5/25, 6/1, 6/8, 6/15, 6/22, 6/29, 7/6, 7/13

Course outline

This course is an introduction to quantum computing from a computer science perspective. It will cover the foundations of quantum computation, quantum algorithms, quantum error correction and cryptography. This course will be taught in English. No prior knowledge of quantum mechanics will be required.

Topics

1. Introduction and background: a preview of quantum physics, linear algebra
2. Quantum model of computation: quantum gates, quantum circuits, measurements
3. Introductory quantum algorithms: the Deutsch algorithm, the Deutsch-Jozsa algorithm, Simon's algorithm
4. Grover's quantum search algorithm
5. Shor's factoring algorithm and its generalizations
6. Quantum error correction and fault-tolerance
7. Quantum cryptography

Lectures

Lecture 1 [April 6]
Guidance and introduction: overview and history of quantum computation.

Lecture 2 [April 13]
Basics of quantum computation I: quantum states.

Lecture 3 [April 20]
Basics of quantum computation II: measurements.

Lecture 4 [April 27]
Basics of quantum computation III: unitary transformations, Deutsch's algorithm.

Lecture 5 [Mai 11]
Quantum teleportation and dense coding.

Lecture 6 [Mai 18]
Quantum search I: simulating classical computation on a quantum computer, search oracles.

Lecture 7 [Mai 25]
Quantum search II: description and analysis of Grover's algorithm.

Lecture 8 [June 1]
Quantum search III: applications of quantum search, amplitude amplification (a good reference for these topics is this survey paper).

Lecture 9 [June 8]
Integer factoring I: Simon's algorithm.

Lecture 10 [June 15]
Integer factoring II: Shor's algorithm.

Lecture 11 [June 22]
(More) recent quantum algorithms: the Hidden Subgroup Problem, quantum walks, element disjointness and triangle finding.

Lecture 12 [June 29]
Quantum cryptography I.

Lecture 13 [July 6]
Quantum cryptography II. (slides)

Lecture 14 [July 13] (last lecture)
Quantum communication complexity and pseudo-telepathy.

Textbook and suggested reading

There is no required textbook for this course. Students who want to study in more depth the contents of the lectures may refer to Quantum Computation and Quantum Information by Nielsen and Chuang (Cambridge University Press, 2000) or Quantum Computer Science by Mermin (Cambridge University Press, 2007).

Evaluation

Evaluation on submitted reports.
Here are the assignments.