Pseudorandom unitaries with non-adaptive security

Understand

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.