Abstract
In this talk, we study quantum computing through the lens of the minimum circuit size problem (MCSP). In particular, we start by defining problems of computing quantum circuit complexity of Boolean functions, unitaries, and quantum states. Then, we will explore their hardness, the relations between the three quantum MCSPs and their variants, and their connections to quantum cryptography, quantum learning theory, quantum circuit lower bounds, and quantum fine-grained complexity. Due to the fundamental differences between classical and quantum circuits, most results require extra care and reveal properties and phenomena unique to the quantum setting. The talk will be mainly based on [arXiv 2108.03171], and we will also discuss recent attempts to connect quantum meta-complexity problems to quantum primitives.