---
_id: '61777'
abstract:
- lang: eng
  text: "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."
author:
- first_name: Georgios
  full_name: Karaiskos, Georgios
  last_name: Karaiskos
- first_name: Dorian
  full_name: Rudolph, Dorian
  last_name: Rudolph
- first_name: Johannes Jakob
  full_name: Meyer, Johannes Jakob
  last_name: Meyer
- first_name: Jens
  full_name: Eisert, Jens
  last_name: Eisert
- first_name: Sevag
  full_name: Gharibian, Sevag
  last_name: Gharibian
citation:
  ama: 'Karaiskos G, Rudolph D, Meyer JJ, Eisert J, Gharibian S. How hard is it to
    verify a classical shadow? In: <i>International Colloquium on Automata, Languages,
    and Programming (ICALP)</i>. ; 2026.'
  apa: Karaiskos, G., Rudolph, D., Meyer, J. J., Eisert, J., &#38; Gharibian, S. (2026).
    How hard is it to verify a classical shadow? <i>International Colloquium on Automata,
    Languages, and Programming (ICALP)</i>.
  bibtex: '@inproceedings{Karaiskos_Rudolph_Meyer_Eisert_Gharibian_2026, title={How
    hard is it to verify a classical shadow?}, booktitle={International Colloquium
    on Automata, Languages, and Programming (ICALP)}, author={Karaiskos, Georgios
    and Rudolph, Dorian and Meyer, Johannes Jakob and Eisert, Jens and Gharibian,
    Sevag}, year={2026} }'
  chicago: Karaiskos, Georgios, Dorian Rudolph, Johannes Jakob Meyer, Jens Eisert,
    and Sevag Gharibian. “How Hard Is It to Verify a Classical Shadow?” In <i>International
    Colloquium on Automata, Languages, and Programming (ICALP)</i>, 2026.
  ieee: G. Karaiskos, D. Rudolph, J. J. Meyer, J. Eisert, and S. Gharibian, “How hard
    is it to verify a classical shadow?,” 2026.
  mla: Karaiskos, Georgios, et al. “How Hard Is It to Verify a Classical Shadow?”
    <i>International Colloquium on Automata, Languages, and Programming (ICALP)</i>,
    2026.
  short: 'G. Karaiskos, D. Rudolph, J.J. Meyer, J. Eisert, S. Gharibian, in: International
    Colloquium on Automata, Languages, and Programming (ICALP), 2026.'
date_created: 2025-10-10T13:45:07Z
date_updated: 2026-04-20T13:55:08Z
external_id:
  arxiv:
  - '2510.08515'
language:
- iso: eng
publication: International Colloquium on Automata, Languages, and Programming (ICALP)
status: public
title: How hard is it to verify a classical shadow?
type: conference
user_id: '71541'
year: '2026'
...