Adaptivity can help exponentially for shadow tomography
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_ | 1866915080862433280 |
|---|---|
| author | Chen, Sitan Gong, Weiyuan Zhang, Zhihan |
| author_facet | Chen, Sitan Gong, Weiyuan Zhang, Zhihan |
| contents | In recent years there has been significant interest in understanding the statistical complexity of learning from quantum data under the constraint that one can only make unentangled measurements. While a key challenge in establishing tight lower bounds in this setting is to deal with the fact that the measurements can be chosen in an adaptive fashion, a recurring theme has been that adaptivity offers little advantage over more straightforward, nonadaptive protocols.
In this note, we offer a counterpoint to this. We show that for the basic task of shadow tomography, protocols that use adaptively chosen two-copy measurements can be exponentially more sample-efficient than any protocol that uses nonadaptive two-copy measurements. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_19022 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Adaptivity can help exponentially for shadow tomography Chen, Sitan Gong, Weiyuan Zhang, Zhihan Quantum Physics Information Theory Machine Learning In recent years there has been significant interest in understanding the statistical complexity of learning from quantum data under the constraint that one can only make unentangled measurements. While a key challenge in establishing tight lower bounds in this setting is to deal with the fact that the measurements can be chosen in an adaptive fashion, a recurring theme has been that adaptivity offers little advantage over more straightforward, nonadaptive protocols. In this note, we offer a counterpoint to this. We show that for the basic task of shadow tomography, protocols that use adaptively chosen two-copy measurements can be exponentially more sample-efficient than any protocol that uses nonadaptive two-copy measurements. |
| title | Adaptivity can help exponentially for shadow tomography |
| topic | Quantum Physics Information Theory Machine Learning |
| url | https://arxiv.org/abs/2412.19022 |