REVIEW 10 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
Signed reviews
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 10 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.
-
Near-Term Pseudorandom and Pseudoresource Quantum States
The paper defines and constructs pseudorandom quantum states for subpolynomial-time observers, proving that weaker observers can be fooled with less coherence, entanglement, and magic.
-
Parallel Kac's Walk Generates PRU
A linear number of parallel Kac's walk steps forms an adaptively secure pseudorandom unitary, and adding inverse queries costs no extra asymptotic steps.
-
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)}.
-
Adaptive-depth randomized measurement for fermionic observables
A depth-adaptive fermionic classical shadow protocol achieves polynomial sample complexity at depth max{d_int^2/log n, d_int}, where d_int is the observable's interaction distance.
-
Pseudorandom quantum authentication
Quantum states can be hidden and authenticated with a reusable key using pseudorandom unitaries, injected mixing qubits, and unitary designs.
-
Ambient unitaries don't enable shallow group designs
Even with arbitrary ambient unitaries and ancillas, sublinear-depth nearest-neighbour circuits remain far from approximate 2-designs over the matchgate, orthogonal, and symplectic groups and from a Clifford 4-design.
-
Approximate k-uniform states: definition, construction and applications
The paper introduces epsilon-approximate k-uniform states, proves Haar-random states and shallow random circuits produce them, and connects them to approximate quantum error-correcting codes and information masking.
Discussion (0). Continue with ORCID to comment.