Function-like pseudorandom unitaries generate pseudorandom quantum processes
Abstract
Haar-random unitaries provide a canonical model of generic random quantum evolution, but they typically have exponential description and circuit complexity. Although pseudorandom unitaries efficiently emulate a single Haar-random unitary, many tasks require an entire reusable family of independently random-looking operations. We introduce pseudorandom function-like unitaries (PRFU), which generate such a family indexed by public labels using only a single short key. We distinguish classical- and coherent-label access and establish security under adaptive quantum queries. For classical labels, we provide a generic construction from a post-quantum pseudorandom function and a pseudorandom unitary. For coherent labels, we use an indexed path-recording framework to analyze interference across labels and prove security of a construction based on quantum-secure function and permutation primitives. We further show that PRFUs generate pseudorandom channels and quantum combs with private memory, which are secure against adaptive interventions and concurrent sessions. Combining PRFUs with unitary gluing yields a one-key family of pseudorandom unitaries whose supported register widths can be chosen after key generation. Further applications include nonce-resolved quantum authentication, coherently masked QRAM queries, and efficient emulation of random multi-time dynamics. Our results extend quantum pseudorandomness from individual operations to efficiently generated families of random-looking quantum dynamics.
Related
- Derivatives of Quantum Randomness: Separating Pseudorandom Unitaries from Pseudorandom (Function-like) States
- How to Build Pseudorandom Unitaries in Microcrypt
- Distinctness threshold for pseudorandom unitaries
- How to make quantum cheese: efficient geometry oracles for exponentially many pseudorandom microstructures
- Optimal Quantum-Circuit Synthesis and Implementation of General Unitaries with Parallelized Bitstring-Conditioned Rotations
BibTeX
@misc{xu2026functionlike,
title = {{Function-like pseudorandom unitaries generate pseudorandom quantum processes}},
author = {Zitai Xu and Rahul Arvind and Kishor Bharti and Tobias Haug and Dax Enshan Koh and Wai-Keong Mok and Andrew Tanggara and Alexey V. Gorshkov},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.01038},
eprint = {2610.01038},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.01038},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Function-like pseudorandom unitaries generate pseudorandom quantum processes
AU - Zitai Xu
AU - Rahul Arvind
AU - Kishor Bharti
AU - Tobias Haug
AU - Dax Enshan Koh
AU - Wai-Keong Mok
AU - Andrew Tanggara
AU - Alexey V. Gorshkov
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.01038
UR - https://arxiv.org/abs/2610.01038
AB - Haar-random unitaries provide a canonical model of generic random quantum evolution, but they typically have exponential description and circuit complexity. Although pseudorandom unitaries efficiently emulate a single Haar-random unitary, many tasks require an entire reusable family of independently random-looking operations. We introduce pseudorandom function-like unitaries (PRFU), which generate such a family indexed by public labels using only a single short key. We distinguish classical- and coherent-label access and establish security under adaptive quantum queries. For classical labels, we provide a generic construction from a post-quantum pseudorandom function and a pseudorandom unitary. For coherent labels, we use an indexed path-recording framework to analyze interference across labels and prove security of a construction based on quantum-secure function and permutation primitives. We further show that PRFUs generate pseudorandom channels and quantum combs with private memory, which are secure against adaptive interventions and concurrent sessions. Combining PRFUs with unitary gluing yields a one-key family of pseudorandom unitaries whose supported register widths can be chosen after key generation. Further applications include nonce-resolved quantum authentication, coherently masked QRAM queries, and efficient emulation of random multi-time dynamics. Our results extend quantum pseudorandomness from individual operations to efficiently generated families of random-looking quantum dynamics.
ER -