The quest for true randomness is a fundamental challenge in both classical and quantum computing. True randomness, the kind you get from truly unpredictable sources like radioactive decay, is often impractical to generate in large quantities. Pseudorandomness provides an elegant workaround: generating sequences that *look* random to a computationally limited observer. This is akin to a masterful magician’s illusion – perfectly plausible, yet ultimately a trick of the eye. Researchers at the University of Chicago and the University of Cambridge have taken a significant step forward in this field, unveiling new forms of unconditionally secure pseudorandomness in quantum systems.
The Illusion of Randomness
In the realm of quantum computing, creating truly random quantum states is exponentially hard. Previous attempts to generate pseudorandom quantum states relied on complexity-theoretic assumptions — essentially, bets about the difficulty of specific computational problems. These assumptions are useful, but they leave a nagging uncertainty. What if our assumptions are wrong? The new research delivers something stronger: unconditional security.
This achievement pivots on a key insight: Instead of aiming to fool powerful, general-purpose quantum computers, which is incredibly difficult, the researchers focused on a specific type of limited quantum computer, one with a “shallow” circuit depth. This means the circuits are relatively simple and have limited connectivity between their components. Think of it as designing a lock that’s nearly impenetrable to simple lockpicks, but maybe vulnerable to high-tech explosives. These “shallow” quantum computers represent a more realistic model of near-term quantum technology with limited coherence times and gate counts.
Designs and Deception
The researchers’ clever strategy is to leverage the concept of “quantum designs.” A t-design is a collection of quantum states or unitaries that statistically resemble a perfectly random collection, matching the first t moments of the distribution. The higher the t, the more closely they mimic true randomness. The crucial finding is that even a simple 2-design (which only matches the first two moments) is sufficient to create pseudorandomness that is unconditionally secure against shallow quantum circuits, a result which initially surprised the researchers.
This result is striking because it bridges a significant gap. The design property only guarantees indistinguishability when you look at a small number (in this case, two) of copies of the quantum object, whereas pseudorandomness requires fooling an adversary that can examine many copies. The researchers elegantly proved that this smaller-scale indistinguishability is enough to guarantee computational indistinguishability on a polynomial number of copies if we constrain the adversary to be a shallow quantum circuit.
Beyond States: Unitary Designs
The work extends beyond quantum states. The researchers show that unitary 2-designs – collections of quantum operations that mimic random unitaries – also achieve unconditional pseudorandomness against a restricted class of shallow quantum circuits, even when queried in parallel. This is significant because it opens up possibilities for constructing pseudorandom unitary operations, a critical element in various quantum algorithms and cryptographic protocols.
Implications and Open Questions
This research has profound implications for quantum cryptography and the foundations of quantum complexity theory. By demonstrating unconditional security against realistic near-term quantum devices, it paves the way for more secure quantum cryptographic systems and more robust quantum algorithms that rely on randomness. But the work also generates exciting new research avenues. For example, the researchers are investigating the extent to which their techniques could be extended to more complex adversaries or whether entirely new, more powerful unconditional constructions are possible.
The work by Soumik Ghosh, Sathyawageeswar Subramanian, and Wei Zhan highlights the power of focusing on realistic models of quantum computation. By shifting the focus from hypothetical, all-powerful quantum computers to the more pragmatic limitations of near-term devices, we can unlock new possibilities for unconditionally secure quantum randomness — a fundamental resource for the burgeoning field of quantum technologies.
