Learning beyond Cliffords: circuits and states

Abstract

Learning unknown quantum circuits and states are ubiquitous tasks in quantum information theory. A well-known result is that Clifford circuits and states produced by these circuits (i.e., stabilizer states) are learnable in polynomial time. Stabilizer states and Clifford circuits are known to be classical simulable using the Gottesman-Knill framework which is crucial in these learning procedures. It is widely open how to learn states or circuits beyond the Clifford group. In this submission: 1) we give optimal bounds for learning states produced by the d-th level of the diagonal Clifford hierarchy, using separable and entangled measurements; (2) using the extended Gottesman formalism, we show how to learn in polynomial time a circuit with T-depth one consisting of O(log n) many T gates.