Introduction to Quantum Computation (Summer 2014)

Instructor: François Le Gall
Place: Friday, 10:30 - 12:00, Room 102 of Science Building Number 7

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

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

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

Lecture 4 [May 9]
Basics of quantum computation III: unitary transforms, Deutsch｡ﾇs quantum algorithm.

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

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

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

Lecture 8 [June 6]
Quantum search III: applications of quantum search, quantum amplitude amplification, reduction from integer factoring to period finding.

Lecture 9 [June 13]
Integer Factoring I: Period finding and the Hidden Subgroup Problem, Simon's algorithm.

Lecture 10 [June 20]
Integer Factoring II: Analysis of Simon's algorithm, Shor's period finding algorithm, relation with integer factoring.

Lecture 11 [June 27]
Quantum Cryptography I: classical private key and public key cryptography, description of the BB84 protocol.

Lecture 12 [July 13]
Quantum Cryptography II: Analysis of the security of the BB84 protocol.

Lecture 13 [July 18, final lecture]
Conclusions: other tasks in quantum cryptography, implementations of quantum computers, fault tolerance and quantum error-correcting codes.

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.