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

• Sophie Laplante (Université Paris Cité, IRIF)
• Frédéric Magniez (CNRS, IRIF)

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.

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

Lectures take place Tuesdays 8:45, room 1004. Unless specified otherwise lectures are in the 3-hour format. Lectures will take place in French, English upon request. (In the past all lectures have been in English.) References in brackets refer to Ronald de Wolf's (RdW) and John Watrous' (JW) lecture notes.

Basic notions (order and contents subjects to change)

• Sept 13 SL States, measurements, entanglement. CHSH [RdW: Chapter 1.1-1.4 + 16.1-16.2] [JW: Lectures 1&2, Lecture 3 pp.6-8, Lecture 20 pp. 1-5]
• Sept 20 SL density matrices, Entropy and Holevo's theorem. Gates and circuits, no-cloning theorem, superdense coding, teleportation [RdW: 1.5] [JW Lecture 3, Lecture 4 pp. 1-3]
• Sept 27 SL BPP in BQP, Quantum query model, Deutsch-Jozsa [RdW: 2.1, 2.4] [JW Lecture 4 pp. 3-6]
• Oct 4 SL Bernstein-Vazirani, Grover's algorithm, Simon's algorithm [RdW: 7.1-7.2, 3.1-3.2] [JW: Lectures 6, 12, 13]

Algorithms and complexity (contents subjects to change)

• Oct 11 FM Modern definition of quantum algorithms, Amplitude Amplification, Quantum Counting [RdW: 7.3-7.4, Qiskit: 3.1, 3.8-3.9, 4.1]
• Oct 18 FM Fourier Transformation, Period Finding [RdW: 4.4-4.5, 5.3, Qiskit: 3.5]
• Oct 25 NO CLASS but HOMEWORK (see homework section)
• Nov 1 NO CLASS (public holiday)
• Nov 8 Frédéric Magniez Correction of Homework, Factorization, Discrete Logarithm, Hidden Subgroup Problem [RdW : 5.1-5.4, 6.1, Qiskit: 3.7]
• Nov 15 FM Phase estimation, Linear System Solver (special case of unitary systems). Lower bounds for query complexity: polynomial method. . [RdW: 4.6, 10.1, 11.1-11.2, Qiskit: 3.6, 4.1]

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 by IRIF and MPQ, which you are welcome to attend.

They take place in room 454A of building Condorcet, on Fridays, 12h-13h, starting October 14th (3 in October, 1 in December):

• 14/10 Patrice Bertet (SPEC CEA Saclay): “Single spin magnetic resonance by microwave fluorescence detection”

• 21/10 Simon Apers (CNRS, IRIF, Université Paris Cité): “Developments in quantum algorithms”

• 28/10 Thierry Lahaye (Laboratoire Charles Fabry, Institut d'Optique, CNRS et Université Paris-Saclay): “Quantum simulation and quantum computing with arrays of single Rydberg atoms”

• 02/12 Roberto Osellame (Politecnico di Milano, CNR-IFN): “Integrated quantum photonics, a powerful platform for quantum technologies”

Here is the homework to do during the break period (Oct 25 and Nov 1):

• Before Nov 8, send a pdf file or a picture of your homework by email to magniez@irif.fr
• Answer in english or french to the following problems in Ronald de Wolf Quantum Computing lecture notes
  • Chapter 1: 4, 6, 7, 10
  • Chapter 2: 3, 9, 11
  • Chapter 3: 4, 5

The final exam will take place on Nov 22, 9:00-11:30. Handwritten and printed lecture notes (your own, Ronald de Wolf, or others) are allowed for the exam.

Please make sure to have your student ID with you for the exam.

Sample exams:

• 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.
• Part of exam from 2014, with an example of a quantum algorithm to design.

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

- Ronald de Wolf Quantum Computing lecture notes

- John Watrous Quantum Computation Lecture notes

- John Preskill Lecture notes for PH219/CS219 mainly for information theory (10.1, 10.2.1) and Holevo's bound (10.6.2)

- Qiskit (open-source SDK) Textbook mixing quantum computation explanations and source codes

The following textbooks are also suggested.

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

This course is a prerequisite for the course Quantum information and cryptography which covers advanced algorithms, 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

If you are particularly interested in quantum computing you can also take courses from the Physics masters program Dispositifs quantiques