Pseudorandom and Pseudoentangled States from Subset States
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914698972102656 |
|---|---|
| author | Jeronimo, Fernando Granha Magrafta, Nir Wu, Pei |
| author_facet | Jeronimo, Fernando Granha Magrafta, Nir Wu, Pei |
| contents | Pseudorandom states (PRS) are an important primitive in quantum cryptography. In this paper, we show that subset states can be used to construct PRSs. A subset state with respect to $S$, a subset of the computational basis, is \[
\frac{1}{\sqrt{|S|}}\sum_{i\in S} |i\rangle. \] As a technical centerpiece, we show that for any fixed subset size $|S|=s$ such that $s = 2^n/ω(\mathrm{poly}(n))$ and $s=ω(\mathrm{poly}(n))$, where $n$ is the number of qubits, a random subset state is information-theoretically indistinguishable from a Haar random state even provided with polynomially many copies. This range of parameter is tight. Our work resolves a conjecture by Ji, Liu and Song. Since subset states of small size have small entanglement across all cuts, this construction also illustrates a pseudoentanglement phenomenon. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_15285 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Pseudorandom and Pseudoentangled States from Subset States Jeronimo, Fernando Granha Magrafta, Nir Wu, Pei Quantum Physics Computational Complexity Cryptography and Security Pseudorandom states (PRS) are an important primitive in quantum cryptography. In this paper, we show that subset states can be used to construct PRSs. A subset state with respect to $S$, a subset of the computational basis, is \[ \frac{1}{\sqrt{|S|}}\sum_{i\in S} |i\rangle. \] As a technical centerpiece, we show that for any fixed subset size $|S|=s$ such that $s = 2^n/ω(\mathrm{poly}(n))$ and $s=ω(\mathrm{poly}(n))$, where $n$ is the number of qubits, a random subset state is information-theoretically indistinguishable from a Haar random state even provided with polynomially many copies. This range of parameter is tight. Our work resolves a conjecture by Ji, Liu and Song. Since subset states of small size have small entanglement across all cuts, this construction also illustrates a pseudoentanglement phenomenon. |
| title | Pseudorandom and Pseudoentangled States from Subset States |
| topic | Quantum Physics Computational Complexity Cryptography and Security |
| url | https://arxiv.org/abs/2312.15285 |