Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2510.08515 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917539365257216 |
|---|---|
| author | Karaiskos, Georgios Rudolph, Dorian Meyer, Johannes Jakob Eisert, Jens Gharibian, Sevag |
| author_facet | Karaiskos, Georgios Rudolph, Dorian Meyer, Johannes Jakob Eisert, Jens Gharibian, Sevag |
| contents | Classical shadows are succinct classical representations of quantum states which allow one to encode a set of properties P of a quantum state rho, while only requiring measurements on logarithmically many copies of rho in the size of P. In this work, we initiate the study of verification of classical shadows, denoted classical shadow validity (CSV), from the perspective of computational complexity, which asks: Given a classical shadow S, how hard is it to verify that S predicts the measurement statistics of a quantum state? We first show that even for the elegantly simple classical shadow protocol of [Huang, Kueng, Preskill, Nature Physics 2020] utilizing local Clifford measurements, CSV is QMA-complete. This hardness continues to hold for the high-dimensional extension of said protocol due to [Mao, Yi, and Zhu, PRL 2025]. In contrast, we show that for the HKP and MYZ protocols utilizing global Clifford measurements, CSV can be "dequantized" for low-Frobenius norm observables, i.e., solved in randomized poly-time with standard sampling assumptions. Among other results, we also show that CSV for exponentially many observables is complete for a quantum generalization of the second level of the polynomial hierarchy, yielding the first natural complete problem for such a class. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_08515 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | How hard is it to verify a classical shadow? Karaiskos, Georgios Rudolph, Dorian Meyer, Johannes Jakob Eisert, Jens Gharibian, Sevag Quantum Physics Computational Complexity Classical shadows are succinct classical representations of quantum states which allow one to encode a set of properties P of a quantum state rho, while only requiring measurements on logarithmically many copies of rho in the size of P. In this work, we initiate the study of verification of classical shadows, denoted classical shadow validity (CSV), from the perspective of computational complexity, which asks: Given a classical shadow S, how hard is it to verify that S predicts the measurement statistics of a quantum state? We first show that even for the elegantly simple classical shadow protocol of [Huang, Kueng, Preskill, Nature Physics 2020] utilizing local Clifford measurements, CSV is QMA-complete. This hardness continues to hold for the high-dimensional extension of said protocol due to [Mao, Yi, and Zhu, PRL 2025]. In contrast, we show that for the HKP and MYZ protocols utilizing global Clifford measurements, CSV can be "dequantized" for low-Frobenius norm observables, i.e., solved in randomized poly-time with standard sampling assumptions. Among other results, we also show that CSV for exponentially many observables is complete for a quantum generalization of the second level of the polynomial hierarchy, yielding the first natural complete problem for such a class. |
| title | How hard is it to verify a classical shadow? |
| topic | Quantum Physics Computational Complexity |
| url | https://arxiv.org/abs/2510.08515 |