REVIEW 4 cited by
How to Construct Random Unitaries
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
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.
Forward citations
Cited by 4 Pith papers
-
Information-Computation Gaps in Quantum Learning via Low-Degree Likelihood
A quantum extension of the low-degree method shows that state designs imply computational hardness for many single-copy quantum measurement strategies, yielding new information-computation gaps.
-
Quantum Simulation of Random Unitaries from Clebsch-Gordan Transforms
Clebsch-Gordan transforms give exact compressed oracles for Haar-random unitary group actions, with efficient circuits for U(d).
-
MicroCrypt Assumptions with Quantum Input Sampling and Pseudodeterminism: Constructions and Separations
Quantum input sampling turns several MicroCrypt primitives into equivalent weak forms, and black-box separations show these forms are strictly weaker than uniform-sampling primitives.
-
Pseudorandomness Properties of Random Reversible Circuits
Random 3-bit gates in a fixed 2D nearest-neighbor brickwork produce approximate k-wise independent permutations of n bits in depth sqrt(n) e^{O(k^3)}.
Discussion (0). Continue with ORCID to comment.