In this talk, I will describe the first computationally-efficient algorithm for average-case learning of shallow quantum circuits with many-qubit gates. Specifically, leveraging prior results on Pauli concentration of QAC0 [NPVY'24] and efficient learning of QNC0 circuits [HLB+'24], we provide a quasi-polynomial sample- and time-complexity algorithm for learning a full unitary description of unknown QAC0 circuits (with at most logarithmic ancilla) up to inverse-polynomially small error. As time permits, I will discuss interesting open questions following from the work, such as: using PRUs to prove optimality of learning, the possibility of efficient proper learning of QAC0, and general connections to the number of ancilla required to compute Parity in QAC0.
The talk is based on the paper [arXiv:2410.16693], joint work with Robert Huang, to appear at COLT 2025.
