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.
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.
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⊆PPP, 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 ⊆ BPP, even if the state ρ is the unique state consistent with S.
Abstract Efficiently learning expectation values of a quantum state using classical shadow tomography has become a fundamental task in quantum information theory. In a classical shadows protocol, one measures a state in a chosen basis W after it has evolved under a unitary transformation randomly sampled from a chosen distribution U . In this work we study the case where U corresponds to either local or global orthogonal Clifford gates, and W consists of real-valued vectors. Our results show that for various situations of interest, this ‘real’ classical shadow protocol improves the sample complexity over the standard scheme based on general Clifford unitaries. For example, when one is interested in estimating the expectation values of arbitrary real-valued observables, global orthogonal Cliffords typically decrease the required number of samples by a factor of two. More dramatically, for k -local observables composed only of real-valued Pauli operators, sampling local orthogonal Cliffords leads to a reduction by an exponential-in- k factor in the sample complexity over local unitary Cliffords. Finally, we show that by measuring in a basis containing complex-valued vectors, orthogonal shadows can, in the limit of large system size, exactly reproduce the original unitary shadows protocol.
The real classical shadows protocol of West et al. replaces the unitary (Clifford) ensemble of the Huang--Kueng--Preskill scheme by the orthogonal (real Clifford) ensemble, and for symmetric observables achieves strictly smaller estimator variances: a factor approaching two for global evolution and an exponential factor (3/2)k for k-local real Pauli observables. Real hardware, however, never implements the ideal evolution. Building on the noisy classical shadows framework of Koh and Grewal, we give a complete theory of the real classical shadows protocol in the presence of a known completely positive trace-preserving noise channel acting after the orthogonal evolution. We derive the noisy global and local orthogonal shadow channels from first principles using the Weingarten calculus of the orthogonal group, prove that each is a depolarizing channel acting on the symmetric (respectively locally symmetric) component of its input, and derive from it the exact single-shot variance in closed form, together with the associated shadow seminorm, two-sided bounds on it, and the resulting sample-complexity guarantees. We prove that the noiseless sample-complexity advantages survive intact under noise. Because the variances are exact rather than bounded, the ratio is controlled by a single dimensionless parameter, which gives a closed-form criterion for when the factor of two is attainable: both the second-moment and the variance ratio reach it exactly when the observable's norm profile grows, and the noise enters that limit only through a factor lying within 2/(d+2) of two, so the advantage is uniform in the noise. For rank-one targets it is provably unattainable, saturating strictly below two. The local real-Pauli advantage remains (3/2)k. We treat complex measurement bases through a reality parameter and a transposed-noise scalar, recovering unitary shadows in the appropriate limit.
The classical shadows protocol, recently introduced by Huang, Kueng, and Preskill [Nat. Phys. 16, 1050 (2020)], is a quantum-classical protocol to estimate properties of an unknown quantum state. Unlike full quantum state tomography, the protocol can be implemented on near-term quantum hardware and requires few quantum measurements to make many predictions with a high success probability. In this paper, we study the effects of noise on the classical shadows protocol. In particular, we consider the scenario in which the quantum circuits involved in the protocol are subject to various known noise channels and derive an analytical upper bound for the sample complexity in terms of a shadow seminorm for both local and global noise. Additionally, by modifying the classical post-processing step of the noiseless protocol, we define a new estimator that remains unbiased in the presence of noise. As applications, we show that our results can be used to prove rigorous sample complexity upper bounds in the cases of depolarizing noise and amplitude damping.
A crucial subroutine for various quantum computing and communication algorithms is to efficiently extract different classical properties of quantum states. In a notable recent theoretical work by Huang, Kueng, and Preskill [Nat. Phys. 16, 1050 (2020)NPAHAX1745-247310.1038/s41567-020-0932-7], a thrifty scheme showed how to project the quantum state into classical shadows and simultaneously predict M different functions of a state with only O(log_{2}M) measurements, independent of the system size and saturating the information-theoretical limit. Here, we experimentally explore the feasibility of the scheme in the realistic scenario with a finite number of measurements and noisy operations. We prepare a four-qubit GHZ state and show how to estimate expectation values of multiple observables and Hamiltonians. We compare the measurement strategies with uniform, biased, and derandomized classical shadows to conventional ones that sequentially measure each state function exploiting either importance sampling or observable grouping. We next demonstrate the estimation of nonlinear functions using classical shadows and analyze the entanglement of the prepared quantum state. Our experiment verifies the efficacy of exploiting (derandomized) classical shadows and sheds light on efficient quantum computing with noisy intermediate-scale quantum hardware.
We study the sample complexity of the classical shadows task: what is the fewest number of copies of an unknown state you need to measure to predict expected values with respect to some class of observables? Large joint measurements are likely required in order to minimize sample complexity, but previous joint measurement protocols only work when the unknown state is pure. We present the first joint measurement protocol for classical shadows whose sample complexity scales with the rank of the unknown state. In particular we prove O(rB/ε2) samples suffice, where r is the rank of the state, B is a bound on the squared Frobenius norm of the observables, and ε is the target accuracy. In the low-rank regime, this is a nearly quadratic advantage over traditional approaches that use single-copy measurements. We present several intermediate results that may be of independent interest: a solution to a new formulation of classical shadows that captures functions of non-identical input states; a generalization of a ``nice'' Schur basis used for optimal qubit purification and quantum majority vote; and a measurement strategy that allows us to use local symmetries in the Schur basis to avoid intractable Weingarten calculations in the analysis.