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.24484 · Lecture notes in computer science

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

Published Dec 2, 2025• 1 citation
arXivHTMLPDF
DOI
10.1007/978-3-032-12296-4_3

Related papers

Pseudorandom Unitaries in the Haar Random Oracle Model

Prabhanjan Ananth, John Bostanci, Aditya Gulati +1 more

arXiv:2509.24432•Lecture notes in computer science•Jan 1, 2025•4 citations

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

Pseudorandomness with Proof of Destruction and Applications

Amit Behera, Zvika Brakerski, Or Sattath +1 more

Lecture notes in computer science•Jan 1, 2023•14 citations

Random unitaries from Hamiltonian dynamics

Cui, Laura, Thomas Schuster, Mao, Liang +2 more

The nature of randomness and complexity growth in systems governed by unitary dynamics is a fundamental question in quantum many-body physics. This problem has motivated the study of models such as local random circuits and their convergence to Haar-random unitaries in the long-time limit. However, these models do not correspond to any family of physical time-independent Hamiltonians. In this work, we address this gap by studying the indistinguishability of time-independent Hamiltonian dynamics from truly random unitaries. On one hand, we establish a no-go result showing that for any ensemble of constant-local Hamiltonians and any evolution times, the resulting time-evolution unitary can be efficiently distinguished from Haar-random and fails to form a $2$-design or a pseudorandom unitary (PRU). On the other hand, we prove that this limitation can be overcome by increasing the locality slightly: there exist ensembles of random polylog-local Hamiltonians in one-dimension such that under constant evolution time, the resulting time-evolution unitary is indistinguishable from Haar-random, i.e. it forms both a unitary $k$-design and a PRU. Moreover, these Hamiltonians can be efficiently simulated under standard cryptographic assumptions.

arXiv:2510.08434•Oct 9, 2025•27 citations

On the Impossibility of Cryptography with Tamperable Randomness

Per Austrin, Kai-Min Chung, Mohammad Mahmoody +2 more

Lecture notes in computer science•Jan 1, 2014•28 citations

Simple Constructions of Linear-Depth t-Designs and Pseudorandom Unitaries

Tony Metger, Alexander Poremba, Makrand Sinha +1 more

Uniformly random unitaries, i.e. unitaries drawn from the Haar measure, have many useful properties, but cannot be implemented efficiently. This has motivated a long line of research into random unitaries that “look” sufficiently Haar random while also being efficient to implement. Two different notions of derandomisation have emerged:$t$-designs are random unitaries that information-theoretically reproduce the first$t$moments of the Haar measure, and pseudorandom unitaries (PRUs) are random unitaries that are computationally indistinguishable from Haar random. In this work, we take a unified approach to constructing$t$-designs and PRUs. For this, we introduce and analyse the “$PFC$ensemble”, the product of a random computational basis permutation$P$, a random binary phase operator$F$, and a random Clifford unitary$C$. We show that this ensemble reproduces exponentially high moments of the Haar measure. We can then derandomise the$PFC$ensemble to show the following: •Linear-depth$t$-designs. We give the first construction of a (diamond-error) approximate$t$-design with circuit depth linear in$t$. This follows from the$PFC$ensemble by replacing the random phase and permutation operators with their$2t$-wise independent counterparts. •Non-adaptive PRUs. We give the first construction of PRUs with non-adaptive security, i.e. we construct unitaries that are indistinguishable from Haar random to polynomial-time distinguishers that query the unitary in parallel on an arbitary state. This follows from the$PFC$ensemble by replacing the random phase and permutation operators with their pseudorandom counterparts. •Adaptive pseudorandom isometries. We show that if one considers isometries (rather than unitaries) from$n$to$n+\omega(\log n)$qubits, a small modification of our PRU construction achieves adaptive security, i.e. even a distinguisher that can query the isometry adaptively in sequence cannot distinguish it from Haar random isometries. This gives the first construction of adaptive pseudorandom isometries. Under an additional conjecture, this proof also extends to adaptive PRUs.

arXiv:2404.12647•Annual Symposium on Foundations of Computer Science•Oct 27, 2024•80 citations
The nature of randomness and complexity growth in systems governed by unitary dynamics is a fundamental question in quantum many-body physics. This problem has motivated the study of models such as local random circuits and their convergence to Haar-random unitaries in the long-time limit. However, these models do not correspond to any family of physical time-independent Hamiltonians. In this work, we address this gap by studying the indistinguishability of time-independent Hamiltonian dynamics from truly random unitaries. On one hand, we establish a no-go result showing that for any ensemble of constant-local Hamiltonians and any evolution times, the resulting time-evolution unitary can be efficiently distinguished from Haar-random and fails to form a 222-design or a pseudorandom unitary (PRU). On the other hand, we prove that this limitation can be overcome by increasing the locality slightly: there exist ensembles of random polylog-local Hamiltonians in one-dimension such that under constant evolution time, the resulting time-evolution unitary is indistinguishable from Haar-random, i.e. it forms both a unitary kkk-design and a PRU. Moreover, these Hamiltonians can be efficiently simulated under standard cryptographic assumptions.
Uniformly random unitaries, i.e. unitaries drawn from the Haar measure, have many useful properties, but cannot be implemented efficiently. This has motivated a long line of research into random unitaries that “look” sufficiently Haar random while also being efficient to implement. Two different notions of derandomisation have emerged:ttt-designs are random unitaries that information-theoretically reproduce the firsttttmoments of the Haar measure, and pseudorandom unitaries (PRUs) are random unitaries that are computationally indistinguishable from Haar random. In this work, we take a unified approach to constructingttt-designs and PRUs. For this, we introduce and analyse the “PFCPFCPFCensemble”, the product of a random computational basis permutationPPP, a random binary phase operatorFFF, and a random Clifford unitaryCCC. We show that this ensemble reproduces exponentially high moments of the Haar measure. We can then derandomise thePFCPFCPFCensemble to show the following: •Linear-depthttt-designs. We give the first construction of a (diamond-error) approximatettt-design with circuit depth linear inttt. This follows from thePFCPFCPFCensemble by replacing the random phase and permutation operators with their2t2t2t-wise independent counterparts. •Non-adaptive PRUs. We give the first construction of PRUs with non-adaptive security, i.e. we construct unitaries that are indistinguishable from Haar random to polynomial-time distinguishers that query the unitary in parallel on an arbitary state. This follows from thePFCPFCPFCensemble by replacing the random phase and permutation operators with their pseudorandom counterparts. •Adaptive pseudorandom isometries. We show that if one considers isometries (rather than unitaries) fromnnnton+ω(log⁡n)n+\omega(\log n)n+ω(logn)qubits, a small modification of our PRU construction achieves adaptive security, i.e. even a distinguisher that can query the isometry adaptively in sequence cannot distinguish it from Haar random isometries. This gives the first construction of adaptive pseudorandom isometries. Under an additional conjecture, this proof also extends to adaptive PRUs.