Improved quantum data analysis
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2020
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909280002637824 |
|---|---|
| author | Bădescu, Costin O'Donnell, Ryan |
| author_facet | Bădescu, Costin O'Donnell, Ryan |
| contents | We provide more sample-efficient versions of some basic routines in quantum data analysis, along with simpler proofs. Particularly, we give a quantum "Threshold Search" algorithm that requires only $O((\log^2 m)/ε^2)$ samples of a $d$-dimensional state $ρ$. That is, given observables $0 \le A_1, A_2, ..., A_m \le 1$ such that $\mathrm{tr}(ρA_i) \ge 1/2$ for at least one $i$, the algorithm finds $j$ with $\mathrm{tr}(ρA_j) \ge 1/2-ε$. As a consequence, we obtain a Shadow Tomography algorithm requiring only $\tilde{O}((\log^2 m)(\log d)/ε^4)$ samples, which simultaneously achieves the best known dependence on each parameter $m$, $d$, $ε$. This yields the same sample complexity for quantum Hypothesis Selection among $m$ states; we also give an alternative Hypothesis Selection method using $\tilde{O}((\log^3 m)/ε^2)$ samples. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2011_10908 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Improved quantum data analysis Bădescu, Costin O'Donnell, Ryan Quantum Physics Computational Complexity We provide more sample-efficient versions of some basic routines in quantum data analysis, along with simpler proofs. Particularly, we give a quantum "Threshold Search" algorithm that requires only $O((\log^2 m)/ε^2)$ samples of a $d$-dimensional state $ρ$. That is, given observables $0 \le A_1, A_2, ..., A_m \le 1$ such that $\mathrm{tr}(ρA_i) \ge 1/2$ for at least one $i$, the algorithm finds $j$ with $\mathrm{tr}(ρA_j) \ge 1/2-ε$. As a consequence, we obtain a Shadow Tomography algorithm requiring only $\tilde{O}((\log^2 m)(\log d)/ε^4)$ samples, which simultaneously achieves the best known dependence on each parameter $m$, $d$, $ε$. This yields the same sample complexity for quantum Hypothesis Selection among $m$ states; we also give an alternative Hypothesis Selection method using $\tilde{O}((\log^3 m)/ε^2)$ samples. |
| title | Improved quantum data analysis |
| topic | Quantum Physics Computational Complexity |
| url | https://arxiv.org/abs/2011.10908 |