Ruizhe Zhang, The University of Texas at Austin
MCSP is a problem to compute the circuit complexity of Boolean functions. It is a fascinating problem in complexity theory — its hardness is mysterious, and a better understanding of its hardness can have surprising implications to many fields in computer science. In this talk, I will introduce the study of MCSP in the quantum settings. I will first define and investigate the basic complexity-theoretic properties of minimum quantum circuit size problems for Boolean functions, and systematically generalize results known for classical MCSP to the quantum setting (including quantum cryptography, quantum learning theory, quantum circuit lower bounds, and quantum fine-grained complexity). Next, I will introduce the minimum quantum circuit size problems for quantum objects (unitaries and quantum states), which have some reductions that are not known for classical MCSP, e.g., search-to-decision reduction and self-reduction. They also have some connections to tomography and quantum gravity. Due to the fundamental differences between classical and quantum circuits, most of our results require extra care and reveal properties and phenomena unique to the quantum setting.
This is joint work with Nai-Hui Chia, Chi-Ning Chou, and Jiayu Zhang (arXiv:2108.03171).
Recording of the talk