@inproceedings{61777,
  abstract     = {{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 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]. 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.}},
  author       = {{Karaiskos, Georgios and Rudolph, Dorian and Meyer, Johannes Jakob and Eisert, Jens and Gharibian, Sevag}},
  booktitle    = {{International Colloquium on Automata, Languages, and Programming (ICALP)}},
  title        = {{{How hard is it to verify a classical shadow?}}},
  year         = {{2026}},
}