19 Apr 2024 | Tony Metger, Alexander Poremba, Makrand Sinha, and Henry Yuen
This paper introduces the PFC ensemble, a random ensemble of unitaries composed of a random computational basis permutation P, a random binary phase operator F, and a random Clifford unitary C. The PFC ensemble is shown to reproduce exponentially high moments of the Haar measure, making it a (diamond-error) t-design. By replacing the random phase and permutation operators with their 2t-wise independent counterparts, the PFC ensemble can be derandomized to construct linear-depth t-designs. Similarly, replacing them with pseudorandom counterparts yields non-adaptive pseudorandom unitaries (PRUs). Furthermore, a small modification of the PRU construction achieves adaptive security for isometries, leading to the first construction of adaptive pseudorandom isometries (PRIs). The PFC ensemble is also shown to be a t-design with exponentially small diamond distance error, enabling efficient constructions of both t-designs and PRUs. The paper also discusses the implications of these results for quantum computing and cryptography, including applications in quantum cryptography and the modeling of chaotic quantum systems.This paper introduces the PFC ensemble, a random ensemble of unitaries composed of a random computational basis permutation P, a random binary phase operator F, and a random Clifford unitary C. The PFC ensemble is shown to reproduce exponentially high moments of the Haar measure, making it a (diamond-error) t-design. By replacing the random phase and permutation operators with their 2t-wise independent counterparts, the PFC ensemble can be derandomized to construct linear-depth t-designs. Similarly, replacing them with pseudorandom counterparts yields non-adaptive pseudorandom unitaries (PRUs). Furthermore, a small modification of the PRU construction achieves adaptive security for isometries, leading to the first construction of adaptive pseudorandom isometries (PRIs). The PFC ensemble is also shown to be a t-design with exponentially small diamond distance error, enabling efficient constructions of both t-designs and PRUs. The paper also discusses the implications of these results for quantum computing and cryptography, including applications in quantum cryptography and the modeling of chaotic quantum systems.