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:2410.21268 · Nature Communications

Pseudochaotic many-body dynamics as a pseudorandom state generator

Wonjun Lee, Hyukjoon Kwon, Gil Young Cho

Published Jul 23, 2025• 2 citations
arXivHTMLPDF

Abstract

Quantum chaos is central to understanding quantum dynamics and is crucial for generating random quantum states, a key resource for quantum information tasks. In this work, we introduce a new class of quantum many-body dynamics, termed pseudochaotic dynamics. Although distinct from chaotic dynamics, out-of-time-ordered correlators, the key indicators of quantum chaos, fail to distinguish them. Moreover, pseudochaotic dynamics generates pseudorandom states that are computationally indistinguishable from Haar-random states. We construct pseudochaotic dynamics by embedding a smaller k-qubit subsystem into a larger n-qubit system. We demonstrate that a subsystem of size $$k=\omega (\log n)$$ is sufficient to induce pseudochaotic behavior in the entire n-qubit system. Furthermore, we construct a quantum circuit exhibiting pseudochaotic dynamics and demonstrate that it generates pseudorandom states within $${{{\rm{polylog}}}}(n)$$ depth. In summary, our results constitute the discovery of new quantum dynamics that are computationally indistinguishable from genuine quantum chaos, which provides efficient routes to generate useful pseudorandom states. Recent work introduced pseudorandom quantum states, indistinguishable from truly random states by any polynomial-time algorithm. Here the authors propose pseudochaotic many-body dynamics, which is indistinguishable from chaotic dynamics and can generate pseudorandom states using polylogarithmic-depth circuits.

DOI
10.1038/s41467-025-62081-6

Related papers

Simulating quantum chaos without chaos

Andi Gu, Yihui Quek, Susanne F. Yelin +2 more

Quantum chaos is a quantum many-body phenomenon that is associated with a number of intricate properties, such as level repulsion in energy spectra or distinct scalings of out-of-time ordered correlation functions. In this work, we introduce a novel class of "pseudochaotic" quantum Hamiltonians that fundamentally challenges the conventional understanding of quantum chaos and its relationship to computational complexity. Our ensemble is computationally indistinguishable from the Gaussian unitary ensemble (GUE) of strongly-interacting Hamiltonians, widely considered to be a quintessential model for quantum chaos. Surprisingly, despite this effective indistinguishability, our Hamiltonians lack all conventional signatures of chaos: it exhibits Poissonian level statistics, low operator complexity, and weak scrambling properties. This stark contrast between efficient computational indistinguishability and traditional chaos indicators calls into question fundamental assumptions about the nature of quantum chaos. We, furthermore, give an efficient quantum algorithm to simulate Hamiltonians from our ensemble, even though simulating Hamiltonians from the true GUE is known to require exponential time. Our work establishes fundamental limitations on Hamiltonian learning and testing protocols and derives stronger bounds on entanglement and magic state distillation. These results reveal a surprising separation between computational and information-theoretic perspectives on quantum chaos, opening new avenues for research at the intersection of quantum chaos, computational complexity, and quantum information. Above all, it challenges conventional notions of what it fundamentally means to actually observe complex quantum systems.

arXiv:2410.18196•Oct 23, 2024•0 citations

Efficient Quantum Pseudorandomness

Fernando G. S. L. Brandão, Aram W. Harrow, Michał Horodecki

Randomness is both a useful way to model natural systems and a useful tool for engineered systems, e.g., in computation, communication, and control. Fully random transformations require exponential time for either classical or quantum systems, but in many cases pseudorandom operations can emulate certain properties of truly random ones. Indeed, in the classical realm there is by now a well-developed theory regarding such pseudorandom operations. However, the construction of such objects turns out to be much harder in the quantum case. Here, we show that random quantum unitary time evolutions ("circuits") are a powerful source of quantum pseudorandomness. This gives for the first time a polynomial-time construction of quantum unitary designs, which can replace fully random operations in most applications, and shows that generic quantum dynamics cannot be distinguished from truly random processes. We discuss applications of our result to quantum information science, cryptography, and understanding the self-equilibration of closed quantum dynamics.

arXiv:1605.00713•Physical Review Letters•Apr 29, 2016•51 citations

Near-Term Pseudorandom and Pseudoresource Quantum States

Andrew Tanggara, Mile Gu, Kishor Bharti

