Quantum Computing

2022 Fall course at the Eötvös Loránd University, Budapest

(Neptun course codes -- Math MSc: qtcomp1u1_m22vx; Computer Science PhD: INFPHD639EN-N; Math PhD: MAT/471)

Lecturer: András Gilyén

The course is organized as part of the QTEdu Master pilot and the material is based on Ronald de Wolf's lectures. Ronald's lecture notes and course decription:

Today's computers---both in theory (Turing machines) and practice (PCs and smart phones)---are based on classical physics. However, modern quantum physics tells us that the world behaves quite differently. A quantum system can be in a superposition of many different states at the same time, and can exhibit interference effects during the course of its evolution. Moreover, spatially separated quantum systems may be entangled with each other and operations may have "non-local" effects because of this. Quantum computation is the field that investigates the computational power and other properties of computers based on quantum-mechanical principles. Its main building block is the qubit which, unlike classical bits, can take both values 0 and 1 at the same time, and hence affords a certain kind of parallelism. The laws of quantum mechanics constrain how we can perform computational operations on these qubits, and thus determine how efficiently we can solve a certain computational problem. Quantum computers generalize classical ones and hence are at least as efficient. However, the real aim is to find computational problems where a quantum computer is much more efficient than classical computers. For example, Peter Shor in 1994 found a quantum algorithm that can efficiently factor large integers into their prime factors. This problem is generally believed to take exponential time on even the best classical computers, and its assumed hardness forms the basis of much of modern cryptography (particularly the widespread RSA system). Shor's algorithm breaks all such cryptography. A second important quantum algorithm is Grover's search algorithm, which searches through an unordered search space quadratically faster than is possible classically. In addition to such algorithms, there is a plethora of other applications: quantum cryptography, quantum communication, simulation of physical systems, and many others.

The course is taught from a mathematical and theoretical computer science perspective, but should be accessible for physicists as well.

Prerequisites: Familiarity with basic linear algebra, probability theory, discrete math, algorithms, all at the level of a first Bachelor's course. Also general mathematical maturity: knowing how to write down a proof properly and completely.

Lectures & location:

The course is taught in English and consitst of a two-hour lecture and also a two-hour exercise class per week held in the Southern Block of ELTE's Lágymányos Campus. (NB You need to sign up for both the lecture and exercise classes in Neptun.) The lecture is on Tuesdays from 14:10 to 15:50 in room 3-517 and the exercise class is from 16:00-17:30 in seminar room 3-218.

Homework and Grading:

There is graded homework exercises for each week. The final grade will come from a weighted combination of the homeworks (1/3) and the final exam (2/3). The weekly homework is due before the start of the following lecture. You can either send the solutions electroincally as a pdf file or hand in the written solution at the start of the exercise class. When computing the average grade for the homeworks, the two lowest scores will be dropped. This is also meant to cover cases of illness etc.; in general no extension is allowed for homework submission. Cooperation among students is allowed, but everyone has to hand in their own solution set in their own words. Do not share files before the homework deadline, and never put the solutions online. Plagiarism will not be tolerated. You can find the current homework grades here.

Note that Appendix C of Ronald's lecture notes has hints for some of the exercises, indicated by (H). If the hint gives you some facts (for instance that there exists an efficient classical algorithm for testing if a given number is prime) then you can use these facts in your answer without proving/deriving these facts themselves.

Class Schedule:

  1. Tuesday September 13: Lecture -- Introduction (Chapter 1 of the lecture notes)
    Note: Make sure you know the material in Appendices A and B of the lecture notes before next week's lecture!

  2. Tuesday September 20, 14:10-15:50 (room LD-3-517): Lecture -- The circuit model of quantum computation & the Deutsch-Jozsa algorithm (Chapter 2)
    16:00-17:30 (room LD-3-218): Exercise class

  3. Tuesday September 27, 14:10-15:50 (room LD-3-517): Lecture -- Simon's algorithm (Chapter 3) -- homework due at the beginning of the class: Exercises 4, 6, 10, 12 of Chapter 1
    16:00-17:30 (room LD-3-218): Exercise class

  4. Tuesday October 11, 14:10-15:50 (room LD-3-517): Lecture -- Quantum Fourier transform (Chapter 4) -- homework due at the beginning of the class: Exercises 5, 9 of Chapter 2 and Exercises 1, 3 of Chapter 3
    16:00-17:30 (room LD-3-218): Exercise class

  5. Tuesday October 18, 14:10-15:50 (room LD-3-517): Lecture -- Shor's factoring algorithm (Chapter 5) -- homework due at the beginning of the class: Exercises 1, 3, 4 of Chapter 4
    16:00-17:30 (room LD-3-218): Exercise class

  6. Tuesday October 25, 14:10-15:50 (room LD-3-517): Lecture -- Grover's search algorithm and quantum walks (Chapter 7-8) -- homework due at the beginning of the class: Exercises 2, 3 of Chapter 5
    16:00-17:30 (room LD-3-218): Exercise class

    Tuesday November 1, No Class (All Saints' Day)

  7. Tuesday November 8, 14:10-15:50 (room LD-3-517): Lecture -- Hamiltonian simulation, HHL, and QSVT (Chapter 9-10) -- homework due at the beginning of the class: Homeworks Nr.5
    16:00-17:30 (room LD-3-218): Exercise class

    Tuesday November 15, No Class

    Tuesday November 22, No Class

  8. Tuesday November 29, 14:10-15:50 (room LD-3-517): Lecture -- QSVT and its applications -- homework due at the beginning of the class: Homeworks Nr.6
    16:00-17:30 (room LD-3-218): Exercise class

  9. Tuesday December 6, 14:00-15:30 (Rényi Institute, "Dog room" (Kutyás terem)): Lecture -- Quantum complexity theory + Non-local games -- homework due at the beginning of the class: Homeworks Nr.7
    15:45-17:10 (Rényi Institute, Dog room (kutyás terem)): Exercise class

  10. Tuesday January 10, 14:00: Last bonus homework due date: Homeworks Nr.8