Andrew Tanggara, Mile Gu, Kishor Bharti (Apr 25 2025).
Abstract: 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.
