Speaker
Description
Shallow quantum circuits lie at the forefront of modern experimental capabilities and theoretical understanding. In this work, we present the first computationally-efficient algorithm for average-case learning of a class of shallow circuits with many-qubit gates. Namely, we provide a quasipolynomial sample and time complexity algorithm for learning 1/poly(n)-approximate unitaries of QAC^0 circuits, i.e., constant-depth circuits with arbitrary single-qubit gates and polynomially many CZ gates of un-bounded width. Note that QAC^0 implements circuits requiring linear-depth in the 1D geometry and
logarithmic-depth in the all-to-all-connected geometry of constant-width gates. Furthermore, leveraging our learned QAC0 unitaries, we provide an efficient algorithm for circuit synthesis of poly-logarithmic depth QAC circuits, making progress towards a quasipolynomial proper-learning algorithm for QAC0.
