11-20

Special Quantum Seminar - Why is it so hard to prove the limits of quantum circuits?

Although almost all quantum states require exponentially large quantum circuits to prepare, it remains a central challenge to prove that even very restricted circuits cannot prepare specific states. In this talk, I will describe the landscape of what we can currently prove about the limits of quantum circuits, known as circuit lower bounds. I will highlight some of the strongest known results, including my work introducing the magic hierarchy, a framework that unifies several circuit models, including those with intermediate measurements. I will also discuss my work on a quantum analogue of the natural proofs barrier, which identifies obstacles to extending existing lower-bound techniques to more powerful circuits.