Recognition: 2 theorem links
· Lean TheoremOn Scalable Pseudorandom Unitaries and the Unitary Synthesis Problem
Pith reviewed 2026-05-12 04:14 UTC · model grok-4.3
The pith
Constructing scalable pseudorandom unitaries via the random oracle model would positively resolve the unitary synthesis problem.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We formalize ROM-PRUs as statistically secure pseudorandom unitaries in the random oracle model and prove novel connections showing that any such family yields a positive solution to the Aaronson-Kuperberg unitary synthesis problem. In particular, every unitary synthesis algorithm must invoke a classical oracle of input length (2-o(1)) log d bits, where d is the dimension; the same bound therefore applies to every ROM-PRU. This rules out all existing candidate constructions for scalable PRUs and positions the ROM-PRU model as a useful idealized setting for studying pseudorandom unitaries.
What carries the argument
ROM-PRUs (statistically secure pseudorandom unitaries in the random oracle model) together with their proven reductions to approximate unitary designs and epsilon-nets over the unitary group, which in turn reduce to classical-oracle unitary synthesis algorithms.
If this is right
- All previously published candidate constructions for scalable PRUs are ruled out.
- Any future ROM-PRU must invoke an oracle whose input length is nearly twice the logarithm of the unitary dimension.
- A positive resolution of the unitary synthesis problem would immediately yield scalable ROM-PRUs.
- Research on pseudorandom unitaries can usefully treat the ROM-PRU model as an idealized testbed even if concrete instantiations remain open.
Where Pith is reading between the lines
- If unitary synthesis turns out to be hard, then scalable PRUs will probably require construction techniques that lie entirely outside the random oracle paradigm.
- The oracle-length lower bound may be used to derive new impossibility results for other quantum pseudorandom primitives that rely on similar design or net arguments.
- Practical quantum cryptography that invokes PRUs may need to budget for oracle queries whose bit length is almost twice the system dimension.
Load-bearing premise
Every cryptographically secure scalable PRU must be constructible inside the random oracle model and the established links to unitary designs and epsilon-nets capture all relevant cases without hidden restrictions.
What would settle it
An explicit unitary synthesis algorithm that correctly implements every d-dimensional unitary by querying a classical oracle on inputs shorter than (2-o(1)) log d bits, or a scalable PRU construction whose security proof does not rely on the random oracle model.
read the original abstract
We consider the task of constructing pseudorandom unitaries (PRUs) with scalable security, i.e. families in which the security parameter may vary independently of the dimension (or input bit-length). It is not known whether scalable PRUs can be constructed. In this work we show that if scalable PRUs can be constructed via the prevailing paradigm for analyzing PRUs, then there would be a positive solution to the Aaronson-Kuperberg unitary synthesis problem, a longstanding question in quantum complexity theory about whether implementing arbitrary unitaries can be efficiently reduced to computing a Boolean function. Specifically, we formalize the notion of ROM-PRUs, which are statistically secure PRUs in the random oracle model (ROM). All prior known constructions of cryptographically secure PRUs are based on a ROM-PRU construction. We prove novel connections between ROM-PRUs, approximate unitary designs, epsilon-nets over the unitary group, and the unitary synthesis problem. In particular, we prove that any unitary synthesis algorithm (and thus any ROM-PRU) must use a classical oracle with input length (2 - o(1)) log d bits, where d is the dimension of the unitary to be implemented. This bound rules out all existing candidates for scalable PRUs in the literature. Together, these connections indicate that ROM-PRUs provide a fruitful idealized model for studying pseudorandom unitaries.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper claims that scalable pseudorandom unitaries (PRUs) cannot be constructed via the prevailing random-oracle-model paradigm (ROM-PRUs) without implying a positive resolution to the Aaronson-Kuperberg unitary synthesis problem. It formalizes ROM-PRUs as statistically secure families in the random oracle model, proves connections between ROM-PRUs, approximate unitary designs, and ε-nets over the unitary group, and derives an information-theoretic lower bound: any unitary synthesis algorithm (and hence any ROM-PRU) requires a classical oracle whose input length is (2−o(1))log d bits, where d is the dimension. This bound is used to rule out all existing candidate constructions in the literature.
Significance. If the formal connections and lower-bound derivation hold, the result is significant: it supplies a concrete barrier to scalable PRUs under the ROM paradigm and links a cryptographic question to a longstanding open problem in quantum complexity. The paper is credited for its explicit formalization of ROM-PRUs, the derivation of the (2−o(1))log d oracle lower bound directly from standard approximate-design and net arguments, and the one-way implications that remain falsifiable. These elements provide a useful idealized model for future work even if scalable PRUs ultimately require a different paradigm.
minor comments (3)
- [Abstract / §1] Abstract and introduction: the phrase 'prevailing paradigm for analyzing PRUs' is used without an immediate pointer to the precise ROM-PRU definition or the prior constructions being referenced; adding a short paragraph or citation in §1 would improve readability.
- [Connections between ROM-PRUs, designs, and synthesis] The reduction from ROM-PRUs to unitary synthesis via approximate designs and ε-nets is stated at a high level; a dedicated subsection or appendix that explicitly tracks the approximation parameters (ε, δ) through each step would make the argument easier to verify.
- [Lower-bound statement] Notation: the dimension d is sometimes treated as 2^n and sometimes left general; a single consistent convention (with a remark on the asymptotic regime) would prevent minor confusion when reading the oracle-length bound.
Simulated Author's Rebuttal
We thank the referee for the positive summary of our manuscript, the recognition of its significance in linking ROM-PRUs to the Aaronson-Kuperberg problem, and the recommendation for minor revision. The formalization of ROM-PRUs, the connections to approximate designs and ε-nets, and the (2−o(1))log d oracle lower bound are indeed the core contributions, and we are glad these elements are viewed as providing a useful idealized model. No specific major comments were listed in the report, so we have no point-by-point rebuttals to provide. We will incorporate any minor editorial suggestions in the revised version.
Circularity Check
No significant circularity identified
full rationale
The paper derives one-way implications and information-theoretic lower bounds on oracle input length for unitary synthesis algorithms (and thus ROM-PRUs) by formalizing and proving connections to approximate unitary designs and epsilon-nets over the unitary group. These steps rely on standard complexity and information-theoretic arguments within the manuscript rather than any self-definitional reductions, fitted parameters renamed as predictions, load-bearing self-citations, or imported uniqueness theorems. The central result rules out prior candidates based on their oracle sizes but remains self-contained against external benchmarks such as the Aaronson-Kuperberg problem.
Axiom & Free-Parameter Ledger
axioms (2)
- domain assumption The random oracle model provides statistical security for PRU definitions
- standard math Approximate unitary designs and epsilon-nets exist and can be related to PRU security
Reference graph
Works this paper leans on
-
[1]
Quantum versus classical proofs and advice
[AK07] Scott Aaronson and Greg Kuperberg. “Quantum versus classical proofs and advice”. In: Twenty-Second Annual IEEE Conference on Computational Complexity (CCC’07). IEEE. 2007, pp. 115–128 (cit. on p. 15). [BCH+21] Fernando GSL Brand˜ ao, Wissam Chemissany, Nicholas Hunter-Jones, Richard Kueng, and John Preskill. “Models of quantum complexity growth”. I...
-
[2]
How to Construct Random Unitaries
issn: 2521-327X. doi: 10.22331/q-2024-05-08-1340 . url: https://doi.org/10.22331/q-2024-05-08- 1340 (cit. on p. 8). [MH25] Fermi Ma and Hsin-Yuan Huang. “How to Construct Random Unitaries”. In: Pro- ceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025 . Ed. by Michal Kouck´ y and Nikhil Bansal. ACM...
-
[3]
51 Shay Solomon, Amitai Uzrad, and Tianyi Zhang
IEEE, 2024, pp. 485–492. doi: 10.1109/FOCS61266.2024.00038. url: https://doi.org/10.1109/FOCS61266.2024.00038 (cit. on pp. 1–3, 5, 8, 13, 14, 18–20). [OSH21] Micha l Oszmaniec, Adam Sawicki, and Micha l Horodecki. “Epsilon-nets, unitary de- signs, and random quantum circuits”. In: IEEE Transactions on Information Theory 68.2 (2021), pp. 989–1015 (cit. on ...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.