Verification Complexity and Extension of Classical Shadows

preprint Verification Complexity and Extension of Classical Shadows Georgios Karaiskos author Asad Raza author Dorian Rudolph author 57863 Dax Enshan Koh author Sevag Gharibian author 715410000-0002-9992-3379 7 department 623 department Classical shadows are an influential framework for compressing copies of a given quantum state $ρ$ into classical data $S$, enabling many properties of $ρ$ 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 $ρ$, 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-$Σ_2$ $\subseteq$ $\mathrm{P}^{\mathrm{PP}}$, where qc-$Σ_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 $ρ$, estimating the 3-local marginals of $ρ$ is intractable unless QCMA $\subseteq$ BPP, even if the state $ρ$ is the unique state consistent with $S$. 2026 eng arXiv:2609.40107 2609.40107 @article{Karaiskos_Raza_Rudolph_Koh_Gharibian_2026, title={Verification Complexity and Extension of Classical Shadows}, journal={arXiv:2609.40107}, author={Karaiskos, Georgios and Raza, Asad and Rudolph, Dorian and Koh, Dax Enshan and Gharibian, Sevag}, year={2026} } Karaiskos G, Raza A, Rudolph D, Koh DE, Gharibian S. Verification Complexity and Extension of Classical Shadows. arXiv:260940107. Published online 2026. Karaiskos, Georgios, et al. “Verification Complexity and Extension of Classical Shadows.” ArXiv:2609.40107, 2026. G. Karaiskos, A. Raza, D. Rudolph, D.E. Koh, S. Gharibian, ArXiv:2609.40107 (2026). Karaiskos, Georgios, Asad Raza, Dorian Rudolph, Dax Enshan Koh, and Sevag Gharibian. “Verification Complexity and Extension of Classical Shadows.” ArXiv:2609.40107, 2026. G. Karaiskos, A. Raza, D. Rudolph, D. E. Koh, and S. Gharibian, “Verification Complexity and Extension of Classical Shadows,” arXiv:2609.40107. 2026. Karaiskos, G., Raza, A., Rudolph, D., Koh, D. E., & Gharibian, S. (2026). Verification Complexity and Extension of Classical Shadows. In arXiv:2609.40107. 672922026-10-01T07:32:45Z2026-10-01T07:33:38Z