arXiv:2610.06700
Random-Oracle Unitary Synthesis is Impossible
Andrew Huang, Akshar Ramkumar, John Wright
Abstract
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.
AI Summary
The paper asks whether access to a uniformly random classical Boolean oracle suffices to synthesize Haar-random $n$-qubit unitaries, and how much query security pseudorandom unitaries can achieve in the random-oracle model (ROM). Its synthesis definition requires a coupling between the implemented channel and a Haar-random unitary with expected diamond distance at most $\epsilon$. Writing $N=2^n$, random-oracle synthesis requires $k\geq\sqrt{N}/\operatorname{poly}(n)$ oracle queries whenever $1-\epsilon\geq1/\operatorname{poly}(n)$, independently of the number of ancillas. For ROM pseudorandom unitaries secure against $T=\Omega(N^{1+\gamma})$ queries, the lower bound is $k\geq N^{\min\{\gamma,1\}/2}/\operatorname{poly}(n)$ under nontrivial implementation and design errors. This rules out scalable PRUs within this model. Conversely, an ensemble using $\operatorname{poly}(n)$ oracle queries achieves a $2^{-n^2/3}$-approximate strong adaptive $(N/8)$-design, including inverse, conjugate, transpose, and controlled queries. The lower bounds use influence-weighted adaptive resampling of oracle bits. Forward and backward martingale decompositions show that most bits can be resampled without substantially changing the relevant circuit block, yielding small covering sets. A random-Pauli/Choi-state argument handles discarded ancillas; Haar concentration and a collective measurement distinguish these sets from Haar or sufficiently high-order designs. The construction alternates random diagonal phases with fixed mixing unitaries, analyzed through low-degree irreducible representations. The upper bound is only query-efficient: suitable mixing unitaries exist with high probability under Haar sampling, but no computationally efficient implementation is established. The lower bounds do not resolve general unitary synthesis, where the oracle may be structured and chosen for the target unitary.
It was able to solve the problem and an additional prompt obtained the ROM-PRU lower bound as well.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.