(in Polish) Mathematics of quantum computing: from pseudorandomness to quantum computational advantage 1100-MAC
The purpose of this course is to give a conceptual and rigorous introduction to quantum computing. We will present mathematical techniques useful for studying the transition from classical simulability to quantum advantage as the size and complexity of a quantum computer grow. The central theme of the lectures will be quantum pseudorandomness captured by the notion of unitary t-designs. We will present constructions of unitary t-designs and cover basic applications of this concept in benchmarking, tomography, complexity growth in random quantum circuits, and proposals for quantum computational supremacy. We will also cover some techniques to efficiently simulate restricted forms of quantum computation, despite presence of entanglement and nonclassical correlations.
Specific topics we intend to cover:
1. Basic concepts in quantum computing
2. Introduction to classical complexity theory (complexity classes P, NP, BPP, BQP)
3. Definition and constructions of unitary t- designs
4. Applications of t-designs
- Randomized benchmarking
- Shadow tomography
- Complexity growth in random quantum circuits
- Anti-concentration in quantum supremacy proposals
5. Classical simulation of restricted forms of quantum computing
6. Theory of quantum supremacy experiments
Course coordinators
Additional information
Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system: