Winston Fu, Dax Enshan Koh, Siong Thye Goh, and Jian Feng Kong, “Classical shadows with improved median-of-means estimation.” Quantum Science and Technology 10, 035043 (2025)
Abstract:
The classical shadows protocol, introduced by Huang et al (2020 Nat. Phys. 16 1050), makes use of the median-of-means (MoM) estimator to efficiently estimate the expectation values of M observables with failure probability δ using only $\mathcal{O}(\log(M/\delta))$ measurements. In their analysis, Huang et al used loose constants in their asymptotic performance bounds for simplicity. However, the specific values of these constants can significantly affect the number of shots used in practical implementations. To address this, we studied a modified MoM estimator proposed by Minsker (2023 Proc. 36th Conf. on Learning Theory (PMLR) 195 5925) that uses optimal constants and involves a U-statistic over the data set. For efficient estimation, we implemented two types of incomplete U-statistics estimators, the first based on random sampling and the second based on cyclically permuted sampling. We compared the performance of the original and modified estimators when used with the classical shadows protocol with single-qubit Clifford unitaries (Pauli measurements) for an Ising spin chain, and global Clifford unitaries (Clifford measurements) for the Greenberger–Horne–Zeilinger state. While the original estimator outperformed the modified estimators for Pauli measurements, the modified estimators showed improved performance over the original estimator for Clifford measurements. Our findings highlight the importance of tailoring estimators to specific measurement settings to optimize the performance of the classical shadows protocol in practical applications.
License type:
Attribution 4.0 International (CC BY 4.0)
Funding Info:
This research / project is supported by the Agency for Science, Technology and Research - Central Research Fund - Use-Inspired Basic Research (UIBR)
Grant Reference no. : NA
This research / project is supported by the National Research Foundation, and Agency for Science, Technology and Research - Quantum Engineering Programme
Grant Reference no. : NRF2021-QEP2-02-P03
Description:
For the publisher's version, refer here: https://iopscience.iop.org/article/10.1088/2058-9565/addffd