Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2212.11338 · Physical Review A

Learning efficient decoders for quasichaotic quantum scramblers

Lorenzo Leone, Salvatore F. E. Oliviero, Seth Lloyd, Alioscia Hamma

Published Feb 22, 2024• 35 citations
arXivHTMLPDF

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.

DOI
10.1103/physreva.109.022429

Related papers

Efficient Learning of Clifford-Scrambled Product States

Tobias Haug

Clifford circuits acting on product magic states provide a compact ansatz exhibiting extensive magic, volume-law entanglement, and even classically hard sampling under standard complexity assumptions. Here, we efficiently recover its hidden product subsystems from two-copy Bell sampling. Quadratic relations between Bell samples determine the irreducible blocks after removing Pauli stabilizers, and binary linear algebra constructs a Clifford disentangler. For logarithmic-size blocks, approximate learning of the full state is efficient whenever the state remains inverse-polynomially separated from acquiring additional Pauli stabilizers. We efficiently learn $n$-qubit states prepared by random $T$-doped Clifford circuits with $T$-gate density below one via $O(n^2)$ Bell samples, and disentangle hidden product blocks in Clifford-augmented matrix product states. For unitary learning, we exactly learn $T$-depth-one circuits using $O(n^2)$ queries. Finally, we rule out pseudorandom states and unitaries with a product bipartition hidden by Clifford circuits.

quant-pharXiv:2609.27128•Sep 24, 2026•0 citations

Unscrambling Quantum Information with Clifford Decoders

Salvatore F. E. Oliviero, Lorenzo Leone, Seth Lloyd +1 more

Quantum information scrambling is a unitary process that destroys local correlations and spreads information throughout the system, effectively hiding it in nonlocal degrees of freedom. In principle, unscrambling this information is possible with perfect knowledge of the unitary dynamics [B. Yoshida and A. Kitaev, arXiv:1710.03363.]. However, this Letter demonstrates that even without previous knowledge of the internal dynamics, information can be efficiently decoded from an unknown scrambler by monitoring the outgoing information of a local subsystem. We show that rapidly mixing but not fully chaotic scramblers can be decoded using Clifford decoders. The essential properties of a scrambling unitary can be efficiently recovered, even if the process is exponentially complex. Specifically, we establish that a unitary operator composed of t non-Clifford gates admits a Clifford decoder up to t≤n.

arXiv:2212.11337•Physical Review Letters•Feb 22, 2024•31 citations

Efficient learning of Clifford disentanglers and typical $t$-doped unitaries with exponentially more $T$ gates

Gerard Aguilar, Sofiene Jerbi, Jens Eisert +1 more

Highly entangled and highly non-stabilizer quantum states need not be hard to learn. We give efficient algorithms for testing and recovering hidden tensor-product structure in unknown pure state vectors of the form $\lvertψ\rangle = U_C \bigotimes_i \lvertψ_i\rangle$, where $U_C$ is an arbitrary unknown Clifford unitary. Although the Clifford can thoroughly scramble the visible product structure, we prove that the Bell distribution retains a characteristic family of quadratic symmetries. By simultaneously block-diagonalising these symmetries, our algorithms linearize the problem and manage to recover both a disentangling Clifford and the hidden partitions with polynomial sample and computational complexity. This may be viewed as an extension of the abelian StateHSP paradigm in which classical post-processing exposes genuinely quadratic structure. Applied to Choi states, the method yields efficient proper learning algorithms for typical $t$-doped Clifford unitaries in regimes containing exponentially more $T$ gates than previously accessible: the required condition fails only for an exponentially small fraction of circuits when $t\sim n$, and continues to hold for a constant fraction even when $t=2n$. Our framework also provides tools for compressing structured many-body Hamiltonians and suggests benchmarking protocols for encoded logical product states in the early fault-tolerant regime.

quant-pharXiv:2609.27565•Sep 24, 2026•0 citations

Lecture Notes on Information Scrambling, Quantum Chaos, and Haar-Random States

Marcin Płodzień

