Introduction to Quantum Algorithms

Official name: MTAT.05.118 “Quantum Computing I”
Responsible: Assoc. Prof. Dirk Oliver Theis
Next session: Spring 2021

This course covers the basic (i.e., easiest) quantum algorithms.

After a review of quantum mechanics to the extent that is necessary for quantum algorithms, we will discuss the quantum circuit model for universal (fault-tolerant) quantum computing. From there, we will venture to increasingly complex quantum algorithms. We start with the Fourier transform based algorithms (Deutsch-Josza, and Simon’s algorithms, Quantum Fourier Transform, Fourier Sampling, Quantum Phase Estimation) which allows us to discuss Shor’s algorithm. We then proceed to amplitude amplification (Grover’s algorithm) and amplitude estimation. The course concludes with an outlook where we apply all the techniques learned in the semester to discuss a baby-version of the quantum linear system solver.

There will be two lecture classes per week, so that there’s sufficient time to work out lots of example quantum calculations in class.

Prerequisites

The subject matter is somewhat mathematical. If you are not at home with finite-dimensional vector spaces over the complex numbers, and with the spectral theory of normal operators there, you’ll be in for a rough ride. Having mastered a standard course in quantum physics gives sufficient math background. The plan is that LTFY.04.010 Introduction into Quantum Computing will cover all necessary math.

Syllabus
  1. Working with pure states
  2. The circuit model
  3. Fourier sampling & Deutsch-Jozsa algorithm
  4. Period finding and Simon’s algorithm
  5. Quantum Fourier transform
  6. Quantum Phase estimation
  7. Shor’s algorithm
  8. Quantum amplitude amplification
  9. Quantum amplitude estimation
  10. Outlook: Quantum linear system solver
Homework assignments

Homework assignments are handed out once a week, with 1 week time to solve them.

About the level of detail in the solutions:

  • For the parts of the solution that you find easy and are completely certain about: Just give the final answer (if it’s wrong it’s wrong).
  • For the parts of the solution where you’re not wholly comfortable with: Write the solution down in detail explaining your arguments and thoughts, so that we can comment on them during marking, and take problems up in class.
Documents