"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 mechanics
The 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:
- the experiment is easy to explain;
- its results are counterintuitive and cannot be reasonably explained from the viewpoint of “classical” physics;
- it reveals quantum effects (such as the noncommutativity) in a very explicit way.
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).
| Finite-dimensional Hilbert space H | Quantum system |
| Non-negative operator R on H with trace 1 | State of the system |
| Self-conjugate operator A on H | Observable |
| Eigenvalues of A | Possible results of observation |
| tr(RA) | Expected result after an observation of A in the state R |
| Unitary operator on H | Transformation of the system |
Proofs for some claims made in the lecture
Lecture 2: The Deutsch and Deutsch-Jozsa algorithms
The 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 algorithms
Lecture 4: Shor's factorization algorithm
Lecture 5: Quantum teleportation