Constructing Pseudo Random Unitaries (PRU) with Efficient Circuits

Random unitaries—the quantum analogue of picking a matrix uniformly from the Haar measure—are ubiquitous in quantum algorithms, benchmarking, cryptography, and even black-hole physics. Unfortunately, a Haar-random unitary requires exponentially many parameters to specify, so physicists and computer scientists have long sought pseudorandom unitaries (PRUs): short quantum circuits that behave as if they were drawn from the Haar distribution.

After seven years of open effort, Fermi Ma (UC Berkeley) and Hsin-Yuan Huang (Google AI / Caltech / MIT) have now shown that PRUs do exist, assuming only the minimal cryptographic assumption of a quantum-secure one-way function. Even better, they build a strong variant that remains pseudorandom to adversaries who can query both a unitary 𝑈 and its inverse 𝑈†. (arXiv:2410.10116v1)

Why This Matters

• Cryptography & Complexity – PRUs are the unitary counterpart of classical pseudorandom functions; they unlock quantum-secure encryption, zero-knowledge proofs, and hardness results.
• Quantum Simulation & Benchmarking – Efficient “random” circuits improve randomized benchmarking and quantum supremacy tests.
• Fundamental Physics – Chaotic dynamics of black holes are often modeled by Haar randomness; PRUs provide a physically realistic substitute.
• Theory Closure – Prior works only achieved weaker “non-adaptive” PRUs or required heavier assumptions. This paper closes the main conceptual gap.

Key Takeaway

Randomness is recorded, not hidden—by tracking Feynman paths, the authors sidestep heavy Weingarten calculus and derive elementary proofs (including a simpler proof of the recent “gluing lemma” for low-depth random circuits).

Main Results at a Glance

Broader Implications

How to Construct Random Unitaries turns the long-standing dream of efficient Haar-like circuits into rigorous reality, opening new frontiers across quantum information science and fundamental physics.

• Black-Hole Modelling – PRUs give a circuit-depth-bounded stand-in for Haar chaos, sharpening recent holographic results.
• Efficient Randomization Tools – Quantum randomized benchmarking, shadow tomography, and learning algorithms can substitute PRUs for expensive t-designs.
• New Proof Techniques – The path-recording framework yields elementary arguments in places where Weingarten calculus was the norm, hinting at broader applicability.

Looking Ahead

The authors expect follow-up work on:

• Depth-Optimized PRUs – Combining their framework with low-depth t-designs to match near-term hardware.
• Pseudorandom Isometries and Channels – Extending the construction beyond square unitaries.
• Cryptographic Protocols – Designing quantum money and authentication schemes that require only the OWF assumption.

Quick Primer on “Haar Randomness” in Quantum Computing

The term “Haar” is named after the Hungarian mathematician Alfréd Haar. In 1909 Haar introduced what is now called the Haar measure—the unique left- and right-invariant measure on any compact topological group. When that group is the unitary group U(d), the Haar measure gives the rigorous notion of a uniformly random unitary matrix.

Haar is the theoretical ideal; Haar-like circuits are the efficient stand-ins that modern quantum information science builds upon.

Why We Need Haar-Like Objects

• Experimental randomization – True Haar unitaries are infeasible; Haar-like circuits let us approximate ideal randomness with O(poly n) gates.
• Cryptographic hardness – Many proofs require that no efficient quantum algorithm can exploit structure in U; PRUs give that guarantee under standard assumptions.
• Complexity theory – Separations such as “random circuit sampling” rely on the chaotic behavior of Haar or Haar-like distributions.