Information scrambling, the process by which quantum information spreads and becomes effectively inaccessible, is central to modern quantum statistical physics and quantum chaos. These lecture notes provide an introduction to information scrambling from both static and dynamical perspectives. The spectral properties of reduced density matrices arising from Haar-random states are developed through the geometry of the unitary group and the universal results of random matrix theory. This geometric framework yields universal, model-independent predictions for entanglement and spectral statistics, capturing generic features of quantum chaos without reference to microscopic details. Dynamical diagnostics such as the spectral form factor and out-of-time-ordered correlators further reveal the onset of chaos in time-dependent evolution. The notes are aimed at advanced undergraduate and graduate students in physics, mathematics, and computer science who are interested in the connections between quantum chaos, information dynamics, and quantum computing. Concepts such as entanglement growth, Haar randomness, random-matrix statistics, and unitary t-designs are introduced through their realization in random quantum circuits and circuit complexity. The same mathematical framework also underpins modern quantum-device benchmarking, where approximate unitary designs and random circuits translate geometric ideas into quantitative tools for assessing fidelity, noise, and scrambling efficiency in real quantum processors.

quant-pharXiv:2511.14397•Nov 19, 2025•0 citations

Learning Clifford-structured quantum unitaries and Hamiltonians

Arkopal Dutt, Dale Jacobs, John Jeang +2 more

Learning algorithms for structured quantum unitaries and Hamiltonians have primarily considered classes of processes that are local or sparse in the Pauli basis. We turn our attention to learning $n$-qubit quantum unitaries $U$ and Hamiltonians $H$, given query access to $U$ or the unitary evolution of $H$, that may be dense in the Pauli basis but still admit concise Clifford decompositions. Specifically, we consider unitaries (or Hamiltonians) of the form $U = \sum_i α_i C_i$ over Cliffords $C_i$ with bounded Clifford extent $\sum_i |α_i|$. To extract this Clifford structure, we introduce an agnostic tomography protocol for Clifford unitaries that given query access to an unknown unitary $U$ with optimal Clifford fidelity $\textsf{opt}$, outputs a Clifford unitary witnessing fidelity $\geq \textsf{opt} - \varepsilon$ for some error $\varepsilon > 0$, in time $\textsf{poly}(n,(1/\varepsilon)^{\log(1/\varepsilon)})$. We then apply this protocol to obtain tomography protocols for unitaries and Hamiltonians that have bounded Clifford extent. This extends learnability of Hamiltonians from those with sparse Pauli decompositions to those that are dense (i.e., has sparsity $Ω(2^n)$) in the Pauli basis but are Clifford structured.

quant-pharXiv:2608.09912•Aug 11, 2026•0 citations

Foundations for learning from noisy quantum experiments

Hsin-Yuan Huang, Steven T. Flammia, John P. Preskill

Understanding what can be learned from experiments is central to scientific progress. In this work, we use a learning-theoretic perspective to study the task of learning physical operations in a quantum machine when all operations (state preparation, dynamics, and measurement) are a priori unknown. We prove that, without any prior knowledge, if one can explore the full quantum state space by composing the operations, then every operation can be learned. When one cannot explore the full state space but all operations are approximately known and noise in Clifford gates is gate-independent, we find an efficient algorithm for learning all operations up to a single unlearnable parameter characterizing the fidelity of the initial state. For learning a noise channel on Clifford gates to a fixed accuracy, our algorithm uses quadratically fewer experiments than previously known protocols. Under more general conditions, the true description of the noise can be unlearnable; for example, we prove that no benchmarking protocol can learn gate-dependent Pauli noise on Clifford+T gates even under perfect state preparation and measurement. Despite not being able to learn the noise, we show that a noisy quantum computer that performs entangled measurements on multiple copies of an unknown state can yield a large advantage in learning properties of the state compared to a noiseless device that measures individual copies and then processes the measurement data using a classical computer. Concretely, we prove that noisy quantum computers with two-qubit gate error rate $ε$ can achieve a learning task using $N$ copies of the state, while $N^{Ω(1/ε)}$ copies are required classically.