A pseudorandom quantum state (PRS) is an ensemble of quantum states indistinguishable from Haar-random states to observers with efficient quantum computers. It allows one to substitute the costly Haar-random state with efficiently preparable PRS as a resource for cryptographic protocols, while also finding applications in quantum learning theory, black hole physics, many-body thermalization, quantum foundations, and quantum chaos. All existing constructions of PRS equate the notion of efficiency to quantum computers which runtime is bounded by a polynomial in its input size. In this work, we relax the notion of efficiency for PRS with respect to observers with near-term quantum computers implementing algorithms with runtime that scales slower than polynomial-time. We introduce the $\mathbf{T}$-PRS which is indistinguishable to quantum algorithms with runtime $\mathbf{T}(n)$ that grows slower than polynomials in the input size $n$. We give a set of reasonable conditions that a $\mathbf{T}$-PRS must satisfy and give two constructions by using quantum-secure pseudorandom functions and pseudorandom functions. For $\mathbf{T}(n)$ being linearithmic, linear, polylogarithmic, and logarithmic function, we characterize the amount of quantum resources a $\mathbf{T}$-PRS must possess, particularly on its coherence, entanglement, and magic. Our quantum resource characterization applies generally to any two state ensembles that are indistinguishable to observers with computational power $\mathbf{T}(n)$, giving a general necessary condition of whether a low-resource ensemble can mimic a high-resource ensemble, forming a $\mathbf{T}$-pseudoresource pair. We demonstate how the necessary amount of resource decreases as the observer's computational power is more restricted, giving a $\mathbf{T}$-pseudoresource pair with larger resource gap for more computationally limited observers.

arXiv:2504.17650•Apr 24, 2025•0 citations

Machine learning, quantum chaos, and pseudorandom evolution

Daniel W. F. Alves, Michael O. Flynn

By modeling quantum chaotic dynamics with ensembles of random operators, we explore how machine learning algorithms can be used to detect pseudorandom behavior in qubit systems. We analyze samples consisting of pieces of correlation functions and find that machine learning algorithms are capable of determining the degree of pseudorandomness which a system is subject to in a precise sense. This is done without computing any correlators explicitly. Interestingly, even samples drawn from two-point functions are found to be sufficient to solve this classification problem. This presents the possibility of using deep learning algorithms to explore late time behavior in chaotic quantum systems which have been inaccessible to simulation.

arXiv:1808.10498•Physical Review A•May 27, 2020•3 citations

Fast Computational Deep Thermalization

Shantanav Chakraborty, Soonwon Choi, Soumik Ghosh +1 more

Deep thermalization refers to the emergence of Haar-like randomness from quantum systems upon partial measurements. As a generalization of quantum thermalization, it is often associated with high complexity and entanglement. Here, we introduce computational deep thermalization and construct the fastest possible dynamics exhibiting it at infinite effective temperature. Our circuit dynamics produce quantum states with low entanglement in polylogarithmic depth that are indistinguishable from Haar random states to any computationally bounded observer. Importantly, the observer is allowed to request many copies of the same residual state obtained from partial projective measurements on the state-this condition is beyond the standard settings of quantum pseudorandomness but natural for deep thermalization. In cryptographic terms, these states are pseudorandom and pseudoentangled, and crucially, they retain these properties under local measurements. Our results demonstrate a new form of computational thermalization in which thermal-like behavior arises from structured quantum states endowed with cryptographic properties instead of from highly unstructured ensembles. The low resource complexity of preparing these states suggests scalable simulations of deep thermalization using quantum computers. Our Letter also motivates the study of computational quantum pseudorandomness beyond BQP observers.

arXiv:2507.13670•Physical Review Letters•Nov 20, 2025•2 citations

Chaos and Randomness in Strongly-Interacting Quantum Systems

Nicholas Hunter-Jones

