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-PRS which is indistinguishable to quantum algorithms with runtime
T(n) that grows slower than polynomials in the input size
n. We give a set of reasonable conditions that a
T-PRS must satisfy and give two constructions by using quantum-secure pseudorandom functions and pseudorandom functions. For
T(n) being linearithmic, linear, polylogarithmic, and logarithmic function, we characterize the amount of quantum resources a
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), giving a general necessary condition of whether a low-resource ensemble can mimic a high-resource ensemble, forming a
T-pseudoresource pair. We demonstate how the necessary amount of resource decreases as the observer's computational power is more restricted, giving a
T-pseudoresource pair with larger resource gap for more computationally limited observers.
Quantum resources like entanglement and magic are essential for characterizing the complexity of quantum states. However, when the number of copies of quantum states and the computational time are limited by numbers polynomial in the system size
n, accurate estimation of the amount of these resources becomes difficult. This makes it impossible to distinguish between ensembles of states with relatively small resources and one that has nearly maximal resources. Such ensembles with small resources are referred to as "pseudo-quantum" ensembles. Recent studies have introduced an ensemble known as the random subset phase state ensemble, which is pseudo-entangled, pseudo-magical, and pseudorandom. While the current state-of-the-art implementation of this ensemble is conjectured to be realized by a circuit with
O(nt) depth, it is still too deep for near-term quantum devices to execute for small
t. In addition, the strict linear dependence on
t has only been established as a lower bound on the circuit depth. In this work, we present significantly improved implementations that only require
ω(logn)⋅O(t[logt]2) depth circuits, which almost saturates the theoretical lower bound. This is also the fastest known for generating pseudorandom states to the best of our knowledge. We believe that our findings will facilitate the implementation of pseudo-ensembles on near-term devices, allowing executions of tasks that would otherwise require ensembles with maximal quantum resources, by generating pseudo-ensembles at a super-polynomially fewer number of entangling and non-Clifford gates.
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=ω(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) 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.
Can measuring part of a quantum system make the remainder more random than the whole? Deep thermalization is a phenomenon in which measurement on part of a thermalizing quantum many-body system produces a subsystem ensemble of states whose higher moments approximate those of Haar-random states, i.e. a quantum state design. In this work, we tightly limit how much randomness from the global state can be transferred to the subsystem in this way: without further assumptions, a global k-design degrades to at most a k/2-design on the unmeasured subsystem. We show this optimality bound by constructing a global k-design for which each sampled state hides a sign preference in its projected distribution that can always be discovered by analyzing moments of its projected ensemble greater than k/2. Strikingly, we show this design loss can be reversed when the global design is generated by chaotic dynamics. Under the chaotic constant-time evolution of a Gaussian Unitary Ensemble (GUE) Hamiltonian, we find that the projected ensemble becomes exactly Haar-random in the thermodynamic limit --- even if the global state seems to be only a
O(1)-design. Moreover, we show this phenomenon does not require the full GUE structure: it persists under substantially weaker assumptions on the spectrum and eigenbasis, and admits finite-size versions with increasingly accurate projected designs as the measured subsystem grows. Our results identify global chaotic dynamics as a mechanism by which measurements can ``concentrate'' quantum randomness and place tight limits on when such amplification is possible.
We report a phase transition in the projected ensemble-the collection of postmeasurement wave functions of a local subsystem obtained by measuring its complement. The transition emerges in systems undergoing random permutation dynamics, a type of quantum time evolution wherein computational basis states are shuffled without creating superpositions. It separates a phase exhibiting deep thermalization, where the projected ensemble is distributed over Hilbert space in a maximally entropic fashion (Haar random), from a phase where it is minimally entropic ("classical bit-string ensemble"). Crucially, this deep thermalization transition is invisible to the subsystem's density matrix, which always exhibits thermalization to infinite temperature across the phase diagram. Through a combination of analytical arguments and numerical simulations, we show that the transition is tuned by the total amount of coherence injected by the input state and the measurement basis, and is exhibited robustly across different microscopic models. Our findings represent a novel form of ergodicity-breaking universality in quantum many-body dynamics, characterized not by a failure of regular thermalization, but rather by a failure of deep thermalization.
Quantum resource theories provide a unified framework for characterizing useful quantum phenomena subject to physical constraints, but are notoriously hard to assess in experimental systems. In this letter, we introduce a unified protocol for quantifying the resource-generating power of arbitrary quantum evolutions applicable to multiple resource theories. It is based on deep thermalization, which has recently gained attention for its role in the emergence of quantum state designs from partial projective measurements. Central to our approach is the use of projected ensembles, recently employed to probe deep thermalization, together with new twirling identities that allow us to directly infer the resource-generating powers of the underlying dynamics. These identities further reveal how resources build up and thermalize in generic quantum circuits. Finally, we show that quantum resources themselves undergo deep thermalization at the subsystem level, offering a complementary and another experimentally accessible route to infer the resource-generating powers. Our work connects deep thermalization to resource quantification, offering a new perspective on the essential role of various resources in generating state designs and on efficient estimation of quantum resources in experiment.