The power of a single Haar random state: constructing and separating quantum pseudorandomness
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_ | 1866908364901974016 |
|---|---|
| author | Chen, Boyang Coladangelo, Andrea Sattath, Or |
| author_facet | Chen, Boyang Coladangelo, Andrea Sattath, Or |
| contents | In this work, we focus on the following question: what are the cryptographic implications of having access to an oracle that provides a single Haar random quantum state? We find that the study of such a model sheds light on several aspects of the notion of quantum pseudorandomness.
Pseudorandom states (PRS) are a family of states for which it is hard to distinguish between polynomially many copies of either a state sampled uniformly from the family or a Haar random state. A weaker notion, called single-copy pseudorandom states (1PRS), satisfies this property with respect to a single copy. We obtain the following results:
1. First, we show, perhaps surprisingly, that 1PRS (as well as bit-commitments) exist relative to an oracle that provides a single Haar random state.
2. Second, we build on this result to show the existence of an isometry oracle relative to which 1PRS exist, but PRS do not.
Taken together, our contributions yield one of the first black-box separations between central notions of quantum pseudorandomness, and introduce a new framework to study black-box separations between various inherently quantum primitives. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_03295 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The power of a single Haar random state: constructing and separating quantum pseudorandomness Chen, Boyang Coladangelo, Andrea Sattath, Or Quantum Physics Cryptography and Security In this work, we focus on the following question: what are the cryptographic implications of having access to an oracle that provides a single Haar random quantum state? We find that the study of such a model sheds light on several aspects of the notion of quantum pseudorandomness. Pseudorandom states (PRS) are a family of states for which it is hard to distinguish between polynomially many copies of either a state sampled uniformly from the family or a Haar random state. A weaker notion, called single-copy pseudorandom states (1PRS), satisfies this property with respect to a single copy. We obtain the following results: 1. First, we show, perhaps surprisingly, that 1PRS (as well as bit-commitments) exist relative to an oracle that provides a single Haar random state. 2. Second, we build on this result to show the existence of an isometry oracle relative to which 1PRS exist, but PRS do not. Taken together, our contributions yield one of the first black-box separations between central notions of quantum pseudorandomness, and introduce a new framework to study black-box separations between various inherently quantum primitives. |
| title | The power of a single Haar random state: constructing and separating quantum pseudorandomness |
| topic | Quantum Physics Cryptography and Security |
| url | https://arxiv.org/abs/2404.03295 |