Learning quantum circuits of T -depth one

In this paper, we study the problem of learning an unknown quantum circuit of a certain structure. If the unknown target is an n-qubit Clifford circuit, we devise an algorithm to reconstruct its circuit representation by using O(n2) queries to it. It is unknown for decades how to handle circuits beyond the Clifford group for which the stabilizer formalism cannot be applied. Herein, we study quantum circuits of T -depth one on the computational basis. We show that their output states can be represented by a certain stabilizer pseudomixture. By analyzing the algebraic structure of the stabilizer pseudomixture, we can generate a hypothesis circuit that is equivalent to the unknown target T -depth one quantum circuit U on computational basis states, using Pauli and Bell measurements. If the number of T gates in U is of the order O(log n), our algorithm requires O(n2) queries to U to produce its equivalent circuit representation on the computational basis in time O(n3). Using further additional O(43n) classical computations, we can derive an exact description of U for arbitrary input states. Our results greatly extend the previously known facts that stabilizer states can be efficiently identified based on the stabilizer formalism.The full manuscript can be found at [1].