Quantum magic is a crucial resource that enables quantum computation to surpass classical computation. While previous work has linked the amount of quantum magic—quantified by the number of non-Clifford (magic) gates—to classical simulability, the role of its distribution in affecting the complexity of classical simulations remains an open question. In this talk, I will present a comprehensive set of results on the complexity of simulating quantum circuits with one or two layers of magic gates. In particular, I will discuss how the structure of magic depth can be leveraged to design polynomial-time classical simulation algorithms. Finally, I will highlight the prevalence of shallow magic depth circuits in the literature, sometimes in unexpected contexts, highlighting the broad relevance of these results to the quantum information community.
Ref: Classical Simulability of Quantum Circuits with Shallow Magic Depth, arXiv:2409.13809 (accepted, PRX Quantum)