Introduction to Quantum Algorithms

Spring 2020

Official name: MTAT.05.118 “Quantum Computing I”

Assoc. Prof. Dirk Oliver Theis
PhD candidate Rafieh Mosaheb

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.

Compared to last year, we have are slowing down the course by a factor of 2: There will be two lecture classes per week, so that there’s sufficient time to work out lots of example quantum calculations in class.

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. In other words, standard undergraduate math will not be repeated in this course. In the past, having mastered a standard course in quantum physics has indicated sufficient math background.

Syllabus (draft)
  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 (see “Documents” below) are handed out and due on Mondays, 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 or thoughts, so that we can comment on them during marking, and take problems up in class.

Gradesheet for homework assignments