Learning efficient decoders for quasichaotic quantum scramblers

Scrambling of quantum information is an important feature at the root of randomization and benchmarking protocols, the onset of quantum chaos, and black-hole physics. Unscrambling this information is possible given perfect knowledge of the scrambler [arXiv:1710.03363]. We show that one can retrieve the scrambled information even without any previous knowledge of the scrambler, by a learning algorithm that allows the building of an efficient decoder. Remarkably, the decoder is classical in the sense that it can be efficiently represented on a classical computer as a Clifford operator. It is striking that a classical decoder can retrieve with fidelity one all the information scrambled by a random unitary that cannot be efficiently simulated on a classical computer, as long as there is no full-fledged quantum chaos. This result shows that one can learn the salient properties of quantum unitaries in a classical form and sheds a new light on the meaning of quantum chaos. Furthermore, we obtain results concerning the algebraic structure of t-doped Clifford circuits, i.e., Clifford circuits containing t non-Clifford gates, their gate complexity, and learnability that are of independent interest. In particular, we show that a t-doped Clifford circuit Ut can be decomposed into two Clifford circuits U0,U0′ that sandwich a local unitary operator ut, i.e., Ut=U0utU0′. The local unitary operator ut contains t non-Clifford gates and acts nontrivially on at most t qubits. As simple corollaries, the gate complexity of the t-doped Clifford circuit Ut is O(n2+t3), and it admits a efficient process tomography using poly(n,2t) resources.