Introduction to Quantum Computation (Summer 2011)

Instructor: François Le Gall
Place: Friday, 10:15 - 11:45, Room 102 of Science Building Number 7
Announcement: the first lecture is scheduled for May 6th

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 [May 6]
Guidance and introduction: overview and history of quantum computation.

Lecture 2 [May 13]
Basics I: classical states, quantum states, quantum measurements.

Lecture 3 [May 20]
Basics II: unitary transforms, quantum circuits, Deutsch's quantum algorithm.

Lecture 4 [May 27]
Basics III: Deutsch's quantum algorithm, the non-cloning theorem, simulation of classical computation, universal sets of quantum gates.

Lecture 5 [June 3]
Quantum teleportation and quantum superdense coding.

Lecture 6 [June 10]
Quantum search.

Lecture 7 [June 17]
Applications of quantum search: database search, speed-up for NP-complete problems, quantum algorithms for the collision problem (a good reference for these topics is Section 3 of this survey paper).

Lecture 8 [June 24]
Integer Factoring I: Simon's algorithm.

Lecture 9 [July 1]
Integer Factoring II: reduction from integer factoring to period finding, the Quantum Fourier Transform, Shor's algorithm.

Lecture 10 [July 8]
Topics in Quantum Computing: the Hidden Subgroup Problem, quantum communication complexity (the protocol for set intersection by Buhrman, Cleve and Wigderson).

Lecture 11 [July 15]
Quantum Cryptography I: private-key and public-key classical cryptography, Quantum Key Distribution.

Lecture 12 [July 22] (last lecture)
Quantum Key Distribution (analysis of the BB84 protocol), bit commitment, fault-tolerant quantum computation.

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 [update (2011/8/2): a correction has been made in question (2) of Problem 2].