M1 QDCS - Introduction to Quantum Algorithms and Programming

Summary

Beginner's course on quantum algorithms and programming given in the QDCS Master of Université Paris-Saclay. We aim at covering the following topics:

• A tiny bit of linear algebra
• The quantum co-processor model
• Circuit Synthesis
• A bit of complexity
• Canonical algorithms: QFT, Grover, QPE, Shor

The lecturer is Benoit Valiron.

The final grade consists in 1/3 continuous examination (homeworks) and 2/3 final exam.

Information about the Exam

On Friday, Oct 24 from 9am to 11am, in room C.105

On paper

Documents allowed: course notes, your own notes, the solutions of exercises

Material

• Course notes v.2025.09.15 [pdf]

  Contain the union of all of the material I present in the various courses I give: we will not cover everything. There are probably many typos, feel free to report them to me so that I can update the document.

  Added on Sep 15

• Lab session #1 [pdf]

  Series of exercises for practice.

  Added on Sep 19

• Lab session #2 [pdf]

  Series of exercises for practice.

  Q.3 of Ex.2 can be disregarded.

  Added on Sep 26

• Coding session #1 [zip]

  Jupyter Notebook for practice:

  Implementing QPE.

  Added on Oct 3

• Homework #1 [zip]

  Due at the start of next class, on Oct 10.

  Paper and electronic versions are fine.

  Added on Oct 3

• SOLUTIONS Coding session #1 [html]

  HTML output of my jupyter notebook for QPE.

  Added on Oct 10

• HMW Coding session #2 [zip]

  To finish home, serves as a homework

  Due at the start of next class, on Oct 17.

  BEWARE TYPO: "reps=6" to change into "reps=12" in "getSample"

  BEWARE do not forget to measure...

  Added on Oct 10

• HMW Coding session #3 [zip] NEW

  Jupyter Notebook on Grover

  For practice

  Added on Oct 17

• SOLUTIONS for Homework #1 [pdf] NEW

  Sketch of solutions for the homework due Oct 10

  Added on Oct 17

What has been covered so far

Sep 12

• All of Section 2 apart from hermitian matrices
• Sections 3.1 to 3.6.

Sep 19

• Lab session #1
• Section 3.8 (measurement)
• Sections 6.1.1 to 6.1.6 (Deutsch-Josza, study for the case n=1)

Sep 26

• Lab session #2
• Section 3.9 (discard, ancillas, computation-uncomputation)
• We only schemes through Sections 4.1, 4.2, 4.3 (I only mentionned universality, gave an intuition on what is complexity for probabilistic algorithms and how it relates to quantum algorithms. You can still read the sections if you want of course!)
• Section 5.1 (quantum algorithms in general)
• Section 5.5 (QFT)

Oct 3

• Section 5.6 (QPE) and Sections 6.2.1, 6.2.2 and 6.2.3 (first part of Shor's algorithm).
• Coding session #1 (implementing QPE)
• Homework #1 to hand over at the begining of next class, at 9am on Oct 10.

Oct 10

• Section 6.2 (Shor's algorithm).
• Coding session #2 (implementing Shor)
• To finish home and to hand over by the begining of next class, at 9am on Oct 17.

Oct 17

• Overview of circuit synthesis: Paragraph 4.3.20, Sections 5.2, and 5.7.1-13.
• Section 5.4 (Amplitude Amplification, a.k.a. Grover's algorithm).
• Coding session #3 (implementing Grover)

Oct 24

• Exam from 9am to 11am, room C.105