Learning efficient decoders for quasi-chaotic 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^{\prime }$ that sandwich a local unitary operator $u_t$, i.e., $U_t=U_0{u}_t{U}_0^{\prime }$. 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 $\mathrm{poly}(n,2^t)$ resources.

Corrected the typos and emphasized several results on learning Clifford circuits that were previously overlooked in the previous version

References in corpus (20)

• Black holes as mirrors: quantum information in random subsystems
• Randomized Benchmarking of Quantum Gates
• Quantum Process Tomography: Resource Analysis of Different Strategies
• Chaos, Complexity, and Random Matrices
• Magic state distillation in all prime dimensions using quantum Reed-Muller codes
• Scalable measures of magic resource for quantum computers
• Measuring magic on a quantum processor
• Magic-state resource theory for the ground state of the transverse-field Ising model
• Scrambling and Complexity in Phase Space
• Nonstabilizerness determining the hardness of direct fidelity estimation
• Scalable reconstruction of unitary processes and Hamiltonians
• Conditional Mutual Information of Bipartite Unitaries and Scrambling
• Learning and Testing Algorithms for the Clifford Group
• Random Matrix Theory of the Isospectral twirling
• Unscrambling Quantum Information with Clifford decoders
• A single $T$-gate makes distribution learning hard
• Retrieving information from a black hole using quantum machine learning
• The Learnability of Quantum States
• Entanglement complexity of the Rokhsar-Kivelson-sign wavefunctions
• Clifford Circuits can be Properly PAC Learned if and only if $\text{RP}=\text{NP}$

Cited by in corpus (30)

• Nonstabilizerness via matrix product states in the Pauli basis
• Learning t-doped stabilizer states
• Pseudomagic Quantum States
• Unscrambling Quantum Information with Clifford decoders
• Learning quantum states and unitaries of bounded gate complexity
• Stabilizer entropy in non-integrable quantum evolutions
• Magic-induced computational separation in entanglement theory
• Bell sampling from quantum circuits
• Phase transition in Stabilizer Entropy and efficient purity estimation
• Magic of quantum hypergraph states
• Efficient mutual magic and magic capacity with matrix product states
• Stabilizer entropy of quantum tetrahedra
• Doped stabilizer states in many-body physics and where to find them
• Stabilizer Tensor Networks with Magic State Injection
• Efficient learning of quantum states prepared with few fermionic non-Gaussian gates
• Learning quantum states of continuous variable systems
• Bridging Entanglement and Magic Resources within Operator Space
• On Groups in the Qubit Clifford Hierarchy
• Interplay of entanglement structures and stabilizer entropy in spin models
• Disentangling magic states with classically simulable quantum circuits
• Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates
• Hayden-Preskill recovery in chaotic and integrable unitary circuit dynamics
• Optimal trace-distance bounds for free-fermionic states: Testing and improved tomography
• Non-Clifford Cost of Random Unitaries
• PAC-learning of free-fermionic states is NP-hard
• Harvesting stabilizer entropy and non-locality from a quantum field
• Adaptively secure unitary designs with constant non-Clifford cost
• Pseudoentanglement Ain't Cheap
• Disentangling quantum autoencoder
• The symplectic rank of non-Gaussian quantum states