pipette
ESEspañol

Verification Complexity and Extension of Classical Shadows

Georgios Karaiskos, Asad Raza, Dorian Rudolph, Dax Enshan Koh, Sevag Gharibian

Preprint

In the authors' words

Classical shadows are an influential framework for compressing copies of a given quantum state into classical data , enabling many properties of to be predicted from relatively few copies. In this work, we study two natural questions involving shadows: (1) Given , when can one efficiently verify that came from a genuine -qubit state? This is called the Classical Shadow Validity (CSV) problem, introduced by Karaiskos, Rudolph, Meyer, Eisert, and Gharibian [ICALP 2026]. (2) Given that allows one to capture 2-local properties of , can one fake or spoof a shadow 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 -qubit Pauli strings. A result of independent interest along the way is a new upper bound qc- , where qc- 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 of a quantum state , estimating the 3-local marginals of is intractable unless QCMA BPP, even if the state is the unique state consistent with .

Main resultThe abstract does not state a limitation.

Appeared: Thursday, October 1. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 70 pages