arXiv:2609.40107
Verification Complexity and Extension of Classical Shadows
Georgios Karaiskos, Asad Raza, Dorian Rudolph, Dax Enshan Koh, Sevag Gharibian
Abstract
Classical shadows are an influential framework for compressing copies of a given quantum state $ρ$ into classical data $S$, enabling many properties of $ρ$ 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 $ρ$, 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-$Σ_2$ $\subseteq$ $\mathrm{P}^{\mathrm{PP}}$, where qc-$Σ_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 $ρ$, estimating the 3-local marginals of $ρ$ is intractable unless QCMA $\subseteq$ BPP, even if the state $ρ$ is the unique state consistent with $S$.
AI Summary
The paper studies whether classical-shadow predictions are jointly consistent with a quantum state, and whether classical postprocessing can extend two-body marginal data to three-body predictions. Validity means consistency of recovered expectations, not certification of the measurement record’s provenance. For polynomially many permutation-invariant observables, validity is in $\mathsf P$ when reduced Schur–Weyl blocks are explicitly supplied, and in $\mathsf{BQP}$ under efficient quantum measurement access. Symmetrization reduces consistency to a polynomial-size SDP; the quantum algorithm first estimates the blocks. Validity is $\mathsf{QMA}$-hard for local real shadows using only $X/Z$ measurements, matchgate fermionic shadows in an input-specified particle-number sector with observables on at most five modes, and heterodyne/homodyne bosonic shadows. These reductions use an $XZ$-only history-state construction, tagged fermionic constraints with synthesized snapshots, and two-level bosonic encodings with moment-controlled leakage, respectively. Bosonic hardness uses recovery cutoff $M=1$, moment order $\ell=O(\log n)$, and bound $B=2^\ell$, without truncating candidate states. Consistency for all Pauli strings with succinct targets is both $\mathsf{QMA}$-hard and $\mathsf{coNP}$-hard. A postselected-learning argument additionally establishes $\mathrm{qc}$-$\Sigma_2\subseteq\mathsf P^{\mathsf{PP}}$. Finally, polynomial-time randomized reconstruction of requested three-qubit marginals to a fixed constant trace-norm error from two-qubit marginals would imply $\mathsf{QCMA}\subseteq\mathsf{BPP}$, even with a unique global completion. The reduction uses witness isolation, encoded history states, and separate witness-recovery and verification stages. Open questions include completeness of all-Pauli consistency for $\mathrm{qc}$-$\Sigma_2$, higher-alternation upper bounds, bosonic hardness with fixed moment parameters, and concrete cryptographic applications of extension hardness.
The authors used generative AI tools to explore proof ideas, assist in identifying and closing gaps in proofs, and improve the exposition.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 70 pages