Efficient unitary designs and pseudorandom unitaries from permutations
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909495011049472 |
|---|---|
| author | Chen, Chi-Fang Bouland, Adam Brandão, Fernando G. S. L. Docter, Jordan Hayden, Patrick Xu, Michelle |
| author_facet | Chen, Chi-Fang Bouland, Adam Brandão, Fernando G. S. L. Docter, Jordan Hayden, Patrick Xu, Michelle |
| contents | 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^{Ω(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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_16751 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Efficient unitary designs and pseudorandom unitaries from permutations Chen, Chi-Fang Bouland, Adam Brandão, Fernando G. S. L. Docter, Jordan Hayden, Patrick Xu, Michelle Quantum Physics Cryptography and Security Mathematical Physics 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^{Ω(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$. |
| title | Efficient unitary designs and pseudorandom unitaries from permutations |
| topic | Quantum Physics Cryptography and Security Mathematical Physics |
| url | https://arxiv.org/abs/2404.16751 |