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 Uₓ can be decomposed into two Clifford circuits U₀, U₀^' that sandwich a local unitary operator uₓ, i. e. , Uₓ=U₀uₓU₀^'. The local unitary operator uₓ 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 Uₓ is O (n^2+t^3), and it admits a efficient process tomography using poly (n, 2^t) resources.