Distinctness threshold for pseudorandom unitaries
Abstract
Pseudorandomness is increasingly recognized as a key property of ensembles in quantum information theory, statistical mechanics, and quantum many-body physics. Yet it appears in two conceptually different forms: statistical pseudorandomness, embodied by unitary designs, and computational pseudorandomness captured by pseudorandom unitaries (PRUs). The relationship between these two forms of pseudorandomness remains surprisingly poorly understood. Existing PRU constructions reveal this interplay where a statistically randomizing ingredient, a unitary design, is combined with classical cryptographic primitives to produce computational pseudorandomness. We show that statistical pseudorandomness is not necessary for computationally pseudorandom unitaries. We do this by replacing the unitary $2$-design layer in the existing constructions with ensembles that are not even state $1$-designs, yet are sufficiently {\em distinct}, a property we identify to be necessary for any PRU. This yields new non-adaptively secure PRU ensembles whose computational pseudorandomness is obtained without an underlying statistically pseudorandom quantum ensemble, such as a $2$-design. We characterize distinctness via an entangled analogue of anticoncentration and use it to show that distinctness already captures constraints on coherence and imaginarity of PRUs, while identifying broad classes of inputs for which the latter obstruction disappears, enabling real-valued PRUs even for certain (maximally) entangled states. As an application, we use lack of distinctness to constrain the conjectured pseudorandomness of the random phase-Hadamard ensemble to form a PRU.
Related
- Derivatives of Quantum Randomness: Separating Pseudorandom Unitaries from Pseudorandom (Function-like) States
- Function-like pseudorandom unitaries generate pseudorandom quantum processes
- How to Build Pseudorandom Unitaries in Microcrypt
- Elementary proofs of quantum lower bounds for element distinctness and k-sum
- Tight Time-Space Lower Bounds for Collision Finding and Element Distinctness under Label Symmetry
BibTeX
@misc{raza2026distinctness,
title = {{Distinctness threshold for pseudorandom unitaries}},
author = {Asad Raza and Jens Eisert and Bill Fefferman},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.03065},
eprint = {2609.03065},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.03065},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Distinctness threshold for pseudorandom unitaries
AU - Asad Raza
AU - Jens Eisert
AU - Bill Fefferman
PY - 2026
DA - 2026/09/02
PB - arXiv
DO - 10.48550/arxiv.2609.03065
UR - https://arxiv.org/abs/2609.03065
AB - Pseudorandomness is increasingly recognized as a key property of ensembles in quantum information theory, statistical mechanics, and quantum many-body physics. Yet it appears in two conceptually different forms: statistical pseudorandomness, embodied by unitary designs, and computational pseudorandomness captured by pseudorandom unitaries (PRUs). The relationship between these two forms of pseudorandomness remains surprisingly poorly understood. Existing PRU constructions reveal this interplay where a statistically randomizing ingredient, a unitary design, is combined with classical cryptographic primitives to produce computational pseudorandomness. We show that statistical pseudorandomness is not necessary for computationally pseudorandom unitaries. We do this by replacing the unitary $2$-design layer in the existing constructions with ensembles that are not even state $1$-designs, yet are sufficiently {\em distinct}, a property we identify to be necessary for any PRU. This yields new non-adaptively secure PRU ensembles whose computational pseudorandomness is obtained without an underlying statistically pseudorandom quantum ensemble, such as a $2$-design. We characterize distinctness via an entangled analogue of anticoncentration and use it to show that distinctness already captures constraints on coherence and imaginarity of PRUs, while identifying broad classes of inputs for which the latter obstruction disappears, enabling real-valued PRUs even for certain (maximally) entangled states. As an application, we use lack of distinctness to constrain the conjectured pseudorandomness of the random phase-Hadamard ensemble to form a PRU.
ER -