How to Construct Random Unitaries
This resolves a central open question with implications for cryptography, complexity theory, and physics, though it is incremental as it builds on existing assumptions.
The paper proves the existence of pseudorandom unitaries (PRUs), which are efficient quantum circuits indistinguishable from Haar-random unitaries, assuming quantum-secure one-way functions exist, and establishes this for both standard and stronger security notions.
The existence of pseudorandom unitaries (PRUs) -- efficient quantum circuits that are computationally indistinguishable from Haar-random unitaries -- has been a central open question, with significant implications for cryptography, complexity theory, and fundamental physics. In this work, we close this question by proving that PRUs exist, assuming that any quantum-secure one-way function exists. We establish this result for both (1) the standard notion of PRUs, which are secure against any efficient adversary that makes queries to the unitary $U$, and (2) a stronger notion of PRUs, which are secure even against adversaries that can query both the unitary $U$ and its inverse $U^\dagger$. In the process, we prove that any algorithm that makes queries to a Haar-random unitary can be efficiently simulated on a quantum computer, up to inverse-exponential trace distance.