Each year, computing machines become faster and faster, but they still fundamentally rely on Newtonian physics. As early as 1982, Feynman questioned 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.

Quantum computing has become a standard topic in modern computer science. The tools developed for designing, analyzing, and understanding quantum algorithms are now widely used in complexity and algorithms, including cryptography, whether they are distributed, randomized, and not necessarily quantum.

Historically, the first result demonstrating the superiority of the quantum model was in cryptography. In 1984, Bennett and Brassard introduced the first quantum protocol for perfectly secure key distribution. Such unconditional security does not exist in the classical world. Later, the intrinsic property of nonlocality, such as Bell’s inequalities, was also exploited for various communication games like the CHSH games. Their studies opened a new field of research at the interface of complexity and nonlocality.

Following the pioneering work of Deutsch in 1985, Bernstein and Vazirani discovered an efficient universal quantum Turing machine in 1993. This led to a series of revolutionary algorithms. One notable example is Shor's algorithm in 1994 for factoring large integers, a problem considered hard and on which the security of several modern public key cryptographic protocols, such as RSA and Diffie-Hellman, is based. Another significant algorithm is Grover's search algorithm from 1996, which can quadratically speed up most heuristic algorithms.

Currently, many important concepts of theoretical computer science have been extended to quantum computation, encompassing areas from communication to algorithms and error-correcting codes. With the advent of near-term quantum devices, developed by well-known industrial groups and startups, there is also a push to create software based on these new tools to solve emerging industrial use cases.

The aim of this course is to present the fundamentals of several concepts in quantum computation. We will describe the basics of quantum information and computation, along with a range of both simple and significant applications in computer science.

The objectives are twofold. First, this course is a recommended prerequisite before attending more advanced classes in quantum algorithms. Second, it will serve as a solid foundation, which is now a standard worldwide, for any scientist interested in topics such as randomized algorithms, complexity, distributed computing, and cryptography.

This course is also part of the Quantum technologies Graduate School of Université Paris Cité. As a consequence, a joint QuanTech seminar is offered to MPRI students.

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

This course is a recommended prerequisite for the two other quantum courses

• Quantum Algorithms and Complexity (QALCO)
• Quantum Coding and Cryptography (QCC)

It is also related to the MPRI themes

• Algorithms
• Complexity
• Cryptography
• Parallel/Distributed Algo

• First class (lecture & exercises): September 18th, Thursday, 12:45–15:45, Room 1002
• Mondays, 13:45-15:45, Room 1002: 2 hours per week of lectures on Mondays
• Thursdays, 13:00-14:00, Room 1002: 1 hour per week of tutorials that alternate between
  • Practical exercises: 1-hour sessions focused on application exercises, proofs, and answering pre-given exercise questions to aid in understanding new concepts.
  • Seminar: 1-hour sessions by invited speakers, focusing on specialized topics, including the joint QuanTech seminar offered to MPRI students.
  • Warning: Some seminars will be followed by a buffet in a different room and a different time slot (12:15-14:00)
• Materials provided in class for lectures, tutorials and seminars: MPRI2025-QUANTUM

• Sophie Laplante, Professor at Université Paris Cité, IRIF (not teaching in 2025-26)
• Frédéric Magniez, CNRS Research Director at Université Paris Cité, IRIF

1. Single qubits: state, measurement, transformations, quantum key distribution (BB84), Deutsch algorithm
2. Multiple qubits: tensor product, entanglement, partial measurement, super dense coding, teleportation, CHSH game, Bell and Tsirelson inequalities
3. Quantum algorithms: circuit computational model, universal set of gates, Hamiltonian simulation
4. Complexity classes: simulation (BPP in BQP, BQP in PSPACE), oracle separation (Deutsch-Jozsa, Bernstein-Vazirani)
5. Quantum Fourier transform: phase estimation, period finding
6. Shor's algorithm, hidden subgroup problem
7. Grover's algorithm, amplitude amplification, collision finding
8. Lower bounds for query complexity: adversary and polynomial methods

• One homework will be given after basically 4-5 weeks
• A written exam in the classroom during the exam period at the end of the period (2 double-sided cheat sheets authorized)
• Final grade = min(20, E + B), where E is the exam grade and B is the bonus grade, mainly from homework and class participation

• PGG : Amphithéâtre Pierre-Gilles de Gennes, Bâtiment Condorcet - niveau -1, 10, rue Alice Domon et Léonie Duquet, Paris 13, Campus map

All materials will be provided in class. Nonetheless, external resources are available to complement the course:

• Lecture notes (in case your notes are not detailed enough)
  • Quantum Computing: Lecture Notes, Ronald de Wolf
• Online lectures (in case you miss a class)
  • In French: Cours Algorithmes quantiques - Collège de France
  • In English: IBM Quantum Learning: Online Course
• Book for complementary and advanced material (available at the MIR Sophie Germain Library)
  • Quantum Computation and Quantum Information, M. Nielsen and I. Chuang, Cambridge University Press, 2000
• Quantum programming language (optional, to implement some of the algorithms presented in class)
  • Qiskit programming language