Table of Contents
## Quantum information and applications (24h, 3ECTS)Person in charge: Sophie Laplante (Université Paris Diderot, IRIF) ## Teachers for 2017-18## OrganisationLectures take place Tuesdays at 12:45 in room 2035 Lectures will take place in French, English upon request. (In the past all lectures have been in English.) Basic notions - Sept 11 SL
- Sept 18 SL
- Sept 25 SL
- Oct 2 SL
Algorithms and information - Oct 9 AC
- Oct 16 No class
- Oct 23 AC
- Oct 30 AC
- Nov 6 AC
The final exam will take place at the usual time and place (date TBA). Handwritten and printed lecture notes (your own, Ronald de Wolf, Iordanis Kerenidis) are allowed for the exam. Sample exam from 2013. Be aware that the content varies from year to year and in particular there is no crypto in the course this year. ## Presentation and objectivesEach year computing machines become faster and faster, but they use still use at their base the same Newtonian physics. Feynman in 1982 already asked about the necessity of this restriction to classical physics. The idea behind quantum computation is to use quantum phenomena to solve tasks that conventional machines cannot achieve. Historically the first result that showed the superiority of the quantum model was in cryptography. Bennett and Brassard in 1984 gave a first quantum protocol for perfectly secure key distribution. Such an unconditional security does not exist in the classical world. At present many important concepts of theoretical computer science have been extended to quantum computation, from communication to algorithms and error correcting codes. The aim of this course is to present the bases of several concepts about quantum computation. The emphasis will be on quantum algorithms and communication. We will describe the basics of Quantum Computation and its applications in algorithms, communication complexity and nonlocality. ## PrerequisitesAlgorithms, basic notions in computational complexity, basic notions in linear algebra and probability. ## Course outlineIntroduction - Model of quantum computation
- EPR paradox, teleportation, superdense coding.
- Holevo's theorem
Basic algorithms - Deutsch-Jozsa, Simon's algorithm, Grover search
Advanced Algorithms - Period finding, quantum Fourier transform, Shor's factoring algorithm.
- Amplitude amplification, collision algorithms
- Other quantum algorithms relevant in cryptography
Quantum complexity - Basics of quantum complexity theory
## Lecture NotesWe recommend the following lecture notes to use alongside the lectures: - Ronald de Wolf Quantum Computing - Iordanis Kerenidis lecture notes ## Related CoursesThis course is a prerequisite for the course Quantum information and cryptography which covers quantum cryptography and post-quantum cryptography. The following courses are strongly recommended. - 2.11.1 Advanced algorithms
- 2.11.2 Randomness in Complexity
If you are interested in Algorithms and Complexity, we recommend taking courses from the following list. 1st quarter courses - 2-11-1 Advanced Algorithms
- 2-11-2 Randomness in Complexity
- 2-12-1 Techniques in Cryptography and Cryptanalysis
- 2-18-2 Algorithmique distribuée avec mémoire partagée
- 2-38-1 Algorithms for embedded graphs
1st and 2nd quarter courses - 2-13-2 Error correcting codes and applications to cryptography
- 2-18-1 Distributed algorithms for the networks
- 2-24-1 Optimisation
- 2-29-1 Graph algorithms
- 2-33-1 Theory of Computations
## References- Quantum Computer Science: An Introduction. N. David Mermin. Cambridge University Press, 2007.
- Quantum Computing: Lecture Notes. R. de Wolf
- Quantum Computation and Quantum Information. M. Nielsen et I. Chuang. Cambridge University Press, 2000.
## InternshipsInternships in the area of Complexity Theory are available. Please contact the Algorithms and Complexity group of IRIF or PCQC |