Introduction to quantum computer science and applications
Introduction
This course presents quantum-mechanical principles and introduces the quantum model of computing. This model allows for instance to solve in polynomial time problems believed to be hard in the classical world like factorization (Shor's algorithm). This is a significant threat against many currently deployed cryptographic systems.
After presenting the main quantum algorithms we will cover the foundations of quantum information theory and quantum error correcting codes. Ultimately, we will present cryptographic systems whose security is based on the very nature of quantum mechanics.
Acknowledgment
I am particularly grateful to André Chailloux and Jean-Pierre Tillich for sharing with me their materials to build this course (as well as providing many advices). I am also grateful to Daniel Augot and François Morain for spotting many typos in the earlier versions.
Lectures
- Introduction to quantum computing: Lecture 1 and
Exercise Session 1
1) Classical bits versus quantum bits
2) Your first quantum algorithm: Deutsch-Josza algorithm
3) Tensorization: n qubits system
4) Bra-ket and ket-bra notation
- Fundamentals of quantum computing and quantum information: Lecture 2 and
Exercise Session 2
1) Basics of linear algebra: some notation
2) Basics of linear algebra: spectral decomposition, operator functions and trace
3) Postulates of quantum mechanics
4) An application: teleportation
- Density operator and partial trace: Lecture 3 and
Exercise Session 3
1) Density operator
2) The reduced density operator, partial trace and application to the teleportation
3) Schmidt decomposition and purification
- Introduction to quantum computing, the circuit model: Lecture 4 and
Exercise Session 4
1) Notation and basic circuits
2) The Solovay-Kitaev theorem and the quantum gate model
3) Simulating classical circuits with quantum circuits
4) Quantum parallelism and interference
5) A quantum algorithm: Simon's algorithm
- Grover's search algorithm and introduction to the Quantum Fourier Transform: Lecture 5 and
Exercise Session 5
1) Grover's search algorithm
2) Amplitude amplification
3) Introduction to the discrete Fourier transform
4) Quantum Fourier Transform over ℤ/2nℤ
- Phase estimation, Shor's algorithm and Hidden Subgroup Problem: Lecture 6, Morain's presentation and Exercise Session 6
1) Phase estimation
2) Application 1: Quantum Fourier Transform on ℤ/Nℤ and any finite Abelian group
3) Application 2: order finding
4) Shor's algorithm
5) François Morain's presentation about factoring classically
6) Hidden Subgroup Problem
- Quantum errors correcting codes and a little bit of classical error correcting codes Lecture 7 and
Exercise Session 7
1) Classical error correcting codes: to be protected against classical errors
2) A first quantum error correcting code: Shor's code
3) Calderbank-Shor-Steane (CSS) codes
4) Stabilizer codes
5) Threshold theorem
- Distance measures for quantum states and quantum cryptography Lecture 8 and
Exercise Session 8
1) Distances over distributions
2) Distance between quantum states
3) Bit commitment
4) Quantum Key Distribution
Final exam
Presentation of one of the below topics.
- Optimum Unambiguous Discrimination Between Linearly Independent Symmetric States,
A. Chefles and S. M. Barnett.
- On the distinguishability of random quantum states,
A. Montanaro.
- Breaking symmetric cryptosystems with Simon's algorithm,
by
Marc Kaplan, Gaetan Leurent, Anthony Leverrier and María Naya-Plasencia
- Quantum query lower bounds
Chapter 11,
in the lecture notes by Ronald de Wolf
- The hidden nonabelian subgroup problem and the Kuperberg
algorithm,
Chapters 11-13,
in the lecture notes by
Andrew Childs
- Kitaev's toric code,
Section 5,
in the lecture notes by
Gilles Zemor
Bibliography (books and lectures notes used for this course)