A major open problem in quantum complexity is the question of unitary synthesis---namely, is it possible to efficiently implement any unitary, given the ability to evaluate any classical function in superposition? Inspired by a recent work by Brakerski and Yuen (CRYPTO 2026), we propose an ``average-case'' unitary synthesis problem, which asks whether it is possible to efficiently implement a Haar random unitary given access to a random Boolean function. We then demonstrate a superpolynomial query lower bound, establishing that unitary synthesis in this model is impossible. Along with our main result, we settle in the negative a question Brakerski and Yuen pose, of whether scalable pseudorandom unitaries (PRUs) can be implemented in the ROM-PRU model. In particular, we show that in the ROM-PRU model, no $Ω(N^{1+γ})$ unitary design on $n$ qubits, where $N=2^n$ , can be efficiently achieved for any $γ> 0$ . On the other hand, we construct an $O(N)$ -design in $\text{poly}(n)$ queries in the same model, surpassing the previously best known results which constructed $O(\sqrt{N})$ -designs.A major open problem in quantum complexity is the question of unitary synthesis---namely, is it possible to efficiently implement any unitary, given the ability to evaluate any classical function in superposition? Inspired by a recent work by Brakerski and Yuen (CRYPTO 2026), we propose an ``average-case'' unitary synthesis problem, which asks whether it is possible to efficiently implement a Haar random unitary given access to a random Boolean function. We then demonstrate a superpolynomial query lower bound, establishing that unitary synthesis in this model is impossible. Along with our main result, we settle in the negative a question Brakerski and Yuen pose, of whether scalable pseudorandom unitaries (PRUs) can be implemented in the ROM-PRU model. In particular, we show that in the ROM-PRU model, no $Ω(N^{1+γ})$ unitary design on $n$ qubits, where $N=2^n$, can be efficiently achieved for any $γ> 0$. On the other hand, we construct an $O(N)$-design in $\text{poly}(n)$ queries in the same model, surpassing the previously best known results which constructed $O(\sqrt{N})$-designs.

quant-pharXiv:2610.06700Oct 6, 20260 citations

Pseudorandom Function-Like States from Common Haar Unitary

Minki Hhan, Shogo Yamada

arXiv:2411.03201Lecture notes in computer scienceDec 2, 20251 citation

The Power of a Single Haar Random State: Constructing and Separating Quantum Pseudorandomness

Boyang Chen, Andrea Coladangelo, Or Sattath

arXiv:2404.03295Lecture notes in computer scienceJan 1, 20257 citations

On Scalable Pseudorandom Unitaries and the Unitary Synthesis Problem

Zvika Brakerski, Henry Yuen

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.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.

quant-pharXiv:2605.09957May 12, 20260 citations

Ω(N^{1+γ})

unitary design on

n

qubits, where

N=2^n

, can be efficiently achieved for any

γ> 0

. On the other hand, we construct an

O(N)

-design in

\text{poly}(n)

queries in the same model, surpassing the previously best known results which constructed

O(\sqrt{N})

-designs.