Pseudorandom Density Matrices

Pseudorandom states (PRSs) are state ensembles that cannot be efficiently distinguished from Haar-random states. 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 <a:math xmlns:a="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"><a:mi>n</a:mi></a:math>-qubit states that are computationally indistinguishable from the generalized Hilbert-Schmidt ensemble (GHSE), which is constructed from <d:math xmlns:d="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"><d:mo stretchy="false">(</d:mo><d:mi>n</d:mi><d:mo>+</d:mo><d:mi>m</d:mi><d:mo stretchy="false">)</d:mo></d:math>-qubit Haar random states with <i:math xmlns:i="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"><i:mi>m</i:mi></i:math> qubits traced out. For <l:math xmlns:l="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"><l:mi>m</l:mi><l:mo>=</l:mo><l:mn>0</l:mn></l:math>, PRDMs are equivalent to PRSs, whereas for <o:math xmlns:o="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"><o:mi>m</o:mi><o:mo>=</o:mo><o:mi>ω</o:mi><o:mo stretchy="false">(</o:mo><o:mi>log</o:mi><o:mo></o:mo><o:mi>n</o:mi><o:mo stretchy="false">)</o:mo></o:math>, PRDMs are computationally indistinguishable from the maximally mixed state. PRDMs with <t:math xmlns:t="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"><t:mi>m</t:mi><t:mo>=</t:mo><t:mi>ω</t:mi><t:mo stretchy="false">(</t:mo><t:mi>log</t:mi><t:mo></t:mo><t:mi>n</t:mi><t:mo stretchy="false">)</t:mo></t:math> are robust to unital noise channels and separated in terms of security from PRS. PRDMs can disguise valuable quantum resources as trivial states. In particular, we construct pseudoresource state ensembles, which possess near-maximal entanglement, magic and coherence, but are computationally indistinguishable from resource-free states. PRDMs exhibit a pseudoresource gap of <y:math xmlns:y="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"><y:mi mathvariant="normal">Θ</y:mi><y:mo stretchy="false">(</y:mo><y:mi>n</y:mi><y:mo stretchy="false">)</y:mo></y:math> vs 0, surpassing previously found gaps. We also render EFI pairs, a fundamental cryptographic primitive, robust to strong mixed unitary noise. Our work has major implications on quantum resource theory. We show that entanglement, magic, and coherence cannot be efficiently tested, and 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, as well as noise-robust quantum money. Our work provides a comprehensive framework of pseudorandomness for mixed states, which yields powerful quantum cryptographic primitives and fundamental bounds on quantum resource theories.