MTAT.05.118 "Quantum Computing I"

Introduction to Quantum Algorithms

Assoc. Prof. Dirk Oliver Theis

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; maybe the basics of quantum walks, if time permits. The course is concluded 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 slowed 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.

Timeline (draft)

1. Working with pure states
2. The circuit model
3. Fourier Sampling & Deutsch-Jozsa Algorithm
4. 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 (see download folder) 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.

Contact

Dirk Oliver Theis
d o t h e i s [at] u t [dot] e e

Rafieh Mosaheb
r a f i e h . m o s a h e b [at] u t [dot] e e