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)
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.
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.
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.
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.