Pseudorandom unitaries are neither real nor sparse nor noise-robust

Tobias Haug, Kishor Bharti, Dax Enshan Koh

Pseudorandom quantum states (PRSs) and pseudorandom unitaries (PRUs) possess the dual nature of being efficiently constructible while appearing completely random to any efficient q…