Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2509.24432 · Lecture notes in computer science

Pseudorandom Unitaries in the Haar Random Oracle Model

Prabhanjan Ananth, John Bostanci, Aditya Gulati, Yao-Ting Lin

Published Jan 1, 2025• 4 citations
arXivHTMLPDF
DOI
10.1007/978-3-032-01878-6_10

Related papers

Pseudorandomness in the (Inverseless) Haar Random Oracle Model

Prabhanjan Ananth, John Bostanci, Aditya Gulati +1 more

arXiv:2410.19320•Lecture notes in computer science•Jan 1, 2025•7 citations

Unclonable Encryption in the Haar Random Oracle Model

James Bartusek, Eli Goldin

Lecture notes in computer science•Jan 1, 2026•1 citation

Pseudorandom Function-Like States from Common Haar Unitary

Minki Hhan, Shogo Yamada

arXiv:2411.03201•Lecture notes in computer science•Dec 2, 2025•9 citations

Random-Oracle Unitary Synthesis is Impossible

Andrew Huang, Akshar Ramkumar, John Wright

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.06700•Oct 6, 2026•1 citation

On the Limitations of Pseudorandom Unitaries: Or: Cryptographic Applications of LOCC Indistinguishability of Identical Versus Independent Haar Unitaries

Prabhanjan Ananth, Aditya Gulati, Yao-Ting Lin

arXiv:2509.24484•Lecture notes in computer science•Dec 2, 2025•1 citation

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

Boyang Chen, Andrea Coladangelo, Or Sattath

arXiv:2404.03295•Lecture notes in computer science•Jan 1, 2025•30 citations
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 Ω(N1+γ)Ω(N^{1+γ})Ω(N1+γ) unitary design on nnn qubits, where N=2nN=2^nN=2n, can be efficiently achieved for any γ>0γ> 0γ>0. On the other hand, we construct an O(N)O(N)O(N)-design in poly(n)\text{poly}(n)poly(n) queries in the same model, surpassing the previously best known results which constructed O(N)O(\sqrt{N})O(N​)-designs.