Learning Quantum Circuits of Some T Gates

Abstract

In this paper, we study the problem of learning an unknown quantum circuit of a certain structure. If the unknown target is an <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula>-qubit Clifford circuit, we devise an efficient algorithm to reconstruct its circuit representation by using <inline-formula> <tex-math notation="LaTeX">$O(n^{2})$ </tex-math></inline-formula> queries to it. For decades, it has been unknown how to handle circuits beyond the Clifford group since the stabilizer formalism cannot be applied in this case. Herein, we study quantum circuits of <inline-formula> <tex-math notation="LaTeX">$T$ </tex-math></inline-formula>-depth one on the computational basis. We show that the output state of a <inline-formula> <tex-math notation="LaTeX">$T$ </tex-math></inline-formula>-depth one circuit can be represented by a stabilizer pseudomixture with a specific algebraic structure. Using Pauli and Bell measurements on copies of the output states, we can generate a hypothesis circuit that is equivalent to the unknown target circuit on computational basis states as input. If the number of <inline-formula> <tex-math notation="LaTeX">$T$ </tex-math></inline-formula> gates of the target is of the order <inline-formula> <tex-math notation="LaTeX">$O({\log n})$ </tex-math></inline-formula>, our algorithm requires <inline-formula> <tex-math notation="LaTeX">$O(n^{2})$ </tex-math></inline-formula> queries to it and produces its equivalent circuit representation on the computational basis in time <inline-formula> <tex-math notation="LaTeX">$O(n^{3})$ </tex-math></inline-formula>. Using further additional <inline-formula> <tex-math notation="LaTeX">$O(4^{3n})$ </tex-math></inline-formula> classical computations, we can derive an exact description of the target for arbitrary input states. Our results greatly extend the previously known facts that stabilizer states can be efficiently identified based on the stabilizer formalism.