Quantum computer science and Mathematics

Learning outcomes: After passing the course the student understands

• the mathematical background that underlies the RSA cryptosystem
• the formalism of quantum computing
• the key ideas that explain why Shor's algorithm allows to factor integers faster

and has learned about

• a recent (2023) conditional improvement on Shor's algorithm which requires fewer (in a precise sense) quantum gates (this is due to Regev)
• the type of mathematical tools that were used to prove the unconditional correctness of this algorithm (Pilatte, 2024)

Content:

• RSA cryptosystem
• Introduction to quantum computing
• Overview of Shor's algorithm
• Overview of Regev's variant of Shor's algorithm
• Introduction to the mathematical tools of Pilatte's proof of correctness

Qualifications: A basic knowledge of group theory and modular arithmetic will be helpful, but we will try to recall as much as possible at the beginning of the course.

Level: Advanced studies

Teaching methods: Daily lectures during a week (4 times 3 hours) + some optional exercise session (1 hour) to review modular arithmetic

Assessment criteria: Multiple choice quiz on the content of the lectures

Assessment scale: 1-5

Primary teaching language: English

Person in charge: Théo Untrau