Image
Q-FARM event icon

Efficient unitary designs and pseudorandom unitaries from random sums

Summary
Jordan Docter (Stanford)
Michelle Xu (Stanford)
PAB 102/103
May
1
Date(s)
Content

Abstract: Haar randomness is a valuable resource, but difficult to acquire. The desire to spoof it efficiently in the past few decades has propelled the study of both statistical and computational notions of pseudorandomness—constructions which are both close to Haar in some well-defined sense, and efficient to construct. We present new progress along both notions of pseudorandom unitaries: (i) we give a circuit which achieves optimal depth for t-designs, the statistical notion of pseudorandom unitaries, and (ii) we also provide the first construction of a non-adaptive computational pseudorandom unitary. We develop novel techniques in random matrix theory that are essential to both proofs, and hope to inspire their further application to other questions.