Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Quantum information and applications (24h, 3ECTS)

Person in charge: Sophie Laplante (Université Paris Diderot, IRIF)

Teachers for 2020-21

Organisation

Lectures take place Wednesdays 12:45 13:00. We will have 10 x 2.5 hours during the first period.

In case you are awaiting test results, or tested positive for COVID, or have any symptoms, please do stay at home and keep us informed of your situation by email.

From October 7th until further notice, lectures will be given in hybrid mode. Sophie Laplante will use BBB. You can joins us remotely if you have a strong preference to do so, else if you hesitate, flip two coins and join us remotely if it comes down heads twice. Everyone else please come to class.

Lectures will take place in French, English upon request. (In the past all lectures have been in English.)

Basic notions

  • Sept 16 SL States, measurements, entanglement, CHSH
  • Sept 23 SL Evolution, circuits, superdense coding
  • Sept 30 SL Holevo's theorem, teleportation, no-cloning, BQP
  • Oct 7 SL BPP vs BQP, Quantum query model, Deutsch-Jozsa, Bernstein-Vazirani
  • Oct 14 SL Grover's algorithm, Simon's algorithm

Algorithms and information

  • Oct 21 AC NO CLASS THIS WEEK
  • Oct 28 AC
  • Nov 4 AC
  • Nov 18 AC
  • Nov 25 AC

FINAL EXAM

The final exam will take place on Dec. 2nd at the usual time. The exam will be 2 hours. Handwritten and printed lecture notes (your own, Ronald de Wolf, Iordanis Kerenidis, etc.) are allowed for the exam.

The exam will be online at the following link BBB . We will ask you to turn off your microphone and turn on your camera during the exam. We will be available to answer questions by private chat.

Please make sure to have your student ID with you for the exam and that you have the ability to scan or photograph your exam in good enough quality so that it is legible.

The exam will be made available on this page as a PDF file at the beginning of the exam. Please handwrite the answers as you would normally do, and use separate sheets for parts I and II. Please send your answers to the emails given on the exam at the end of the allotted time.

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 objectives

Each 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.

Prerequisites

Algorithms, basic notions in computational complexity, basic notions in linear algebra and probability.

Course outline

Introduction

  • 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 Notes

We recommend the following lecture notes to use alongside the lectures:

- Ronald de Wolf Quantum Computing lecture notes

- Iordanis Kerenidis lecture notes

Related Courses

This 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 Computation and Quantum Information. M. Nielsen et I. Chuang. Cambridge University Press, 2000.

Internships

Internships in the area of Complexity Theory are available. Please contact the Algorithms and Complexity group of IRIF or PCQC

 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA