arXiv:2610.01038
Function-like pseudorandom unitaries generate pseudorandom quantum processes
Zitai Xu, Rahul Arvind, Kishor Bharti, Tobias Haug, Dax Enshan Koh, Wai-Keong Mok, Andrew Tanggara, Alexey V. Gorshkov
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.
AI Summary
The paper asks how one short secret key can specify a reusable, publicly indexed family of quantum operations that jointly resembles independent Haar-random unitaries. It defines pseudorandom function-like unitaries (PRFUs), distinguishing classical-label access from coherent superposition access, with adaptive quantum queries in both settings. For classical labels, the construction is $G_k(x)=V_{F_k(x)}$, combining a post-quantum PRF with an adaptive PRU. A first-occurrence hybrid argument uses efficiently implementable finite-query Haar proxies derived from amplified relative-error unitary designs. For $q$ queries, the security loss is one PRF advantage, $q$ single-instance PRU advantages, and $2q\eta$ proxy error. The construction supports inverse queries when the underlying PRU is strong. For coherent labels, an indexed permutation–phase–Clifford construction shares one Clifford across labels. Indexed path recording bounds its statistical distinguishing advantage from independent Haar blocks by $2q(q-1)/(2^n+1)$ for $q<2^n$. Computational security additionally assumes a qPRF and a tweakable in-place quantum-secure pseudorandom permutation. Both constructions give negligible advantage for polynomially many queries when $n=\omega(\log\lambda)$. Exact oracle simulations extend PRFUs to Haar–Stinespring channels and sequential-Haar comb families with private memory, adaptive interventions, and concurrent sessions. Applications include variable-width PRUs via gluing, fresh-nonce authentication rejection, and masked QRAM. The coherent permutation primitive is not constructed from standard assumptions, and a generic coherent-label lifting from PRUs remains open. The shared-Clifford construction is distinguishable with inverse access. Channel and comb guarantees concern specified Haar-induced reference ensembles, not canonical uniform distributions over processes.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 36 pages, 2 figures