arXiv:2204.13691•Apr 28, 2022•4 citations
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 ttt-doped Clifford circuits, i.e., Clifford circuits containing ttt non-Clifford gates, their gate complexity, and learnability that are of independent interest. In particular, we show that a ttt-doped Clifford circuit Ut{U}_{t}Ut​ can be decomposed into two Clifford circuits U0,U0\ensuremath′{U}_{0},{U}_{0}^{\ensuremath{'}}U0​,U0\ensuremath′​ that sandwich a local unitary operator ut{u}_{t}ut​, i.e., Ut=U0utU0\ensuremath′{U}_{t}={U}_{0}{u}_{t}{U}_{0}^{\ensuremath{'}}Ut​=U0​ut​U0\ensuremath′​. The local unitary operator ut{u}_{t}ut​ contains ttt non-Clifford gates and acts nontrivially on at most ttt qubits. As simple corollaries, the gate complexity of the ttt-doped Clifford circuit Ut{U}_{t}Ut​ is O(n2+t3)O({n}^{2}+{t}^{3})O(n2+t3), and it admits a efficient process tomography using poly(n,2t)poly(n,{2}^{t})poly(n,2t) resources.
Clifford circuits acting on product magic states provide a compact ansatz exhibiting extensive magic, volume-law entanglement, and even classically hard sampling under standard complexity assumptions. Here, we efficiently recover its hidden product subsystems from two-copy Bell sampling. Quadratic relations between Bell samples determine the irreducible blocks after removing Pauli stabilizers, and binary linear algebra constructs a Clifford disentangler. For logarithmic-size blocks, approximate learning of the full state is efficient whenever the state remains inverse-polynomially separated from acquiring additional Pauli stabilizers. We efficiently learn nnn-qubit states prepared by random TTT-doped Clifford circuits with TTT-gate density below one via O(n2)O(n^2)O(n2) Bell samples, and disentangle hidden product blocks in Clifford-augmented matrix product states. For unitary learning, we exactly learn TTT-depth-one circuits using O(n2)O(n^2)O(n2) queries. Finally, we rule out pseudorandom states and unitaries with a product bipartition hidden by Clifford circuits.
Quantum information scrambling is a unitary process that destroys local correlations and spreads information throughout the system, effectively hiding it in nonlocal degrees of freedom. In principle, unscrambling this information is possible with perfect knowledge of the unitary dynamics [B. Yoshida and A. Kitaev, arXiv:1710.03363.]. However, this Letter demonstrates that even without previous knowledge of the internal dynamics, information can be efficiently decoded from an unknown scrambler by monitoring the outgoing information of a local subsystem. We show that rapidly mixing but not fully chaotic scramblers can be decoded using Clifford decoders. The essential properties of a scrambling unitary can be efficiently recovered, even if the process is exponentially complex. Specifically, we establish that a unitary operator composed of t non-Clifford gates admits a Clifford decoder up to t≤n.
Efficient learning of Clifford disentanglers and typical ttt-doped unitaries with exponentially more TTT gates
Highly entangled and highly non-stabilizer quantum states need not be hard to learn. We give efficient algorithms for testing and recovering hidden tensor-product structure in unknown pure state vectors of the form ∣ψ⟩=UC⨂i∣ψi⟩\lvertψ\rangle = U_C \bigotimes_i \lvertψ_i\rangle∣ψ⟩=UC​⨂i​∣ψi​⟩, where UCU_CUC​ is an arbitrary unknown Clifford unitary. Although the Clifford can thoroughly scramble the visible product structure, we prove that the Bell distribution retains a characteristic family of quadratic symmetries. By simultaneously block-diagonalising these symmetries, our algorithms linearize the problem and manage to recover both a disentangling Clifford and the hidden partitions with polynomial sample and computational complexity. This may be viewed as an extension of the abelian StateHSP paradigm in which classical post-processing exposes genuinely quadratic structure. Applied to Choi states, the method yields efficient proper learning algorithms for typical ttt-doped Clifford unitaries in regimes containing exponentially more TTT gates than previously accessible: the required condition fails only for an exponentially small fraction of circuits when t∼nt\sim nt∼n, and continues to hold for a constant fraction even when t=2nt=2nt=2n. Our framework also provides tools for compressing structured many-body Hamiltonians and suggests benchmarking protocols for encoded logical product states in the early fault-tolerant regime.
Information scrambling, the process by which quantum information spreads and becomes effectively inaccessible, is central to modern quantum statistical physics and quantum chaos. These lecture notes provide an introduction to information scrambling from both static and dynamical perspectives. The spectral properties of reduced density matrices arising from Haar-random states are developed through the geometry of the unitary group and the universal results of random matrix theory. This geometric framework yields universal, model-independent predictions for entanglement and spectral statistics, capturing generic features of quantum chaos without reference to microscopic details. Dynamical diagnostics such as the spectral form factor and out-of-time-ordered correlators further reveal the onset of chaos in time-dependent evolution. The notes are aimed at advanced undergraduate and graduate students in physics, mathematics, and computer science who are interested in the connections between quantum chaos, information dynamics, and quantum computing. Concepts such as entanglement growth, Haar randomness, random-matrix statistics, and unitary t-designs are introduced through their realization in random quantum circuits and circuit complexity. The same mathematical framework also underpins modern quantum-device benchmarking, where approximate unitary designs and random circuits translate geometric ideas into quantitative tools for assessing fidelity, noise, and scrambling efficiency in real quantum processors.
Learning algorithms for structured quantum unitaries and Hamiltonians have primarily considered classes of processes that are local or sparse in the Pauli basis. We turn our attention to learning nnn-qubit quantum unitaries UUU and Hamiltonians HHH, given query access to UUU or the unitary evolution of HHH, that may be dense in the Pauli basis but still admit concise Clifford decompositions. Specifically, we consider unitaries (or Hamiltonians) of the form U=∑iαiCiU = \sum_i α_i C_iU=∑i​αi​Ci​ over Cliffords CiC_iCi​ with bounded Clifford extent ∑i∣αi∣\sum_i |α_i|∑i​∣αi​∣. To extract this Clifford structure, we introduce an agnostic tomography protocol for Clifford unitaries that given query access to an unknown unitary UUU with optimal Clifford fidelity opt\textsf{opt}opt, outputs a Clifford unitary witnessing fidelity ≥opt−ε\geq \textsf{opt} - \varepsilon≥opt−ε for some error ε>0\varepsilon > 0ε>0, in time poly(n,(1/ε)log⁡(1/ε))\textsf{poly}(n,(1/\varepsilon)^{\log(1/\varepsilon)})poly(n,(1/ε)log(1/ε)). We then apply this protocol to obtain tomography protocols for unitaries and Hamiltonians that have bounded Clifford extent. This extends learnability of Hamiltonians from those with sparse Pauli decompositions to those that are dense (i.e., has sparsity Ω(2n)Ω(2^n)Ω(2n)) in the Pauli basis but are Clifford structured.
Understanding what can be learned from experiments is central to scientific progress. In this work, we use a learning-theoretic perspective to study the task of learning physical operations in a quantum machine when all operations (state preparation, dynamics, and measurement) are a priori unknown. We prove that, without any prior knowledge, if one can explore the full quantum state space by composing the operations, then every operation can be learned. When one cannot explore the full state space but all operations are approximately known and noise in Clifford gates is gate-independent, we find an efficient algorithm for learning all operations up to a single unlearnable parameter characterizing the fidelity of the initial state. For learning a noise channel on Clifford gates to a fixed accuracy, our algorithm uses quadratically fewer experiments than previously known protocols. Under more general conditions, the true description of the noise can be unlearnable; for example, we prove that no benchmarking protocol can learn gate-dependent Pauli noise on Clifford+T gates even under perfect state preparation and measurement. Despite not being able to learn the noise, we show that a noisy quantum computer that performs entangled measurements on multiple copies of an unknown state can yield a large advantage in learning properties of the state compared to a noiseless device that measures individual copies and then processes the measurement data using a classical computer. Concretely, we prove that noisy quantum computers with two-qubit gate error rate εεε can achieve a learning task using NNN copies of the state, while NΩ(1/ε)N^{Ω(1/ε)}NΩ(1/ε) copies are required classically.