"Quantum algorithims"Последнее изменение: 06/10/2020 05:09:48Aim, scope, and prrequisites: The aim of this mini-course is to introduce basic quantum algorithms in an accessible but mathematically rigorous manner. As prerequisites, we assume the audience’s acquaintance with basic notions and results of the theory of unitary and Hermitian (self-conjugate) operators in finite-dimensional Hilbert spaces. No previous knowledge of quantum mechanics is required. Literature: The course is based on the textbook "An Introduction to Quantum Computing Algorithms" by Arthur Pittenger (Birkhäuser, 2000). Some materials (e.g., proof details) and useful links will be placed here after each lecture. Lecture 1: The Stern-Gerlach experiment and the matrix formalism of quantum mechanicsThe content of the lecture roughly corresponds to Chapter 1 of Pittenger's textbook. We started with a simplified but accurate in large description of the Stern-Gerlach experiment of 1922. The choice is caused by the following reasons:
Then we proceeded with presenting the matrix formalism of quantum mechanics. Finally, we returned to the Stern-Gerlach experiment and demonstrated how its results could be explained via the matrix formalism. We concluded with introducing the Dirac notation. Scott Aaronson's presentation partly used in the lecture. The original paper by Walther Gerlach und Otto Stern (in German!) - it is useful to have a look at it to see the difference between the real experiment and our simplified presentation. Also, I see a trace of historical irony in the authors' acknowledgement: they thank Einstein (as the Director of Kaiser Wilhelm Institute for Physics) for providing a crucial piece of equipment used for the experiment, and as it is well known, Einstein opposed quantum mechanics, even though he was awarded the Nobel prize for his work on photoelectricity, which certainly was quantum mechanical. Wikipedia page about the Stern-Gerlach experiment is quite substantial and contains nice illustrations (partly used in the lecture).
Proofs for some claims made in the lectureLecture 2: The Deutsch and Deutsch-Jozsa algorithmsThe lecture included the material in Section 3.1 of Pittenger's textbook but provided more details. We started with recalling the concepts of the tensor product of Hilbert spaces and Kronecker (tensor) product of matrices. We also introduced the Hadamard transform. The original paper by David Deutsch of 1985 The original paper by David Deutsch and Richard Jozsa of 1992 Lecture 3: The Simon and Grover algorithmsLecture 4: Shor's factorization algorithmLecture 5: Quantum teleportation |