Efficient unitary designs and pseudorandom unitaries from permutations
<|reference_start|>Efficient unitary designs and pseudorandom unitaries from permutations: In this work we give an efficient construction of unitary $k$-designs using $\tilde{O}(k\cdot 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=2^n$. In particular, we show that products of exponentiated sums of $S(N)$ permutations with random phases approximately match the first $2^{\Omega(n)}$ moments of the Haar measure. By substituting either $\tilde{O}(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$.<|reference_end|>
@article{chen2024efficient,
    title={Efficient unitary designs and pseudorandom unitaries from permutations},
    author={Chi-Fang Chen, Adam Bouland, Fernando G.S.L. Brand~ao, Jordan Docter,
  Patrick Hayden, Michelle Xu},
    journal={arXiv preprint arXiv:2404.16751},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.16751},
    primaryClass={quant-ph cs.CR math-ph math.MP}
}