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^{2}) measurement bases are both necessary and sufficient for worst-case optimal shadow estimation for a d-dimensional system 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 O(logn)-depth circuits on n qubits-enable optimal average-case protocols with remarkably simple measurement strategies. Our results establish a fundamental complexity separation: worst-case estimation requires Θ(d^{2}) bases, whereas average-case performance requires only Θ(d) bases, with broad implications for quantum information theory and near-term experiments.