In recent years we have witnessed unprecedented progress in quantum computing, both on the side of theory, as well as in experimental implementations. Thanks to this, quantum computing got a lot of attention and enthusiasm in the media around the world. However, a deep understanding of the recent developments is challenging as the relevant results are scattered across numerous papers that rely on a combination of advanced techniques from physics, mathematics, and computer science.

Our objective of this monograph lecture is to provide a self-contained and rigorous introduction to some of the most important theoretical findings in quantum computing. The main focus will be put on explaining the paradigm of quantum advantage (supremacy) and its recent experimental demonstration by the collaboration of Google and the University of Santa Barbara. Specifically, we will present the complexity-theoretic underpinnings of quantum supremacy experiments and discuss the main techniques for efficient classical simulation of quantum computers. Along the way, we will introduce several useful tools and techniques that find applications throughout quantum information and quantum computing.

A tentative list of subjects we intend to cover:

• Basics of classical and quantum complexity theory
• Compilation of quantum gates
• Unitary t-designs and their applications
• Quantum advantage (supremacy) proposals: from theoretical foundations to experimental realization
• Techniques for efficient classical simulation of quantum computation

Some of the group-theoretic concepts used in this lecture will be covered with more details by the “Mathematical Physics I-compact groups and their representations” lecture which we recommend.

List of lectures