How to Construct Random Unitaries

Fermi Ma; Hsin-Yuan Huang

Paper 2024/1652

How to Construct Random Unitaries

Fermi Ma

, Simons Institute, University of California, Berkeley

Hsin-Yuan Huang

, Google Quantum AI, California Institute of Technology, Massachusetts Institute of Technology

Abstract

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.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
Keywords: quantum cryptography quantum pseudorandomness pseudorandom unitaries
Contact author(s): fermima1 @ gmail com
hsinyuan @ caltech edu
History: 2024-10-18: approved; 2024-10-14: received; See all versions
Short URL: https://ia.cr/2024/1652
License: CC BY

BibTeX

@misc{cryptoeprint:2024/1652,
      author = {Fermi Ma and Hsin-Yuan Huang},
      title = {How to Construct Random Unitaries},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1652},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1652}
}