# How to Construct Random Unitaries

arXiv: https://arxiv.org/abs/2410.10116 · HTML: https://mlsanity.com/paper/2410.10116/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 29 references that are in the map.
- First posted on arXiv 14 Oct 2024.

## Builds on (most cited first, 7 of 7)

- [Predicting Many Properties of a Quantum System from Very Few Measurements](https://mlsanity.com/paper/2002.08953/) (2020)
- [Quantum advantage in learning from experiments](https://mlsanity.com/paper/2112.00778/) (2021)
- [Pseudorandom unitaries are neither real nor sparse nor noise-robust](https://mlsanity.com/paper/2306.11677/) (2023)
- [Pseudorandom States, Non-Cloning Theorems and Quantum Money](https://mlsanity.com/paper/1711.00385/) (2017)
- [Quantum Cryptography in Algorithmica](https://mlsanity.com/paper/2212.00879/) (2022)
- [Simple constructions of linear-depth t-designs and pseudorandom unitaries](https://mlsanity.com/paper/2404.12647/) (2024)
- [A one-query lower bound for unitary synthesis and breaking quantum cryptography](https://mlsanity.com/paper/2310.08870/) (2023)

## Built on by (most cited first, 3 of 3)

- [Testing classical properties from quantum data](https://mlsanity.com/paper/2411.12730/) (2024)
- [Purest Quantum State Identification](https://mlsanity.com/paper/2502.14334/) (2025)
- [Learning to erase quantum states: thermodynamic implications of quantum learning theory](https://mlsanity.com/paper/2504.07341/) (2025)

## Abstract (arXiv)

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.