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. The course is concluded with an outlook where we apply all the techniques learned in the semester to discuss a baby-version of the HHL quantum linear system solver.

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.

Lectures

General info
Lecture 1: Working with pure states
Lecture 2: The circuit model
Lecture 3: Classical computation on a quantum computer
Lecture 4: Review of the Discrete Fourier Transform
Lecture 5: Fourier Sampling & Deutsch-Jozsa Algorithm
Lecture 6: Simon's Algorithm
Lectures 7-8: Quantum Fourier Transform
Lectures 9-10: Quantum Phase Estimation
Lecture 11: Shor's algorithm
Lectures 12-13: Quantum Amplitude Amplification
Lectures 14-15: Quantum Amplitude Estimation
Lecture 16: Outlook: Quantum linear system solver

Practice Sessions

Homework assignments

NEW: You can see your homeworks' grades here: https://docs.google.com/spreadsheets/d/1-ugFJYocfdogez6SUVLDCqsT4AVmEX_se4UOKwDeCPE/edit?usp=sharing

To hand in your solutions:

Print them (or write them in perfect hand-writing), and hand them in before the practice session
Or send them by email to Rafieh (the PDF version is preferred!).
No late submissions will be accepted.

Attention: for the nth set of Homeworks please use the following title for your email and the PDF file (if applicable): HWn_QC_your-name. Otherwise it might not be graded.

# 1

Overleaf link: https://v2.overleaf.com/read/qjjkgmtsngyb
Due Tuesday, Feb 26, 14:14.

# 2

Overleaf link: https://v2.overleaf.com/read/qhbgstqrvbfr
Due Tuesday, Mar 5, 14:14.

# 3

Overleaf link: https://v2.overleaf.com/read/vzkyjvvrskcd
Due Tuesday, Mar 12, 14:14.

# 4

Overleaf link: https://v2.overleaf.com/read/qzhhhkrmkzwv
Due Tuesday, Mar 19, 14:14.

# 5

Overleaf link: https://v2.overleaf.com/read/bgywyfrpjjcb
Due Tuesday, Mar 26, 14:14.

# 6

Overleaf link: https://www.overleaf.com/read/scczbbrcgbcj
Due Tuesday, April 2, 14:14.

# 7

Overleaf link: https://v2.overleaf.com/read/rrwpkbygvxvf
Due Tuesday, April 9, 14:14.

# 8

Overleaf link: https://v2.overleaf.com/read/whvfmvpsgqrv
Due Tuesday, April 16, 14:14.

# 9

Overleaf link: https://www.overleaf.com/read/fqwjtcwybvry
Due Tuesday, April 23, 14:14.

# 10

Overleaf link: https://v2.overleaf.com/read/bjxrmdxcdcyf
Due Tuesday, April 30, 14:14.

# 11

Overleaf link: https://v2.overleaf.com/read/gqvmtxkzcpng
Due Tuesday, May 7, 14:14.

# 12

Overleaf link: https://v2.overleaf.com/read/gdbcgxhycwxj
Due Tuesday, May 14, 14:14.

# 13

Overleaf link: https://v2.overleaf.com/read/mgjstxkthtgb
Due Tuesday, May 21, 14:14.

# 14

Overleaf link: https://www.overleaf.com/read/kkpfwxxzpjgb
Due Tuesday, May 28, 14:14.

Contact

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

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

Kvantarvutus 2018/19 kevad