Pseudorandom density matrices

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.
Comment: 34 pages, 2 figures