# Efficient unitary designs and pseudorandom unitaries from permutations

arXiv: https://arxiv.org/abs/2404.16751 · HTML: https://mlsanity.com/paper/2404.16751/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Apr 2024.

## Built on by (most cited first, 2 of 2)

- [Testing classical properties from quantum data](https://mlsanity.com/paper/2411.12730/) (2024)
- [Noise-tolerant learnability of shallow quantum circuits from statistics and the cost of quantum pseudorandomness](https://mlsanity.com/paper/2405.12085/) (2024)

## Abstract (arXiv)

In this work we give an efficient construction of unitary k-designs using tildeO(k· poly(n)) quantum gates, as well as an efficient construction of a parallel-secure pseudorandom unitary (PRU). Both results are obtained by giving an efficient quantum algorithm that lifts random permutations over S(N) to random unitaries over U(N) for N=2n. In particular, we show that products of exponentiated sums of S(N) permutations with random phases approximately match the first 2Omega(n) moments of the Haar measure. By substituting either tildeO(k)-wise independent permutations, or quantum-secure pseudorandom permutations (PRPs) in place of the random permutations, we obtain the above results. The heart of our proof is a conceptual connection between the large dimension (large-N) expansion in random matrix theory and the polynomial method, which allows us to prove query lower bounds at finite-N by interpolating from the much simpler 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. This allows us to show that the distinguishing probability is a low-degree rational polynomial of the dimension N.