Pseudorandom density matrices

Abstract

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. Here, we introduce pseudorandom density matrices (PRDMs), ensembles of $n$-qubit states that are computationally indistinguishable from the generalized Hilbert-Schmidt ensemble (GHSE), which is constructed from $(n+m)$-qubit Haar random states with $m$ qubits traced out. For $m=0$, PRDMs are equivalent to PRSs, whereas for $m=\omega (\log n)$, PRDMs are computationally indistinguishable from the maximally mixed state. PRDMs with $m=\omega (\log n)$ are robust to unital noise channels and separated in terms of security from PRS. PRDMs disguise valuable quantum resources, possessing near-maximal entanglement, magic and coherence, while being computationally indistinguishable from resource-free states. PRDMs exhibit a pseudoresource gap of $\Theta (n)$ 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.

13+25 pages, 2 figures

References in corpus (14)

• Distillation of secret key and entanglement from quantum states
• Application of a resource theory for magic states to fault-tolerant quantum computing
• Aspects of generic entanglement
• Quantum state discrimination and its applications
• A Sharp Fannes-type Inequality for the von Neumann Entropy
• Stabilizer entropies and nonstabilizerness monotones
• Scalable measures of magic resource for quantum computers
• Efficient quantum algorithms for stabilizer entropies
• Asymptotics of random density matrices
• Pseudomagic Quantum States
• Bures-Hall Ensemble: Spectral Densities and Average Entropies
• Multipartite entanglement measures via Bell basis measurements
• Lower Bounds for Learning Quantum States with Single-Copy Measurements
• A quantum tug of war between randomness and symmetries on homogeneous spaces

Cited by in corpus (11)

• Pseudorandom unitaries are neither real nor sparse nor noise-robust
• A nonstabilizerness monotone from stabilizerness asymmetry
• Efficient witnessing and testing of magic in mixed quantum states
• Entanglement theory with limited computational resources
• Hardness of observing strong-to-weak symmetry breaking
• Information phases of partial projected ensembles generated from random quantum states and scrambling dynamics
• On the Hardness of Measuring Magic
• Estimating time in quantum chaotic systems and black holes
• Condition for the generation of the secret key in a BB84 like quantum key distribution protocol
• Do mixed states exhibit deep thermalisation?
• Measure of set imaginarity