Verification Complexity and Extension of Classical Shadows

@misc{karaiskos2026verification,
  title = {{Verification Complexity and Extension of Classical Shadows}},
  author = {Georgios Karaiskos and Asad Raza and Dorian Rudolph and Dax Enshan Koh and Sevag Gharibian},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.40107},
  eprint = {2609.40107},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.40107},
}

TY  - UNPB
TI  - Verification Complexity and Extension of Classical Shadows
AU  - Georgios Karaiskos
AU  - Asad Raza
AU  - Dorian Rudolph
AU  - Dax Enshan Koh
AU  - Sevag Gharibian
PY  - 2026
DA  - 2026/09/30
PB  - arXiv
DO  - 10.48550/arxiv.2609.40107
UR  - https://arxiv.org/abs/2609.40107
AB  - 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 ⊆ P^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 ⊆ BPP, even if the state ρ is the unique state consistent with S.
ER  -