Introduction to Quantum Computation (Summer 2015)

Instructor: François Le Gall
Place: Friday, 10:25 - 12:10, Room 102 of Science Building Number 7
Schedule: 4/10, 4/17, 4/24, 5/1, 5/8, 5/22, 5/29, 6/5, 6/12, 6/26, 7/3, 7/10, 7/17

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 10]
Guidance and introduction: overview of quantum computation.

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

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

Lecture 4 [May 1]
Basics of quantum computation III: unitary transforms, Deutsch's quantum algorithm.

Lecture 5 [May 8]
Quantum teleportation and quantum dense coding.

Lecture 6 [May 22]
Quantum search I: quantum circuit complexity, search oracles, description of Grover algorithm.

Lecture 7 [May 29]
Quantum search II: analysis of Grover algorithm.

Lecture 8 [June 5]
Integer factoring I: the Hidden Subgroup Problem, Simon's algorithm for period finding.

Lecture 9 [June 12]
Integer factoring II: Shor's algorithm for period finding, reduction from integer factoring to period finding.

Lecture 10 [June 26]
Other quantum algorithms: Amplitude amplification, Quantum walk search.

Lecture 11 [July 3]
Quantum cryptography I: classical private and public key cryptosystems, the BB84 protocol for quantum key distribution.

Lecture 12 [July 10]
Quantum cryptography II: analysis of the BB84 protocol.

Lecture 13 [July 17, final lecture]
Quantum cryptography III and Fault Tolerance: impossibility of quantum bit commitment, quantum fault tolerance, quantum error correction.

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.