How to Construct Random Unitaries
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918027344216064 |
|---|---|
| author | Ma, Fermi Huang, Hsin-Yuan |
| author_facet | Ma, Fermi Huang, Hsin-Yuan |
| contents | The existence of pseudorandom unitaries (PRUs) -- efficient quantum circuits that are computationally indistinguishable from Haar-random unitaries -- has been a central open question, with significant implications for cryptography, complexity theory, and fundamental physics. In this work, we close this question by proving that PRUs exist, assuming that any quantum-secure one-way function exists. We establish this result for both (1) the standard notion of PRUs, which are secure against any efficient adversary that makes queries to the unitary $U$, and (2) a stronger notion of PRUs, which are secure even against adversaries that can query both the unitary $U$ and its inverse $U^\dagger$. In the process, we prove that any algorithm that makes queries to a Haar-random unitary can be efficiently simulated on a quantum computer, up to inverse-exponential trace distance. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_10116 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | How to Construct Random Unitaries Ma, Fermi Huang, Hsin-Yuan Quantum Physics Computational Complexity Computation and Language Mathematical Physics The existence of pseudorandom unitaries (PRUs) -- efficient quantum circuits that are computationally indistinguishable from Haar-random unitaries -- has been a central open question, with significant implications for cryptography, complexity theory, and fundamental physics. In this work, we close this question by proving that PRUs exist, assuming that any quantum-secure one-way function exists. We establish this result for both (1) the standard notion of PRUs, which are secure against any efficient adversary that makes queries to the unitary $U$, and (2) a stronger notion of PRUs, which are secure even against adversaries that can query both the unitary $U$ and its inverse $U^\dagger$. In the process, we prove that any algorithm that makes queries to a Haar-random unitary can be efficiently simulated on a quantum computer, up to inverse-exponential trace distance. |
| title | How to Construct Random Unitaries |
| topic | Quantum Physics Computational Complexity Computation and Language Mathematical Physics |
| url | https://arxiv.org/abs/2410.10116 |