DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.123

How Hard Is It to Verify a Classical Shadow?

Authors: Georgios Karaiskos, Dorian Rudolph, Johannes Jakob Meyer, Jens Eisert, and Sevag Gharibian

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

Classical shadows are succinct classical representations of quantum states which allow one to encode a set of properties P of a quantum state ρ, while only requiring measurements on logarithmically many copies of ρ 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 first 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]. In contrast, we show that for the HKP and MYZ protocols utilizing global Clifford measurements, CSV can be "dequantized" for low-Frobenius norm observables, i.e., solved in randomized poly-time with standard sampling assumptions. Finally, we 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.

Cite as

Georgios Karaiskos, Dorian Rudolph, Johannes Jakob Meyer, Jens Eisert, and Sevag Gharibian. How Hard Is It to Verify a Classical Shadow?. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 123:1-123:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{karaiskos_et_al:LIPIcs.ICALP.2026.123,
  author =	{Karaiskos, Georgios and Rudolph, Dorian and Meyer, Johannes Jakob and Eisert, Jens and Gharibian, Sevag},
  title =	{{How Hard Is It to Verify a Classical Shadow?}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{123:1--123:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.123},
  URN =		{urn:nbn:de:0030-drops-265121},
  doi =		{10.4230/LIPIcs.ICALP.2026.123},
  annote =	{Keywords: classical shadows, quantum complexity theory, QMA, quantum polynomial hierarchy}
}

Search Results

Documents authored by Karaiskos, Georgios

How Hard Is It to Verify a Classical Shadow?

Abstract

Cite as

Thanks for your feedback!

Could not send message