Paper 2024/302

Pseudorandom unitaries with non-adaptive security

Tony Metger, ETH Zurich
Alexander Poremba, Massachusetts Institute of Technology
Makrand Sinha, University of Illinois Urbana-Champaign
Henry Yuen, Columbia University

Pseudorandom unitaries (PRUs) are ensembles of efficiently implementable unitary operators that cannot be distinguished from Haar random unitaries by any quantum polynomial-time algorithm with query access to the unitary. We present a simple PRU construction that is a concatenation of a random Clifford unitary, a pseudorandom binary phase operator, and a pseudorandom permutation operator. We prove that this PRU construction is secure against non-adaptive distinguishers assuming the existence of quantum-secure one-way functions. This means that no efficient quantum query algorithm that is allowed a single application of $U^{\otimes \mathrm{poly}(n)}$ can distinguish whether an $n$-qubit unitary $U$ was drawn from the Haar measure or our PRU ensemble. We conjecture that our PRU construction remains secure against adaptive distinguishers, i.e., secure against distinguishers that can query the unitary polynomially many times in sequence, not just in parallel.

Note: 17 pages.

Available format(s)
Publication info
quantum cryptographypseudorandom unitaries
Contact author(s)
tmetger @ ethz ch
poremba @ mit edu
msinha @ illinois edu
henry yuen @ columbia edu
2024-02-23: approved
2024-02-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Tony Metger and Alexander Poremba and Makrand Sinha and Henry Yuen},
      title = {Pseudorandom unitaries with non-adaptive security},
      howpublished = {Cryptology ePrint Archive, Paper 2024/302},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.