Verification Complexity and Extension of Classical Shadows

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

arXiv:2609.40107 [quant-ph]

(or arXiv:2609.40107v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2609.40107 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.