QLunch: Efficient simulation of random states and random unitaries

Randomness plays a crucial role in cryptography and many other areas like algorithms and simulation. True randomness is, however, a valuable resource. Luckily, it turns out that in many situations, “simulated” randomness is enough, e.g. pseudorandomness, which simulates randomness in computationally bounded environments, or “lazy sampling”, a stateful but unconditional simulation technique. In this talk, I will describe the problem of “lazy-sampling” random quantum states and random unitaries. Subsequently, I will present an efficient scheme for stateful simulation of an oracle that outputs a copy of the same Haar-random quantum state when it is invoked, and sketch an application to quantum money. Finally, I will briefly discuss an existential result for a space-efficient but time-inefficient solution to lazy sampling for Haar-random unitaries.