  Pseudorandom states (PRSs) are state ensembles that cannot be distinguished
from Haar random states by any efficient quantum algorithm. However, the
definition of PRSs has been limited to pure states and lacks robustness against
noise. In this work, we introduce pseudorandom density matrices (PRDMs),
ensembles of $n$-qubit states that are computationally indistinguishable from
the generalized Hilbert-Schmidt ensemble, which is constructed from
$(n+m)$-qubit Haar random states with $m$ qubits traced out. For a mixedness
parameter $m=0$, PRDMs are equivalent to PRSs, whereas for $m=\omega(\log n)$,
PRDMs are computationally indistinguishable from the maximally mixed state. In
contrast to PRSs, PRDMs with $m=\omega(\log n)$ are robust to unital noise
channels and a recently introduced $\mathsf{PostBQP}$ attack. Further, we
construct pseudomagic and pseudocoherent state ensembles, which possess
near-maximal magic and coherence, but are computationally indistinguishable
from states with zero magic and coherence. PRDMs can exhibit a pseudoresource
gap of $\Theta(n)$ vs $0$, surpassing previously found gaps. We introduce
noise-robust EFI pairs, which are state ensembles that are computationally
indistinguishable yet statistically far, even when subject to noise. We show
that testing entanglement, magic and coherence is not efficient. Further, we
prove that black-box resource distillation requires a superpolynomial number of
copies. We also establish lower bounds on the purity needed for efficient
testing and black-box distillation. Finally, we introduce memoryless PRSs, a
noise-robust notion of PRS which are indistinguishable to Haar random states
for efficient algorithms without quantum memory. Our work provides a
comprehensive framework of pseudorandomness for mixed states, which yields
powerful quantum cryptographic primitives and fundamental bounds on quantum
resource theories.
