---
_id: '67292'
abstract:
- lang: eng
  text: '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$.'
author:
- first_name: Georgios
  full_name: Karaiskos, Georgios
  last_name: Karaiskos
- first_name: Asad
  full_name: Raza, Asad
  last_name: Raza
- first_name: Dorian
  full_name: Rudolph, Dorian
  id: '57863'
  last_name: Rudolph
- first_name: Dax Enshan
  full_name: Koh, Dax Enshan
  last_name: Koh
- first_name: Sevag
  full_name: Gharibian, Sevag
  id: '71541'
  last_name: Gharibian
  orcid: 0000-0002-9992-3379
citation:
  ama: Karaiskos G, Raza A, Rudolph D, Koh DE, Gharibian S. Verification Complexity
    and Extension of Classical Shadows. <i>arXiv:260940107</i>. Published online 2026.
  apa: Karaiskos, G., Raza, A., Rudolph, D., Koh, D. E., &#38; Gharibian, S. (2026).
    Verification Complexity and Extension of Classical Shadows. In <i>arXiv:2609.40107</i>.
  bibtex: '@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} }'
  chicago: Karaiskos, Georgios, Asad Raza, Dorian Rudolph, Dax Enshan Koh, and Sevag
    Gharibian. “Verification Complexity and Extension of Classical Shadows.” <i>ArXiv:2609.40107</i>,
    2026.
  ieee: G. Karaiskos, A. Raza, D. Rudolph, D. E. Koh, and S. Gharibian, “Verification
    Complexity and Extension of Classical Shadows,” <i>arXiv:2609.40107</i>. 2026.
  mla: Karaiskos, Georgios, et al. “Verification Complexity and Extension of Classical
    Shadows.” <i>ArXiv:2609.40107</i>, 2026.
  short: G. Karaiskos, A. Raza, D. Rudolph, D.E. Koh, S. Gharibian, ArXiv:2609.40107
    (2026).
date_created: 2026-10-01T07:32:45Z
date_updated: 2026-10-01T07:33:38Z
department:
- _id: '7'
- _id: '623'
external_id:
  arxiv:
  - '2609.40107'
language:
- iso: eng
publication: arXiv:2609.40107
status: public
title: Verification Complexity and Extension of Classical Shadows
type: preprint
user_id: '71541'
year: '2026'
...