This work presents efficient constructions of unitary k-designs and pseudorandom unitaries using quantum gates and permutations. The key idea is to lift random permutations from the symmetric group $ \mathcal{S}(N) $ to random unitaries in $ \mathcal{U}(N) $, where $ N = 2^n $. By using products of exponentiated sums of random permutations with random phases, the authors show that these unitaries approximate the first $ 2^{\Omega(n)} $ moments of the Haar measure. This allows for efficient constructions of both unitary k-designs and pseudorandom unitaries (PRUs). The authors demonstrate that products of exponentiated sparse random matrices, left and right multiplied by random permutations, approximate Haar random unitaries for nonadaptive queries. They show that these constructions can be implemented using $ \tilde{\mathcal{O}}(k \cdot \text{poly}(n)) $ quantum gates, achieving near-linear scaling in k. This matches the lower bound on k-dependence up to logarithmic factors. For pseudorandom unitaries, the authors show that quantum-secure pseudorandom permutations (PRPs) can be used to construct parallel-secure PRUs. This is achieved by replacing truly random permutations with pseudorandom ones in the construction of the unitary k-designs. The proof relies on a conceptual connection between the large dimension expansion in random matrix theory and the polynomial method. This allows the authors to prove query lower bounds at finite-N by interpolating from the large-N limit. The key technical step is to exhibit an orthonormal basis for irreducible representations of the partition algebra that has a low-degree large-N expansion. The authors also show that the distinguishing probability is a low-degree rational polynomial of the dimension N. This allows them to control the finite-N corrections through interpolation from the large-N limit. The main result is that the product of exponentials of sums of random phased permutations is an $ \epsilon $-approximate k-design for large values of k and small values of $ \epsilon $. The work provides efficient constructions of unitary k-designs and pseudorandom unitaries, with applications in quantum information theory and cryptography. The results demonstrate that pseudorandom permutations can be used to construct quantum pseudorandom unitaries, bridging the gap between classical and quantum pseudorandomness.This work presents efficient constructions of unitary k-designs and pseudorandom unitaries using quantum gates and permutations. The key idea is to lift random permutations from the symmetric group $ \mathcal{S}(N) $ to random unitaries in $ \mathcal{U}(N) $, where $ N = 2^n $. By using products of exponentiated sums of random permutations with random phases, the authors show that these unitaries approximate the first $ 2^{\Omega(n)} $ moments of the Haar measure. This allows for efficient constructions of both unitary k-designs and pseudorandom unitaries (PRUs). The authors demonstrate that products of exponentiated sparse random matrices, left and right multiplied by random permutations, approximate Haar random unitaries for nonadaptive queries. They show that these constructions can be implemented using $ \tilde{\mathcal{O}}(k \cdot \text{poly}(n)) $ quantum gates, achieving near-linear scaling in k. This matches the lower bound on k-dependence up to logarithmic factors. For pseudorandom unitaries, the authors show that quantum-secure pseudorandom permutations (PRPs) can be used to construct parallel-secure PRUs. This is achieved by replacing truly random permutations with pseudorandom ones in the construction of the unitary k-designs. The proof relies on a conceptual connection between the large dimension expansion in random matrix theory and the polynomial method. This allows the authors to prove query lower bounds at finite-N by interpolating from the large-N limit. The key technical step is to exhibit an orthonormal basis for irreducible representations of the partition algebra that has a low-degree large-N expansion. The authors also show that the distinguishing probability is a low-degree rational polynomial of the dimension N. This allows them to control the finite-N corrections through interpolation from the large-N limit. The main result is that the product of exponentials of sums of random phased permutations is an $ \epsilon $-approximate k-design for large values of k and small values of $ \epsilon $. The work provides efficient constructions of unitary k-designs and pseudorandom unitaries, with applications in quantum information theory and cryptography. The results demonstrate that pseudorandom permutations can be used to construct quantum pseudorandom unitaries, bridging the gap between classical and quantum pseudorandomness.