Abstract

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 .