Unitary Designs Yield Unconditional Pseudorandomness Against Shallow-Depth Circuits

The quest for truly random numbers underpins many areas of modern technology, from cryptography to scientific simulation, yet generating them efficiently remains a significant challenge. Soumik Ghosh from the University of Chicago, Sathyawageeswar Subramanian from the University of Cambridge, and Wei Zhan, also at the University of Chicago, and their colleagues now demonstrate a path towards achieving this goal through unconditionally efficient pseudorandomness, circumventing the need for complex computational assumptions. Their research establishes that specific quantum states, known as 2-designs, inherently possess properties that make them indistinguishable from truly random states when tested by limited quantum circuits, even those with substantial resources. This breakthrough reveals that unconditional pseudorandomness is possible for restricted, yet natural, types of adversaries, offering a new perspective on complexity theory and potentially paving the way for more secure and efficient technologies.

This work presents the first unconditional construction of pseudorandomness against shallow quantum circuits, demonstrating that the output of a random oracle appears indistinguishable from a truly random string when queried by circuits of depth at most 2. The construction leverages the established mathematical hardness of learning with errors over rings, providing a provable guarantee without relying on unproven complexity assumptions. This result significantly advances the understanding of quantum pseudorandomness and offers a pathway towards building quantum-secure cryptographic primitives with strong theoretical foundations.

Quantum Pseudorandomness via Mathematical Designs

The research centres on creating quantum pseudorandomness, a method for generating quantum states that mimic true randomness to an observer, but are actually produced by a defined process. This aims to achieve this efficiently, as creating genuinely random quantum states requires substantial resources. The approach diverges from previous constructions, which typically rely on unproven cryptographic assumptions and target powerful adversaries, by focusing on security against simpler, more realistic quantum circuits. The core methodology involves leveraging the mathematical properties of ‘designs’, specifically 2-designs, which represent ensembles of quantum states or unitaries that match certain statistical characteristics of a truly random ensemble.

Researchers demonstrate that any quantum state or unitary that qualifies as a 2-design possesses inherent pseudorandomness properties when observed by shallow-depth quantum circuits, circuits with limited complexity and depth. This is innovative because it establishes a link between a relatively weak mathematical requirement, being a 2-design, and a strong security guarantee against a specific class of adversaries. A key insight is that shallow-depth circuits have limited ability to discern structured quantum objects from truly random ones, due to their restricted connectivity and computational power. This allows researchers to bypass the need for complex cryptographic assumptions and construct pseudorandom objects based solely on the design property. The team extended this concept to demonstrate unconditional pseudoentanglement, where states with low entanglement appear indistinguishable from truly random low-entanglement states, and to create pseudorandom unitaries secure against geometrically local quantum circuits. This work establishes a surprising connection between information-theoretic indistinguishability, matching statistical properties on a small number of copies, and computational indistinguishability, appearing random to a computationally limited observer, even when considering many copies of the quantum object.

Unconditional Pseudorandomness from Unitary Designs

This research establishes new methods for creating pseudorandom objects, which are states that appear random despite being generated by a deterministic process. The team demonstrates that these objects can be constructed unconditionally, meaning their randomness does not rely on unproven complexity assumptions, for specific types of computational adversaries. Specifically, the researchers prove that any state which is a ‘2-design’ yields unconditional pseudorandomness against circuits with a limited number of ancillae, and that random phased subspace states exhibit similar properties. Furthermore, any unitary 2-design creates pseudorandom unitaries against geometrically local adversaries, even with limited post-processing.

These findings are significant because they offer a path towards creating secure cryptographic systems and developing new algorithms without relying on potentially false assumptions about computational difficulty. The results contrast with traditional approaches to pseudorandomness, which often require assumptions about the hardness of certain computational problems. The authors acknowledge that their current results apply to restricted classes of adversaries and circuits, and that extending these findings to more general cases remains a challenge. Future work could explore the possibility of constructing pseudorandom objects against broader classes of adversaries, potentially leading to more robust and versatile cryptographic tools.