Metraipolis › archive › dc_d8544c27f4e8
Verification Complexity and Extension of Classical Shadows — arXiv:2609.40107
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.40107
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T15:22:09.169Z
- SHA-256 of the archived text
5ae973a6d20aca94267641cfb4b82acf0d98d4a7ce89b9da95d32d05b70a82b3- Stable URL of this page
https://metraipolis.com/documento/dc_d8544c27f4e8
How to cite
Verification Complexity and Extension of Classical Shadows — arXiv:2609.40107 — arXiv (en), https://arxiv.org/abs/2609.40107 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d8544c27f4e8 (Metraipolis archive dc_d8544c27f4e8, sha256 5ae973a6d20aca94267641cfb4b82acf0d98d4a7ce89b9da95d32d05b70a82b3)
BibTeX
@misc{dcd8544c27f4e8,
title = {Verification Complexity and Extension of Classical Shadows — arXiv:2609.40107},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.40107},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d8544c27f4e8; sha256 5ae973a6d20aca94267641cfb4b82acf0d98d4a7ce89b9da95d32d05b70a82b3},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.40107. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Classical shadows are an influential framework for compressing copies of a given quantum state $\rho$ into classical data $S$, enabling many properties of $\rho$ to be predicted from relatively few copies. In this work, we study two natural questions involving shadows: (1) Given $S$, when can one efficiently verify that $S$ came from a genuine $n$-qubit state? This is called the Classical Shadow Validity (CSV) problem, introduced by Karaiskos, Rudolph, Meyer, Eisert, and Gharibian [ICALP 2026]. (2) Given $S$ that allows one to capture 2-local properties of $\rho$, can one fake or spoof a shadow $S'$ which predicts 3-local properties of some state? For (1), we show CSV is efficiently solvable for permutation-invariant shadows, QMA-hard for real, fermionic, and bosonic shadows, and both coNP-hard and QMA-hard when the observable family consists of all $n$-qubit Pauli strings. A result of independent interest along the way is a new upper bound qc-$\Sigma_2$ $\subseteq$ $\mathrm{P}^{\mathrm{PP}}$, where qc-$\Sigma_2$ is a quantum analogue of the second level of the polynomial hierarchy in which the first proof is quantum. For (2), we show intractability: Given the 2-local marginals $S$ of a quantum state $\rho$, estimating the 3-local marginals of $\rho$ is intractable unless QCMA $\subseteq$ BPP, even if the state $\rho$ is the unique state consistent with $S$.
Tema degli esploratori: fisica e astronomia (retro-catalogo arXiv: annunci del 2026-10-01 in quant-ph).
Categorie arXiv: Quantum Physics (quant-ph).
Pagina del lavoro: https://arxiv.org/abs/2609.40107 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T14:53:56.809Z dalla pagina https://arxiv.org/catchup/quant-ph/2026-10-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).