Simple Constructions of Linear-Depth t-Designs and Pseudorandom Unitaries

Uniformly random unitaries, i.e. unitaries drawn from the Haar measure, have many useful properties, but cannot be implemented efficiently. This has motivated a long line of research into random unitaries that "look" sufficiently Haar random while also being efficient to implement. Two different notions of derandomisation have emerged: t-designs are random unitaries that information-theoretically reproduce the first t moments of the Haar measure, and pseudorandom unitaries (PRUs) are random unitaries that are computationally indistinguishable from Haar random. In this work, we take a unified approach to constructing t-designs and PRUs. For this, we introduce and analyse the "PFC ensemble", the product of a random computational basis permutation P, a random binary phase operator F, and a random Clifford unitary C. We show that this ensemble reproduces exponentially high moments of the Haar measure. We can then derandomise the PFC ensemble to show the following:

(1) Linear-depth t-designs. We give the first construction of a (diamond-error) approximate t-design with circuit depth linear in t. This follows from the PFC ensemble by replacing the random phase and permutation operators with their 2t-wise independent counterparts.

(2) Non-adaptive PRUs. We give the first construction of PRUs with non-adaptive security, i.e. we construct unitaries that are indistinguishable from Haar random to polynomial-time distinguishers that query the unitary in parallel on an arbitary state. This follows from the PFC ensemble by replacing the random phase and permutation operators with their pseudorandom counterparts.

(3) Adaptive pseudorandom isometries. We show that if one considers isometries (rather than unitaries) from n to n+ω(log n) qubits, a small modification of our PRU construction achieves general adaptive security.

This is based on joint work with Tony Metger (ETH Zurich), Makrand Sinha (UIUC) and Henry Yuen (Columbia).