Learning Shallow Quantum Circuits with Many-Qubit Gates

Abstract

The seminal work of [LMN’93] established a cornerstone result for classical complexity, with profound implications for learning theory. By proving low-degree Fourier concentration of AC0, the work demonstrated that Boolean functions computed by constant-depth circuits can be efficiently PAC-learned via low-degree Fourier sampling. This breakthrough provided the first sample- and time-efficient (quasi-polynomial) algorithm for learning AC0. Proposed by [Moore’99] as a natural quantum analog of AC0, QAC0 is the class of constant-depth quantum circuits composed of arbitrary single-qubit gates and polynomial $CZ$ gates of unbounded width. In this work, we present the first algorithm for efficient average-case learning of QAC0 circuits with logarithmic ancilla. Namely, our algorithm achieves quasi-polynomial sample- and time-complexity for learning unknown QAC0 unitaries to inverse-polynomially small error. We further show that these learned unitaries can be efficiently synthesized via poly-logarithmic depth circuits, making progress towards proper learning of QAC0. Since in finite-dimensional circuit geometries QAC0 circuits require polynomial depth to implement, this result significantly expands the family of efficiently learnable quantum circuits.