Introduction to Quantum Computing

1. Detailed presentation of Deutsch-Jozsa algorithm, with an in-depth discussion on the meaning of “quantum algorithm”, and how to rule the game.

2. Elements of complexity theory, starting with the classical (universal Turing machine, P, NP, BPP and BQP, oracles)

3. General elements on quantum circuits, basic gates, and the beginning of universality 4. Universality and the Solovay-Kitaev theorem

5. Introduction to quantum platforms (photonics, ions, supra) and computational alternatives (measurement-based, Ising machines, adiabatic computation)

6. Quantum algorithms:
a) Deutsch-Jozsa “le retour”, Bernstein-Vazirani, Simon b) Period finding and Shor
c) Grover and quantum simulation

7. Introduction to error correction:
a) classical and quantum repetition codes, Shor code
b) back to noise sources (quantum channels = Kraus maps), noise discretization theorem, heuristic approach on the meaning of fault-tolerance of logic gates.