Quantum chaos entails an entropic and computational obstruction to describing a system and thus is intrinsically difficult to characterize. An understanding of quantum chaos is fundamentally related to the mechanism of thermalization in many-body systems and the quantum nature of black holes. In this thesis we adopt the view that quantum information theory provides a powerful framework in which to elucidate chaos in strongly-interacting quantum systems. We first push towards a more precise understanding of chaotic dynamics by relating different diagnostics of chaos, studying the time-evolution of random matrix Hamiltonians, and quantifying random matrix behavior in physical systems. We derive relations between out-of-time ordered correlation functions, spectral quantities, and frame potentials to relate the scrambling of quantum information, decay of correlators, and Haar-randomness. We give analytic expressions for these quantities in random matrix theory to explore universal aspects of late-time dynamics. Motivated by our random matrix results, we define k-invariance in order to capture the onset of random matrix behavior in physical systems. We then refine our diagnostics in order to study chaotic systems with symmetry by considering Haar-randomness with respect to quotients of the unitary group, and in doing so we generalize our quantum information machinery. We further consider extended random matrix ensembles in the context of strongly-interacting quantum systems dual to black holes. Lastly, we study operator growth in classes of random quantum circuits.

•Jun 4, 2018•12 citations
Quantum chaos is central to understanding quantum dynamics and is crucial for generating random quantum states, a key resource for quantum information tasks. In this work, we introduce a new class of quantum many-body dynamics, termed pseudochaotic dynamics. Although distinct from chaotic dynamics, out-of-time-ordered correlators, the key indicators of quantum chaos, fail to distinguish them. Moreover, pseudochaotic dynamics generates pseudorandom states that are computationally indistinguishable from Haar-random states. We construct pseudochaotic dynamics by embedding a smaller k-qubit subsystem into a larger n-qubit system. We demonstrate that a subsystem of size k=ω(log⁡n)k=\omega (\log n)k=ω(logn) is sufficient to induce pseudochaotic behavior in the entire n-qubit system. Furthermore, we construct a quantum circuit exhibiting pseudochaotic dynamics and demonstrate that it generates pseudorandom states within polylog(n){{{\rm{polylog}}}}(n)polylog(n) depth. In summary, our results constitute the discovery of new quantum dynamics that are computationally indistinguishable from genuine quantum chaos, which provides efficient routes to generate useful pseudorandom states. Recent work introduced pseudorandom quantum states, indistinguishable from truly random states by any polynomial-time algorithm. Here the authors propose pseudochaotic many-body dynamics, which is indistinguishable from chaotic dynamics and can generate pseudorandom states using polylogarithmic-depth circuits.
Quantum chaos is a quantum many-body phenomenon that is associated with a number of intricate properties, such as level repulsion in energy spectra or distinct scalings of out-of-time ordered correlation functions. In this work, we introduce a novel class of "pseudochaotic" quantum Hamiltonians that fundamentally challenges the conventional understanding of quantum chaos and its relationship to computational complexity. Our ensemble is computationally indistinguishable from the Gaussian unitary ensemble (GUE) of strongly-interacting Hamiltonians, widely considered to be a quintessential model for quantum chaos. Surprisingly, despite this effective indistinguishability, our Hamiltonians lack all conventional signatures of chaos: it exhibits Poissonian level statistics, low operator complexity, and weak scrambling properties. This stark contrast between efficient computational indistinguishability and traditional chaos indicators calls into question fundamental assumptions about the nature of quantum chaos. We, furthermore, give an efficient quantum algorithm to simulate Hamiltonians from our ensemble, even though simulating Hamiltonians from the true GUE is known to require exponential time. Our work establishes fundamental limitations on Hamiltonian learning and testing protocols and derives stronger bounds on entanglement and magic state distillation. These results reveal a surprising separation between computational and information-theoretic perspectives on quantum chaos, opening new avenues for research at the intersection of quantum chaos, computational complexity, and quantum information. Above all, it challenges conventional notions of what it fundamentally means to actually observe complex quantum systems.
Randomness is both a useful way to model natural systems and a useful tool for engineered systems, e.g., in computation, communication, and control. Fully random transformations require exponential time for either classical or quantum systems, but in many cases pseudorandom operations can emulate certain properties of truly random ones. Indeed, in the classical realm there is by now a well-developed theory regarding such pseudorandom operations. However, the construction of such objects turns out to be much harder in the quantum case. Here, we show that random quantum unitary time evolutions ("circuits") are a powerful source of quantum pseudorandomness. This gives for the first time a polynomial-time construction of quantum unitary designs, which can replace fully random operations in most applications, and shows that generic quantum dynamics cannot be distinguished from truly random processes. We discuss applications of our result to quantum information science, cryptography, and understanding the self-equilibration of closed quantum dynamics.
A pseudorandom quantum state (PRS) is an ensemble of quantum states indistinguishable from Haar-random states to observers with efficient quantum computers. It allows one to substitute the costly Haar-random state with efficiently preparable PRS as a resource for cryptographic protocols, while also finding applications in quantum learning theory, black hole physics, many-body thermalization, quantum foundations, and quantum chaos. All existing constructions of PRS equate the notion of efficiency to quantum computers which runtime is bounded by a polynomial in its input size. In this work, we relax the notion of efficiency for PRS with respect to observers with near-term quantum computers implementing algorithms with runtime that scales slower than polynomial-time. We introduce the T\mathbf{T}T-PRS which is indistinguishable to quantum algorithms with runtime T(n)\mathbf{T}(n)T(n) that grows slower than polynomials in the input size nnn. We give a set of reasonable conditions that a T\mathbf{T}T-PRS must satisfy and give two constructions by using quantum-secure pseudorandom functions and pseudorandom functions. For T(n)\mathbf{T}(n)T(n) being linearithmic, linear, polylogarithmic, and logarithmic function, we characterize the amount of quantum resources a T\mathbf{T}T-PRS must possess, particularly on its coherence, entanglement, and magic. Our quantum resource characterization applies generally to any two state ensembles that are indistinguishable to observers with computational power T(n)\mathbf{T}(n)T(n), giving a general necessary condition of whether a low-resource ensemble can mimic a high-resource ensemble, forming a T\mathbf{T}T-pseudoresource pair. We demonstate how the necessary amount of resource decreases as the observer's computational power is more restricted, giving a T\mathbf{T}T-pseudoresource pair with larger resource gap for more computationally limited observers.
By modeling quantum chaotic dynamics with ensembles of random operators, we explore how machine learning algorithms can be used to detect pseudorandom behavior in qubit systems. We analyze samples consisting of pieces of correlation functions and find that machine learning algorithms are capable of determining the degree of pseudorandomness which a system is subject to in a precise sense. This is done without computing any correlators explicitly. Interestingly, even samples drawn from two-point functions are found to be sufficient to solve this classification problem. This presents the possibility of using deep learning algorithms to explore late time behavior in chaotic quantum systems which have been inaccessible to simulation.
Deep thermalization refers to the emergence of Haar-like randomness from quantum systems upon partial measurements. As a generalization of quantum thermalization, it is often associated with high complexity and entanglement. Here, we introduce computational deep thermalization and construct the fastest possible dynamics exhibiting it at infinite effective temperature. Our circuit dynamics produce quantum states with low entanglement in polylogarithmic depth that are indistinguishable from Haar random states to any computationally bounded observer. Importantly, the observer is allowed to request many copies of the same residual state obtained from partial projective measurements on the state-this condition is beyond the standard settings of quantum pseudorandomness but natural for deep thermalization. In cryptographic terms, these states are pseudorandom and pseudoentangled, and crucially, they retain these properties under local measurements. Our results demonstrate a new form of computational thermalization in which thermal-like behavior arises from structured quantum states endowed with cryptographic properties instead of from highly unstructured ensembles. The low resource complexity of preparing these states suggests scalable simulations of deep thermalization using quantum computers. Our Letter also motivates the study of computational quantum pseudorandomness beyond BQP observers.
Quantum chaos entails an entropic and computational obstruction to describing a system and thus is intrinsically difficult to characterize. An understanding of quantum chaos is fundamentally related to the mechanism of thermalization in many-body systems and the quantum nature of black holes. In this thesis we adopt the view that quantum information theory provides a powerful framework in which to elucidate chaos in strongly-interacting quantum systems. We first push towards a more precise understanding of chaotic dynamics by relating different diagnostics of chaos, studying the time-evolution of random matrix Hamiltonians, and quantifying random matrix behavior in physical systems. We derive relations between out-of-time ordered correlation functions, spectral quantities, and frame potentials to relate the scrambling of quantum information, decay of correlators, and Haar-randomness. We give analytic expressions for these quantities in random matrix theory to explore universal aspects of late-time dynamics. Motivated by our random matrix results, we define k-invariance in order to capture the onset of random matrix behavior in physical systems. We then refine our diagnostics in order to study chaotic systems with symmetry by considering Haar-randomness with respect to quotients of the unitary group, and in doing so we generalize our quantum information machinery. We further consider extended random matrix ensembles in the context of strongly-interacting quantum systems dual to black holes. Lastly, we study operator growth in classes of random quantum circuits.