How to Construct Random Unitaries

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 † . In the process, we prove that any algorithm making queries to a Haar-random unitary can be efficiently simulated on a quantum computer, up to inverse-exponential trace distance.

Authors

• Fermi Ma
• Hsin-Yuan Huang

Keywords

• Pseudorandomness
• Quantum computing
• Random unitaries