Optimal Shadow Estimation with Minimal Measurement Settings

Shadow estimation is a powerful framework for predicting quantum properties from randomized measurements. While 3-design protocols achieve optimal worst-case performance, the minimal number of measurement bases required for such optimality has remained open. Here we prove that Θ\(d²\) measurement bases are both necessary and sufficient for worst-case optimal shadow estimation and construct an explicit basis family. In stark contrast, any state 2-design already suffices for average-case optimality: the mean squared shadow norm of normalized observables is bounded by a universal constant, and we prove strong concentration for Haar-random states, yielding constant sample complexity for generic pure-state fidelity estimation. Easily implementable 2-designs - from mutually unbiased bases, cyclic measurements, or shallow mathcal{O}\(log n\)-depth circuits - enable optimal average-case protocols with remarkably simple measurement strategies. Our results establish a fundamental complexity separation: worst-case estimation requires Θ\(d²\) bases, whereas average-case performance requires only Θ(d) bases, with broad implications for quantum information theory and near-term experiments.