---
res:
  bibo_abstract:
  - "Classical shadows are succinct classical representations of quantum states\r\nwhich
    allow one to encode a set of properties P of a quantum state rho, while\r\nonly
    requiring measurements on logarithmically many copies of rho in the size\r\nof
    P. In this work, we initiate the study of verification of classical shadows,\r\ndenoted
    classical shadow validity (CSV), from the perspective of computational\r\ncomplexity,
    which asks: Given a classical shadow S, how hard is it to verify\r\nthat S predicts
    the measurement statistics of a quantum state? We show that\r\neven for the elegantly
    simple classical shadow protocol of [Huang, Kueng,\r\nPreskill, Nature Physics
    2020] utilizing local Clifford measurements, CSV is\r\nQMA-complete. This hardness
    continues to hold for the high-dimensional\r\nextension of said protocol due to
    [Mao, Yi, and Zhu, PRL 2025]. Among other\r\nresults, we also show that CSV for
    exponentially many observables is complete\r\nfor a quantum generalization of
    the second level of the polynomial hierarchy,\r\nyielding the first natural complete
    problem for such a class.@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Georgios
      foaf_name: Karaiskos, Georgios
      foaf_surname: Karaiskos
  - foaf_Person:
      foaf_givenName: Dorian
      foaf_name: Rudolph, Dorian
      foaf_surname: Rudolph
  - foaf_Person:
      foaf_givenName: Johannes Jakob
      foaf_name: Meyer, Johannes Jakob
      foaf_surname: Meyer
  - foaf_Person:
      foaf_givenName: Jens
      foaf_name: Eisert, Jens
      foaf_surname: Eisert
  - foaf_Person:
      foaf_givenName: Sevag
      foaf_name: Gharibian, Sevag
      foaf_surname: Gharibian
  dct_date: 2026^xs_gYear
  dct_language: eng
  dct_title: How hard is it to verify a classical shadow?@
...