Welcome to the resource topic for 2024/1652
Title:
How to Construct Random Unitaries
Authors: Fermi Ma, Hsin-Yuan Huang
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.
ePrint: https://eprint.iacr.org/2024/1652
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .