Pseudorandom unitaries are neither real nor sparse nor noise-robust

Understand

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

• In this study, we establish fundamental bounds on pseudorandomness.
• We show that PRSs and PRUs exist only when the probability that an error occurs is negligible, ruling out their generation on noisy intermediate-scale and early fault-tolerant quantum computers.
• Further, we show that PRUs need imaginarity while PRS do not have this restriction.