Learning efficient decoders for quasichaotic quantum scramblers

Abstract

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

Topics & Concepts