Learning Shallow Quantum Circuits

Abstract.

Despite fundamental interests in learning quantum circuits, the existence of a computationally efficient algorithm for learning shallow quantum circuits remains an open question. Because shallow quantum circuits can generate distributions that are classically hard to sample from, existing learning algorithms do not apply. In this work, we present a polynomial-time classical algorithm for learning the description of any unknown [Formula: see text]-qubit shallow quantum circuit [Formula: see text] (with arbitrary unknown architecture) within a small diamond distance using single-qubit measurement data on the output states of [Formula: see text]. We also provide a polynomial-time classical algorithm for learning the description of any unknown [Formula: see text]-qubit state [Formula: see text] prepared by a shallow quantum circuit [Formula: see text] (on a 2D lattice) within a small trace distance using single-qubit measurements on copies of [Formula: see text]. Our approach uses a quantum circuit representation based on local inversions and a technique to combine these inversions. This circuit representation yields an optimization landscape that can be efficiently navigated and enables efficient learning of quantum circuits that are classically hard to simulate.