# Classical Shadows with Improved Median-of-Means Estimation

arXiv: https://arxiv.org/abs/2412.03381 · HTML: https://mlsanity.com/paper/2412.03381/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 90 references that are in the map.
- First posted on arXiv 4 Dec 2024.

## Builds on (most cited first, 12 of 12)

- [Predicting Many Properties of a Quantum System from Very Few Measurements](https://mlsanity.com/paper/2002.08953/) (2020)
- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Provably efficient machine learning for quantum many-body problems](https://mlsanity.com/paper/2106.12627/) (2021)
- [Efficient quantum tomography II](https://mlsanity.com/paper/1612.00034/) (2016)
- [Shadows of quantum machine learning](https://mlsanity.com/paper/2306.00061/) (2023)
- [Improved machine learning algorithm for predicting ground state properties](https://mlsanity.com/paper/2301.13169/) (2023)
- [Efficient estimation of Pauli observables by derandomization](https://mlsanity.com/paper/2103.07510/) (2021)
- [Distributed Statistical Estimation and Rates of Convergence in Normal Approximation](https://mlsanity.com/paper/1704.02658/) (2017)
- [Classical Shadows With Noise](https://mlsanity.com/paper/2011.11580/) (2020)
- [Efficient median of means estimator](https://mlsanity.com/paper/2305.18681/) (2023)
- [Sample-optimal classical shadows for pure states](https://mlsanity.com/paper/2211.11810/) (2022)
- [Decision Diagrams for Quantum Measurements with Shallow Circuits](https://mlsanity.com/paper/2105.06932/) (2021)

## Abstract (arXiv)

The classical shadows protocol, introduced by Huang et al. [Nat. Phys. 16, 1050 (2020)], makes use of the median-of-means (MoM) estimator to efficiently estimate the expectation values of M observables with failure probability δ using only O(log(M/δ)) 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 [PMLR 195, 5925 (2023)] 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 (GHZ) 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.