Introduction—Characterizing quantum systems efficiently is a central challenge in quantum science and technology. Full quantum state tomography demands resources that scale exponentially with system size, motivating the development of more targeted approaches. The classical shadow framework [1] provides a powerful alternative: randomized measurements paired with classical post-processing can predict key properties of an unknown quantum state—including expectation values, fidelities, and entanglement witnesses—without full state reconstruction. Shadow estimation has since found broad applications in fidelity estimation [2]–[5], entanglement detection [6]–[11], and Hamiltonian learning [12]–[15], with experimental demonstrations on photonic [16], [17], superconducting [18], [19], and trapped-ion [6], [20] platforms. In practice, the number of distinct measurement bases directly determines the calibration and implementation cost of a shadow protocol, making the identification of minimal measurement schemes a pressing concern.

A shadow estimation protocol is specified by a measurement ensemble \(\mathcal{E}\) of weighted pure states forming a rank-one positive operator-valued measure (POVM) [1], [21], [22]. Its efficiency is governed by the shadow norm \(\|O\|_\mathcal{E}\) of the target observable \(O\), which characterizes the single-shot estimation variance: to estimate an expectation value within additive error \(\varepsilon\), \(\mathcal{O}(\|O\|_\mathcal{E}^2/\varepsilon^2)\) samples suffice regardless of the unknown state. Protocols based on unitary 3-designs—such as the multiqubit Clifford group [23], [24]—achieve the optimal worst-case shadow norm \(\|O\|_\mathcal{E}^2\leq 3\|O\|_2^2\) [1], but require large, highly structured ensembles, which are challenging to implement on near-term hardware. Simpler schemes based on state 2-designs—such as complete sets of mutually unbiased bases (MUBs) [25]–[27] and cyclic measurements [28]—are far more practical, yet their worst-case squared shadow norm grows linearly in \(d\), rendering them suboptimal.

Despite rapid recent progress on shadow estimation based on various measurement ensembles [1], [29]–[39], existing approaches either fail to achieve uniformly efficient estimation for general observables or rely on measurements with superpolynomially many outcomes. A fundamental question therefore remains open: What is the minimal measurement complexity required for optimal shadow estimation, and can simple measurements still be efficient in typical scenarios?

Here we provide a complete answer, revealing a striking complexity separation. First, we prove that \(\Theta(d^2)\) measurement bases are both necessary and sufficient for worst-case optimal shadow estimation, and construct an explicit basis family from phase 3-designs and MUBs. Second, we show that any state 2-design already achieves average-case optimal performance with only \(\Theta(d)\) bases: the mean squared shadow norm over arbitrary target observables is bounded by \(\left(2\sqrt{2}+1\right)\|O\|_2^2\) (Theorem 3). For normalized observables, this bound evaluates to a constant independent of \(d\), close to the 3-design optimum. The worst-case suboptimality of 2-designs thus vanishes in typical scenarios. Third, for fidelity estimation of Haar-random target states, we establish strong concentration of the shadow norm, yielding constant sample complexity for generic pure states even with simple 2-design measurements.

Our results reveal a fundamental \(d^2\)-versus-\(d\) gap between worst-case and average-case measurement complexities, demonstrating that easily implementable ensembles—including complete sets of MUBs, cyclic measurements, and shallow \(\mathcal{O}(\log n)\)-depth circuits [19], [40]–[42]—already realize optimal protocols for typical tasks. Meanwhile, our results highlight the foundational significance of MUBs and symmetric informationally complete (SIC) measurements [43]–[45] in quantum learning.

Preliminaries—Let \(\mathcal{H}\) be a \(d\)-dimensional complex Hilbert space (\(d\geq 2\)). Denote by \(\mathcal{L}(\mathcal{H})\) and \(\mathcal{L}^{\mathrm{H}}_0(\mathcal{H})\) the spaces of linear operators and traceless Hermitian operators on \(\mathcal{H}\), respectively; denote by \(\mathcal{D}(\mathcal{H})\) the set of density operators, and by \(\mathcal{P}(\mathcal{H})\subset\mathcal{D}(\mathcal{H})\) the subset of pure states. For a general operator \(O\in \mathcal{L}(\mathcal{H})\), we denote by \(O_0=O-\mathop{\mathrm{tr}}(O)\mathbb{1}/d\) the traceless part of \(O\), where \(\mathbb{1}\) is the identity operator; for a pure state \(\ket{\phi}\in\mathcal{H}\), we write \(\phi=\ket{\phi}\mkern-2mu\bra{\phi}\) and \(\phi_0=\phi-\mathbb{1}/d\). The notation \(\|\cdot\|_p\) is used for the Schatten \(p\)-norm and \(\|\cdot\|\) for the operator norm.

Given a positive integer \(t\), a state \(t\)-design is a weighted ensemble of pure states whose \(t\)-th moment reproduces the Haar average; it mimics Haar-random states up to \(t\)-th order statistics [44]–[47]. State 2-designs can be realized by SIC ensembles [43]–[45], complete sets of MUBs [25]–[27], or cyclic constructions [28]; the set of multiqubit stabilizer states forms a state 3-design [23], [24], [48]. Unitary \(t\)-designs are defined analogously for ensembles of unitary operators.

A shadow estimation protocol is specified by a state ensemble \(\mathcal{E}=\{\ket{\phi_i},w_i\}_i\) with \(w_i>0\) and \({\sum_i w_i \phi_i=\mathbb{1}/d}\), which ensures that \(\{d\,w_i\phi_i\}_i\) forms a valid rank-one POVM on \(\mathcal{H}\). The associated measurement channel is \[\begin{align} \label{eq:MeasCh} \mathcal{M}_\mathcal{E}(O) = d\sum_i w_i \mathop{\mathrm{tr}}(\phi_i O)\,\phi_i. \end{align}\tag{1}\] When \(\mathcal{E}\) is informationally complete (IC), i.e., \(\{\phi_i\}_i\) spans \(\mathcal{L}(\mathcal{H})\), the channel \(\mathcal{M}_\mathcal{E}\) is invertible. The inverse \(\mathcal{M}_\mathcal{E}^{-1}\) acts as the reconstruction map: each snapshot \(\hat{\rho}_i \mathrel{\vcenter{:}}= \mathcal{M}_\mathcal{E}^{-1}(\phi_i)\) satisfies \(\mathbb{E}[\hat{\rho}_i] = \rho\), making it an unbiased estimator of \(\rho\). Consequently, \(\mathop{\mathrm{tr}}(O \hat{\rho}_i)\) is an unbiased estimator of \(\mathop{\mathrm{tr}}(O\rho)\) for any observable \(O\).

The sample complexity of estimating \(\mathop{\mathrm{tr}}(O\rho)\) to accuracy \(\varepsilon\) with constant success probability scales as \(\|O_0\|_\mathcal{E}^2/\varepsilon^2\) [1], where the squared shadow norm is defined as follows. For a traceless observable \(O_0\in\mathcal{L}^{\mathrm{H}}_0(\mathcal{H})\) (the traceless part of \(O\)), the state-dependent variant is \[\begin{align} \label{eq:normSD} \|O_0\|_{\mathcal{E},\rho}^2 \mathrel{\vcenter{:}}= d\sum_i w_i \mathop{\mathrm{tr}}(\phi_i\rho)\bigl[\mathop{\mathrm{tr}}\bigl(O_0\,\hat{\rho}_i\bigr)\bigr]^2, \end{align}\tag{2}\] and the state-independent (worst-case) one is \(\|O_0\|_\mathcal{E}^2 \mathrel{\vcenter{:}}= \max_{\rho\in\mathcal{D}(\mathcal{H})} \|O_0\|_{\mathcal{E},\rho}^2\). The worst-case norm provides a universal guarantee for all unknown states, while its \(\rho\)-dependent counterpart quantifies performance for a given target state and can be substantially smaller. Henceforth, observables are assumed traceless except in the context of fidelity estimation or otherwise stated.

A key quantity in our analysis is the normalized \(t\)-th frame potential \[\label{eq:FPt} \bar{\Phi}_t(\mathcal{E}) \mathrel{\vcenter{:}}= D_{[t]}\,\Phi_t(\mathcal{E}),\;\; \Phi_t(\mathcal{E}) \mathrel{\vcenter{:}}= \sum_{i,j} w_i w_j \bigl[\mathop{\mathrm{tr}}(\phi_i\phi_j)\bigr]^t,\tag{3}\] where \(D_{[t]}=\binom{d+t-1}{t}\) is the dimension of the symmetric subspace of \(\mathcal{H}^{\otimes t}\). It is well known that \(\bar{\Phi}_t(\mathcal{E})\geq 1\), with equality if and only if \(\mathcal{E}\) forms a state \(t\)-design [45]–[47]. In this work, the case \(t=3\) plays the central role: \(\bar{\Phi}_3(\mathcal{E})\) quantifies how closely a 2-design approximates a 3-design and governs the performance gap in shadow estimation. For any state 2-design, its magnitude is controlled by:

Proposition 1 and other results are proved in Supplemental Material (SM) [49], which includes Refs. [50], [51].

Minimal optimal protocols in the worst-case setting—We first establish a fundamental lower bound on the worst-case shadow norm achievable with a given number of measurement outcomes.

This result encodes a fundamental trade-off: fewer measurement outcomes necessarily imply larger worst-case shadow norms. Achieving optimal worst-case performance—meaning \(\|O\|_\mathcal{E}^2\leq C\|O\|_2^2\) for a universal constant \(C\)—requires at least \(\Omega(d^3)\) outcomes, or equivalently \(\Omega(d^2)\) orthonormal bases, given that each basis corresponds to \(d\) outcomes. Incidentally, when \(\mathcal{E}\) forms a state 2-design, the worst-case shadow norm satisfies \(\|O\|_\mathcal{E}^2\leq (d+1)\|O\|_2^2\) [21], [34], [35]. For typical 2-designs consisting of \(\mathcal{O}(d^2)\) states—such as SICs and complete sets of MUBs—the lower and upper bounds match up to constant factors, demonstrating that standard 2-design measurements are suboptimal for worst-case performance. We now show that the \(\Omega(d^2)\)-basis lower bound is tight.

Our explicit construction achieving this scaling rests on two ingredients: phase 3-designs and MUBs. A pure state \(\ket{\phi}\in \mathcal{H}\) is a phase state with respect to the computational basis \(\{\ket{k}\}_k\) if all its entries have the same magnitude. A phase \(t\)-design is a finite ensemble of phase states whose \(t\)-th moment matches that of the uniform random-phase (URP) ensemble \[\label{eq:URPmain} \mathcal{T}= \left\{\frac{1}{\sqrt{d}}\sum_{k=0}^{d-1}\mathrm{e}^{\mathrm{i}\varphi_k}\ket{k}\colon \mathrm{e}^{\mathrm{i}\varphi_k}\sim \mathrm{U}(1)\right\},\tag{4}\] which geometrically forms a \(d\)-dimensional torus. Intuitively, a phase \(t\)-design captures the same statistical correlations as fully random phases up to order \(t\), using only finitely many states. Mathematically, it is equivalent to a projective toric \(t\)-design studied in Ref. [52]. As shown in the End Matter, a phase 2-design can be constructed from \(3p\) bases and a phase 3-design from \(7p^2\) bases, where \(p\) is any prime satisfying \(p \geq \max\{d,5\}\) and can be chosen such that \(p \leq \max\{2d,5\}\). When \(d\) is not divisible by \(3\), the number of bases required for a phase 3-design can be reduced to \(3p^2\). Since any phase \(t\)-design (with \(t\geq 1\)) is also a state 1-design, it gives rise to a valid POVM.

The construction proceeds as follows. Consider \(N\geq 2\) MUBs \(\mathcal{B}_1,\mathcal{B}_2,\ldots,\mathcal{B}_N\). For each basis \(\mathcal{B}_j\), we construct a phase 3-design \(\mathcal{E}_{\mathcal{B}_j}\) with respect to \(\mathcal{B}_j\). The combined ensemble \(\mathcal{E}_N=\bigsqcup_{j=1}^N \mathcal{E}_{\mathcal{B}_j}/N\) assigns uniform probability across all sub-ensembles and comprises at most \(7Np^2\) bases in total. MUBs ensure that the combined ensemble probes complementary degrees of freedom: while a single phase 3-design can only access coherence relative to its reference basis, MUBs guarantee that no observable direction is left unexplored.

Already for \(N=2\) MUBs, we have \(\|O\|_{\mathcal{E}_2}^2 \leq 14\|O\|_2^2\), achieving constant worst-case shadow norm with \(\Theta(d^2)\) bases—matching the lower bound from Proposition 2 up to a constant factor. The bound improves monotonically with \(N\): for \(N=d+1\) (a complete set of MUBs), the prefactor reads \(3+7/d+4/d^2\), which is quite close to the optimal value of \(3\) achieved by state 3-designs. In practice, \(N=2\) or \(3\) MUBs strike a favorable balance between measurement overhead and shadow norm, as adding MUBs rapidly decreases the prefactor at first but yields diminishing returns thereafter. The ensemble \(\mathcal{E}_N\) is not a state 2-design unless \(N=d+1\); nevertheless, the measurement channel \(\mathcal{M}_{\mathcal{E}_N}\) and reconstruction map \(\mathcal{M}_{\mathcal{E}_N}^{-1}\) both admit simple closed forms (see the End Matter), enabling straightforward construction of unbiased estimators.

Minimal optimal protocols for average performance—We now turn to average performance and show that far fewer measurement bases suffice. We call a protocol average-case optimal if the mean squared shadow norm over a unitary orbit—observables sharing the spectrum of \(O\) but with arbitrary eigenbases—is bounded by \(c\|O\|_2^2\) for a dimension-independent constant \(c\).

For \(O\in\mathcal{L}(\mathcal{H})\) and a unitary ensemble \(\mathcal{U}\) on \(\mathrm{U}(\mathcal{H})\), define the orbit \[\begin{align} \Xi(O,\mathcal{U})\mathrel{\vcenter{:}}= \left\{UOU^\dagger \mid U\sim\mathcal{U}\right\}. \end{align}\] Let \(\|\Xi(O,\mathcal{U})\|_\mathcal{E}^2\) denote the mean squared shadow norm averaged over \(\mathcal{U}\), and \(\|\Xi(O,\mathcal{U})\|_{\mathcal{E},\rho}^2\) its state-dependent counterpart. Note that \(\mathcal{U}\) defines only the observable class over which performance is averaged; it plays no role in the measurement protocol. For a unitary 2-design \(\mathcal{U}\) and a state 2-design \(\mathcal{E}\) [21], [53], we have \[\begin{align} \label{eq:SDopt} \|\Xi(O,\mathcal{U})\|_{\mathcal{E},\rho}^2 = \frac{d+1}{d}\|O\|_2^2, \end{align}\tag{5}\] so any state 2-design is already optimal in the state-dependent setting. However, this is of limited practical interest because \(\rho\) is usually unknown. The state-independent norm \(\|\Xi(O,\mathcal{U})\|_\mathcal{E}^2\), providing a universal guarantee regardless of \(\rho\), can be much larger; the following theorem bounds this gap.

The 4-design assumption on \(\mathcal{U}\) (satisfied, e.g., by the Haar measure) ensures sufficient moment control over the orbit. The parameter \(\bar{\Phi}_3\) quantifies deviation from a 3-design [\(\bar{\Phi}_3 = \mathcal{O}(d)\) for any state 2-design by Proposition 1]: at \(\bar{\Phi}_3=1\) the bound recovers the 3-design optimum \(3\|O\|_2^2\), while even the worst 2-design incurs at most a constant-factor overhead.

State 2-designs can be constructed from \(d^2+\mathcal{O}\left(d^{1.525}\right)\) states [54] or \(\mathcal{O}(d)\) orthonormal bases [55], [56]. Explicitly, mixing a fixed basis \(\mathcal{B}\) [with probability \(1/(d+1)\)] with a phase 2-design over \(\mathcal{B}\) [with probability \(d/(d+1)\)] yields a valid state 2-design. Meanwhile, a phase 2-design requires at most \(6d\) bases (Proposition 4 in the End Matter). Conversely, at least \(d^2\) states or \(d+1\) bases are necessary to construct an IC ensemble and guarantee finite shadow norms for all observables in \(\Xi(O,\mathcal{U})\), assuming that the orbit spans \(\mathcal{L}^{\mathrm{H}}_0(\mathcal{H})\).

The contrast is striking: average-case optimal shadow estimation requires only \(\Theta(d)\) bases, versus \(\Theta(d^2)\) in the worst case—a fundamental quadratic gap. Notably, ensembles as simple as complete sets of MUBs [25]–[27], cyclic measurements [28], or shallow \(\mathcal{O}(\log n)\)-depth circuits [40] already form state 2-designs and thus achieve average-case optimal performance, enabling practical protocols with unexpectedly economical measurement strategies. Moreover, \(d+1\) bases suffice to realize average-case optimal shadow estimation whenever \(d\) is a prime power, since a complete set of MUBs exists in every prime-power dimension [25]–[27]. Furthermore, if a SIC exists in every dimension—as conjectured and supported by strong evidence [43]–[45], [57]—then \(d^2\) outcomes suffice to realize a minimal optimal protocol.

Fidelity estimation—Predicting the fidelity \(\mathop{\mathrm{tr}}(\rho\psi)\) between an unknown state \(\rho\) and a known target state \(\psi\) is among the most important applications of shadow estimation, central to state verification, benchmarking, and certification [4], [5]. Here the observable is the projector \(\psi\), so sample complexity is governed by \(\|\psi_0\|_\mathcal{E}^2\) with \(\psi_0=\psi-\mathbb{1}/d\). Theorem 3 immediately bounds the mean squared shadow norm for Haar-random target states. The following proposition further establishes a large-deviation guarantee, whose proof requires an independent and considerably more involved argument (see SM Sec. 5).

For SIC ensembles and complete sets of MUBs, the normalized third frame potentials read \[\begin{align} \label{eq:bPhi3SICMUB} \bar{\Phi}_3(\mathcal{E}_\mathrm{SIC})=\frac{(d+2)(d+3)}{6(d+1)},\;\, \bar{\Phi}_3(\mathcal{E}_\mathrm{MUB})=\frac{(d+1)(d+2)}{6d}, \end{align}\tag{6}\] each scaling as \(d/6\) in the large-\(d\) limit and attaining near-maximal values among 2-designs (cf.Proposition 1). Nevertheless, Fig. 2 demonstrates that these canonical 2-designs already closely match the 3-design benchmark for average-case performance.

Since \(\bar{\Phi}_3(\mathcal{E})=\mathcal{O}(d)\) for any 2-design (Proposition 1), choosing \(k=\mathcal{O}\left(1/\sqrt{d}\mkern 2mu\right)\) in Eq. (?? ) yields \(\|\psi_0\|_\mathcal{E}^2=\mathcal{O}(1)\) except with probability \(\mathcal{O}(1/d^2)\). Hence, the shadow norm concentrates tightly around its mean for Haar-random \(\psi\), with a universally fast rate for all state 2-designs; dependence on \(\bar{\Phi}_3\) only marginally slows convergence for larger \(\bar{\Phi}_3\). States with anomalously large shadow norms thus form a vanishingly small subset of the state space: generic pure-state fidelity estimation achieves constant sample complexity with any 2-design measurement, constructible from only \(\mathcal{O}(d)\) bases. This stands in stark contrast to the \(\Theta(d^2)\) bases required for worst-case optimality.

For stabilizer measurements, by means of involved analysis, a universal upper bound on the shadow norm was established in Refs. [58], [59], scaling with local dimension but not qudit number. However, that bound cannot imply constant sample complexity for generic fidelity estimation. Our concentration result is stronger in this regard: the shadow norm remains \(\mathcal{O}(1)\) with high probability for any state 2-design, independent of both the system dimension and local dimension. This prediction is corroborated by numerical calculation on \(n\)-qudit stabilizer measurements, as illustrated in Fig. 3 in the End Matter.

Beyond Haar-random states, the mean squared shadow norm also admits constant upper bounds for other physically motivated ensembles of target states: URP ensembles, relevant to Hamiltonian simulation, and Clifford orbits, relevant to randomized benchmarking and quantum error correction (Proposition 6 in the End Matter).

Summary and outlook—We have determined the fundamental measurement complexity of shadow estimation. In the worst case, \(\Theta(d^2)\) bases are both necessary and sufficient for optimal performance; our explicit construction from phase 3-designs and MUBs achieves this without requiring exact state 3-design structure. In the average case, only \(\Theta(d)\) bases suffice: any state 2-design yields a constant mean squared shadow norm governed by \(\bar{\Phi}_3\). For fidelity estimation, the shadow norm concentrates tightly for Haar-random targets, implying constant sample complexity for generic instances. Together, these results reveal a sharp quadratic gap between worst-case and average-case complexities: \(d^2\) versus \(d\) bases. For a \(10\)-qubit system, this reduces the required number of bases from \({\sim}10^6\) to \({\sim}10^3\), demonstrating that the practical cost can be far lower than the worst-case bound suggests.

Looking forward, extending these results to multipartite settings and structured observable classes—such as local Hamiltonians, where problem-specific structure may yield further reductions—remains an important open direction. On the practical side, easily implementable 2-designs—realized via complete sets of MUBs [34], [35], cyclic measurements [28], or shallow \(\mathcal{O}(\log n)\)-depth circuits [19], [40]–[42]—already achieve optimal average-case performance. This is especially relevant for decoherence-limited devices, where measurement overhead is a primary bottleneck. Finally, connections with Hamiltonian-driven shadow protocols [32], [33] offer a promising route: the system’s intrinsic dynamics could naturally generate structured measurements, enabling optimal shadow estimation without external randomization.

Acknowledgments—We thank Changhao Yi, Xiaodi Li, and Xinyang Shu for inspiring discussions. This work is supported by Shanghai Science and Technology Innovation Action Plan (Grant No.24LZ1400200), National Natural Science Foundation of China (Grant No.), Quantum Science and Technology-National Science and Technology Major Project (Grant No.2024ZD0300101), National Key Research and Development Program of China (Grant No.2022YFA1404204), and Shanghai Municipal Science and Technology Major Project (Grant No.2019SHZDZX01).

Appendix A: Reconstruction map for the combined phase-design ensemble \(\mathcal{E}_N\)—Consider \(N\geq 2\) MUBs \(\mathcal{B}_1,\mathcal{B}_2,\ldots,\mathcal{B}_N\) and the ensemble \(\mathcal{E}_N\) used in Theorem 2. Any operator \(O\in\mathcal{L}(\mathcal{H})\) can be decomposed as \[\begin{align} O = \frac{\mathop{\mathrm{tr}}(O)\mathbb{1}}{d} + O_\perp + \sum_{j=1}^{N} O_{\mathcal{B}_j}, \end{align}\] where \(O_{\mathcal{B}_j}\) denotes the traceless component diagonal in basis \(\mathcal{B}_j\), and \(O_\perp\) is the component orthogonal to all \(\mathcal{B}_j\)-diagonal operators, which vanishes when \(N=d+1\). With respect to this decomposition, the reconstruction map takes the simple form \[\begin{align} \label{eq:ReconMap} \mathcal{M}_{\mathcal{E}_N}^{-1}(O) = \frac{\mathop{\mathrm{tr}}(O)\mathbb{1}}{d} + dO_\perp + \sum_{j=1}^{N}\frac{Nd}{N-1}O_{\mathcal{B}_j}. \end{align}\tag{7}\] For a complete set of MUBs (\(N=d+1\)), the ensemble \(\mathcal{E}_N\) forms a 2-design, and the reconstruction map reduces to the familiar form \(\mathcal{M}_{\mathcal{E}_{d+1}}^{-1}(O) = (d+1)O - \mathop{\mathrm{tr}}(O)\mathbb{1}\) [1].

Appendix B: Construction of nearly tight phase 2- and 3-designs from orthonormal bases—To construct a phase 2-design (3-design), at least \(\Theta(d^2)\) (\(\Theta(d^3)\)) states are required. Here we provide nearly tight constructions from orthonormal bases. In the case of phase 2-designs, our construction is a reformulation of the construction in Ref. [56], but in a much simpler language. This reformulation is crucial to generalization to phase 3-designs.

Given any positive integer \(t\), define the function \[f_t(x)\mathrel{\vcenter{:}}= \left\lfloor \frac{tx}{d}\right\rfloor,\quad x\in \mathscr{I}:= \{0,1,\ldots,d-1\}.\] Let \(p\) be any prime that satisfies \(p\geq\max\{d,3\}\). Then a phase 2-design can be constructed as follows: \[\label{eq:caT2} \begin{gather} \mathcal{T}_2\mathrel{\vcenter{:}}= \left\{\ket{\psi_2(a,b,c)} \colon a\in \mathbb{Z}_d,\, b\in \mathbb{Z}_3,\, c\in \mathbb{Z}_p\right\},\\ \ket{\psi_2(a,b,c)}\mathrel{\vcenter{:}}= \frac{1}{\sqrt{d}} \sum_{x\in \mathscr{I}} \omega_d^{ax}\omega_3^{bf_2(x)}\omega_p^{cx^2}\ket{x}, \end{gather}\tag{8}\] where \(\omega_k=\mathrm{e}^{2\pi\mathrm{i}/k}\) for a positive integer \(k\) is a primitive \(k\)-th root of unity; note that \(\mathcal{T}_2\) is composed of \(3p\) bases. When \(d\) is odd, we have an alternative construction using only \(2p\) bases: \[\label{eq:tcaT2} \begin{gather} \tilde{\mathcal{T}}_2\mathrel{\vcenter{:}}=\left\{\ket{\tilde{\psi}_2(a,b,c)} \colon a\in \mathbb{Z}_d,\, b\in \mathbb{Z}_2,\, c\in \mathbb{Z}_p\right\},\\ \ket{\tilde{\psi}_2(a,b,c)}\mathrel{\vcenter{:}}=\frac{1}{\sqrt{d}} \sum_{x\in \mathscr{I}} \omega_d^{ax}\omega_2^{bx}\omega_p^{cx^2}\ket{x}. \end{gather}\tag{9}\]

Next, we turn to phase 3-designs. Let \(p\) be any prime that satisfies \(p\geq\max\{d,5\}\). Then a phase 3-design can be constructed as follows: \[\label{eq:caT3} \begin{gather} \mathcal{T}_3\mathrel{\vcenter{:}}=\left\{\ket{\psi_3(a,b,c)} \colon a\in \mathbb{Z}_d,\, b\in \mathbb{Z}_7,\, c_2, c_3\in \mathbb{Z}_p\right\},\\ \ket{\psi_3(a,b,c)}\mathrel{\vcenter{:}}=\frac{1}{\sqrt{d}} \sum_{x\in \mathscr{I}} \omega_d^{ax}\omega_7^{bf_3(x)}\omega_p^{c_2x^2+c_3x^3}\ket{x}; \end{gather}\tag{10}\] note that \(\mathcal{T}_3\) is composed of \(7p^2\) bases. When \(d\) is not divisible by \(3\), we have an alternative construction using only \(3p^2\) bases: \[\label{eq:tcaT3} \begin{gather} \tilde{\mathcal{T}}_3\mathrel{\vcenter{:}}=\left\{\ket{\tilde{\psi}_3(a,b,c)} \colon a\in \mathbb{Z}_d,\, b\in \mathbb{Z}_3,\, c_2, c_3\in \mathbb{Z}_p\right\},\\ \ket{\tilde{\psi}_3(a,b,c)}\mathrel{\vcenter{:}}=\frac{1}{\sqrt{d}} \sum_{x\in \mathscr{I}} \omega_d^{ax}\omega_3^{bx}\omega_p^{c_2x^2+c_3x^3}\ket{x}. \end{gather}\tag{11}\]

Proposition 5 is a simple corollary of Lemma 2 in SM Sec. 1; Proposition 4 follows from similar but simpler reasoning. It is well known that, for any positive integer \(d\), there exists a prime \(p\) with \(p\leq 2d\) [60]. Therefore, for any dimension \(d\), a phase 2-design can be constructed from no more than \(6d\) bases, while a phase 3-design can be constructed from no more than \(28d^2\) bases. In the large-\(d\) limit, it is possible to tighten these bounds.

Appendix C: Numerical evidence for concentration in stabilizer shadow estimation—Figure 3 plots the probability upper bound from Proposition 3 for the event \(\|\psi_0\|_{\mathcal{E}}^2 \geq 9\). Here, \(\psi\) denotes a Haar-random pure state of \(n\) qudits with local dimension \(p\), and fidelity estimation is implemented via stabilizer measurements. These measurements form a Clifford orbit which, for odd prime \(p\), is a state 2-design but not a 3-design [23], [24], [48]. The worst-case shadow norm satisfies \(\|\psi_0\|_\mathcal{E}^2\leq 2p-1\) [58], with the bound approximately saturated by stabilizer states when \(n\geq 2\). This worst-case scaling with \(p\) might suggest suboptimality for fidelity estimation. However, Fig. 3 demonstrates that the large-deviation probability vanishes rapidly with increasing \(n\) for various choices of \(p\). The normalized third frame potential \(\bar{\Phi}_3(\mathcal{E})=(p+1)(d+2)/[3(d+p)]\) [59] approaches \((p+1)/3\) for large \(n\); together with Proposition 3, this yields an \(\mathcal{O}\left(1/d^2\right)\) tail bound that explains the observed concentration and confirms constant sample complexity for typical fidelity estimation. Related numerical observations were reported in Ref. [58]; our Theorem 3 and Proposition 3 provide the rigorous theoretical underpinning that has been missing in the prior work.

Appendix D: Fidelity estimation beyond Haar-random pure states—The main text establishes concentration for Haar-random target states. Here we show that constant mean squared shadow norms also hold for other physically motivated ensembles.

URP ensembles—The URP ensemble models long-time outputs of Hamiltonian evolution with random energy eigenvalues under a no-resonance condition [61], a standard setting in quantum thermalization. The bound Eq. (12 ) holds for the URP ensemble with respect to any orthonormal basis and converges to \(\sqrt{48}-1\approx 5.93\) as \(d\to\infty\), guaranteeing efficient fidelity estimation with any 2-design measurement regardless of system size.

Clifford orbits—The bound Eq. (13 ) is uniform over all initial states \(\psi\) and equals \(2\sqrt{15}-1\approx 6.75\). It applies to any Clifford orbit, including orbits of stabilizer states, central to quantum error correction, and magic states, relevant to magic state distillation. Since Clifford orbits arise naturally in verification and benchmarking, efficient fidelity estimation for these targets is particularly valuable in practice.

Comparison—Both bounds are slightly larger than the Haar-random mean of \(2\sqrt{2}+1\approx 3.83\), reflecting less randomness in these ensembles. Nevertheless, all three bounds are \(\mathcal{O}(1)\), confirming that constant sample complexity for fidelity estimation is a robust structural feature of 2-design measurements, not an artifact of Haar randomness.

In this Supplemental Material (SM), we prove the results presented in the main text and End Matter, including Propositions 1–6 as well as Theorems 2 and 3. In addition, we provide some auxiliary results on frame potentials, the combined phase-design ensemble based on MUBs (optimal for worst-case shadow estimation), and shadow norms.

As in the main text, let \(\mathcal{H}\) be a complex Hilbert space of dimension \(d\ge2\). Denote by \(\mathcal{L}(\mathcal{H})\), \(\mathcal{L}^{\mathrm{H}}(\mathcal{H})\), \(\mathcal{L}_0(\mathcal{H})\), and \(\mathcal{L}^{\mathrm{H}}_0(\mathcal{H})\) the spaces of linear operators, Hermitian operators, traceless operators, and traceless Hermitian operators on \(\mathcal{H}\), respectively. Denote by \(\mathcal{D}(\mathcal{H})\) the set of density operators on \(\mathcal{H}\) and by \(\mathcal{P}(\mathcal{H})\) the subset of pure state projectors. For any operator \(O \in \mathcal{L}(\mathcal{H})\), we write \(O_0=O-\mathop{\mathrm{tr}}(O)\mathbb{1}/d\) for the traceless part of \(O\); for any pure state \(\ket{\phi} \in \mathcal{H}\), we write \(\phi = \ket{\phi}\mkern-2mu\bra{\phi}\) for the corresponding projector and \(\phi_0=\phi-\mathbb{1}/d\). Given a positive integer \(t\), denote by \(P_{[t]}\) the projector onto the \(t\)-partite symmetric subspace of \(\mathcal{H}^{\otimes t}\) and by \(D_{[t]}=\mathop{\mathrm{tr}}(P_{[t]})\) the dimension of the symmetric subspace.

We also introduce the vectorization map between operators on \(\mathcal{H}\) and vectors in \(\mathcal{H}\otimes \mathcal{H}\). For any \(O \in \mathcal{L}(\mathcal{H})\), its vectorization is defined in the computational basis \(\{\ket{k}\}_{k=0}^{d-1}\) as \[\begin{align} \dket{O} \mathrel{\vcenter{:}}= \sum_{k,l} O_{kl}\ket{k}\otimes \ket{l}, \end{align}\] where \(O_{kl}=\bra{k}O\ket{l}\).

1 State \(t\)-designs and phase \(t\)-designs↩︎

Here we discuss state \(t\)-designs and phase \(t\)-designs in more detail and derive auxiliary results relevant to this work.

Let \(\mathcal{E}= \{\ket{\phi_i}, w_i\}_{i}\) be an ensemble of pure states in \(\mathcal{H}\), where \(w_i>0\) and \(\sum_i w_i=1\). The \(t\)-th moment operator and normalized moment operator of \(\mathcal{E}\) are defined as \[Q_t(\mathcal{E})\mathrel{\vcenter{:}}=\sum_i w_i\phi_i^{\otimes t}, \quad \bar{Q}_t(\mathcal{E})\mathrel{\vcenter{:}}= D_{[t]}Q_t(\mathcal{E}).\] The \(t\)-th frame potential and normalized \(t\)-th frame potential of \(\mathcal{E}\) are defined as [see Eq. (3 )] \[\label{eq:FPtSupp} \Phi_t(\mathcal{E}) \mathrel{\vcenter{:}}= \sum_{i,j} w_i w_j \bigl[\mathop{\mathrm{tr}}(\phi_i\phi_j)\bigr]^t,\quad \bar{\Phi}_t(\mathcal{E}) \mathrel{\vcenter{:}}= D_{[t]}\,\Phi_t(\mathcal{E}),\tag{14}\] which can also be expressed as \[\Phi_t(\mathcal{E})=\mathop{\mathrm{tr}}\left\{[Q_t(\mathcal{E})]^2\right\},\quad \bar{\Phi}_t(\mathcal{E})=D_{[t]}\mathop{\mathrm{tr}}\left\{[Q_t(\mathcal{E})]^2\right\}=\frac{\mathop{\mathrm{tr}}\left\{[\bar{Q}_t(\mathcal{E})]^2\right\}}{D_{[t]}}.\] By definition, we have \[\label{eq:Phittp1} \Phi_{t+1}(\mathcal{E}) \leq \Phi_t(\mathcal{E}),\quad \bar{\Phi}_{t+1}(\mathcal{E})\leq \frac{d+t}{t+1} \bar{\Phi}_t(\mathcal{E}),\tag{15}\] given that \(D_{[t+1]}=(d+t)D_{[t]}/(t+1)\).

1.1 Haar-random states and state \(t\)-designs↩︎

State \(t\)-designs, also known as complex projective \(t\)-designs, are configurations of pure states whose \(t\)-th moments match those of Haar-random states [44]–[47]. They can be viewed as the complex analog of spherical designs on the real unit sphere and have found applications in areas such as approximation theory, combinatorics, and quantum information. The ensemble \(\mathcal{E}\) is a state \(t\)-design if \(\bar{Q}_t(\mathcal{E})=P_{[t]}\). It is known that \(\bar{\Phi}_t(\mathcal{E})\geq 1\), and the lower bound is saturated if and only if \(\mathcal{E}\) is a \(t\)-design. In addition, any state \(t\)-design in dimension \(d\) has at least \[\begin{align} \binom{d+\lceil t/2\rceil-1}{\lceil t/2\rceil} \binom{d+\lfloor t/2\rfloor-1}{\lfloor t/2\rfloor} \end{align}\] elements [46], [50]; the lower bound simplifies to \(d^2\) and \(d^2(d+1)/2\) for \(t=2\) and \(t=3\), respectively. When \(t=2\), the lower bound is saturated if and only if the ensemble \(\mathcal{E}\) induces a SIC-POVM. It is conjectured and supported by strong evidence that a SIC exists in every finite dimension [43]–[45], [57]. In sharp contrast, it remains open whether a 3-design can always be constructed using only \(\mathcal{O}(d^3)\) states. As a prominent example, the set of \(n\)-qubit stabilizer states forms a 3-design [23], [24], [48], yet the number of such states grows superpolynomially with dimension \(d\).

1.2 Uniform random phase states and phase \(t\)-designs↩︎

Given a positive integer \(t\), two sequences \(\boldsymbol{k},\boldsymbol{l}\in \{0,1,\dots,d-1\}^t\) are said to be equivalent if one can be obtained from the other by a permutation of entries. The equivalence class of \(\boldsymbol{k}\) is denoted by \([\boldsymbol{k}]\), and its cardinality by \(|[\boldsymbol{k}]|\). Let \(\mathcal{B}= \{\ket{k}_\mathcal{B}\}_{k=0}^{d-1}\) be an orthonormal basis of \(\mathcal{H}\). For each equivalence class \([\boldsymbol{k}]\), we define the corresponding symmetric ket in \(\mathcal{H}^{\otimes t}\) by \[\begin{align} \ket{[\boldsymbol{k}]}_\mathcal{B}\mathrel{\vcenter{:}}= \frac{1}{\sqrt{|[\boldsymbol{k}]|}} \sum_{\boldsymbol{l}\in [\boldsymbol{k}]} \ket{l_1}_\mathcal{B}\otimes \cdots \otimes \ket{l_t}_\mathcal{B}. \end{align}\] Recall that the uniform random phase (URP) ensemble \(\mathcal{T}_\mathcal{B}\) with respect to \(\mathcal{B}=\{\ket{k}_\mathcal{B}\}\) has the form \[\mathcal{T}_\mathcal{B}=\left\{\frac{1}{\sqrt{d}} \sum_{k=0}^{d-1} \mathrm{e}^{\mathrm{i}\varphi_k} \ket{k}_\mathcal{B}\colon \mathrm{e}^{\mathrm{i}\varphi_k}\sim \mathrm{U}(1)\right\}, \label{eq:URPsupp}\tag{16}\] where \(\varphi = (\varphi_0, \varphi_1, \dots, \varphi_{d-1})\) is uniformly distributed over \([0,2\pi)^d\). When \(\mathcal{B}\) is the computational basis, we omit the subscript \(\mathcal{B}\) and simply write \(\mathcal{T}\).

We now define phase designs. Let \(\mathcal{E}_\mathcal{B}\) be an ensemble of phase states (equal-modulus states) of the form \[\begin{align} \label{eq:PhaseState} \ket{\phi} = \frac{1}{\sqrt d} \sum_{k=0}^{d-1}\mathrm{e}^{\mathrm{i}\varphi_k}\ket{k}_\mathcal{B}. \end{align}\tag{17}\] The ensemble \(\mathcal{E}_\mathcal{B}\) is called a phase \(t\)-design with respect to \(\mathcal{B}\) if \[\begin{align} Q_t(\mathcal{E}_\mathcal{B}) = Q_t(\mathcal{T}_\mathcal{B}). \end{align}\] By definition, any phase \(t\)-design with \(t\geq 1\) is also a state 1-design and thus defines a POVM. In addition, a phase \(t\)-design determines a projective toric \(t\)-design [52], and vice versa.

1.3 Proof of Proposition 1↩︎

1.4 Proofs of Propositions 4 and 5↩︎

Proposition 5 is a simple corollary of the following lemma, which guarantees that the third moment operators of \(\mathcal{T}_3\) and \(\tilde{\mathcal{T}}_3\) have the form in Lemma 1. Proposition 4 follows from similar but simpler reasoning.

1.5 Auxiliary results on frame potentials↩︎

Here we introduce auxiliary results on (normalized) frame potentials and their variants, which are useful for studying shadow norms in shadow estimation.

Suppose \(\mathcal{E}=\{\ket{\phi_{i}}, w_i\}_{i}\) is a pure state ensemble on \(\mathcal{H}\) and \(\psi \in \mathcal{P}(\mathcal{H})\). We define the \(t\)-th frame potential of \(\mathcal{E}\) relative to \(\psi\) and its normalized version as \[\begin{align} \Phi_t(\mathcal{E},\psi)\mathrel{\vcenter{:}}=\sum_iw_i\left[\mathop{\mathrm{tr}}(\psi \phi_i)\right]^t,\quad \bar{\Phi}_t(\mathcal{E},\psi)\mathrel{\vcenter{:}}= D_{[t]}\Phi_t(\mathcal{E},\psi). \end{align}\] where \(D_{[t]}=\binom{d + t - 1}{t}\) is the dimension of the symmetric subspace of \(\mathcal{H}^{\otimes t}\). These definitions are also applicable when \(t=0\), in which case \(\bar{\Phi}_t(\mathcal{E},\psi)=\Phi_t(\mathcal{E},\psi)=\bar{\Phi}_t(\mathcal{E})=\Phi_t(\mathcal{E})=D_{[t]}=1\). By definition, \(\Phi_t(\mathcal{E})=\sum_j w_j\Phi_t(\mathcal{E},\phi_j)\), which implies \[\min_{\psi\in \mathcal{P}(\mathcal{H})} \Phi_t(\mathcal{E},\psi) \le \Phi_t(\mathcal{E}) \le \max_{\psi\in \mathcal{P}(\mathcal{H})} \Phi_t(\mathcal{E},\psi).\]

1.6 Proofs of auxiliary results Lemmas 3 and 6↩︎

2 Shadow estimation within the framework of rank-1 IC-POVMs↩︎

In this section we briefly introduce shadow estimation within the framework of rank-1 IC POVMs, following the presentation in the main text. Let \(\mathcal{E}= \{\ket{\phi_i}, w_i\}_i\) be a state ensemble that forms a \(1\)-design, which induces the POVM \(\{ d w_i \phi_i \}_i\). If \(\mathcal{E}\) is informationally complete (IC), any quantum state \(\rho \in \mathcal{D}(\mathcal{H})\) can be reconstructed as \(\rho = d \sum_i w_i \mathop{\mathrm{tr}}(\phi_i \rho)\, \hat{\rho}_i\), where \(\hat{\rho}_i\) is the estimator associated with outcome \(i\). When \(\mathcal{E}\) is informationally overcomplete, the choice of \(\hat{\rho}_i\) is not unique. In the shadow-estimation framework, one usually employs the canonical reconstruction, which is the standard choice in the absence of prior information about \(\rho\).

The canonical measurement channel can be represented in two equivalent ways. The first directly defines the channel action: \[\begin{align} \mathcal{M}_\mathcal{E}(\rho) &= d \sum_i w_i \mathop{\mathrm{tr}}(\phi_i \rho)\, \phi_i. \label{eq:FD1} \end{align}\tag{22}\] The second uses the vectorization (double-ket) notation. For any operator \(A \in \mathcal{L}^{\mathrm{H}}(\mathcal{H})\), we define its vectorization \(\dket{A} \in \mathcal{H}\otimes \mathcal{H}\) by expanding \(\dket{A} = \sum_{k,l} A_{kl}\, \ket{k}\otimes\ket{l}\) in a fixed orthonormal basis, so that the Hilbert–Schmidt inner product becomes \(\dbraket{A}{B}=\mathop{\mathrm{tr}}\left(A^\dagger B\right)\). The outer product \(\dketbra{A}{A} = \dket{A}\dbra{A}\) then acts as a linear operator on this space. With this notation the measurement channel becomes \[\begin{align} \mathcal{M}_\mathcal{E}= d \sum_i w_i \dketbra{\phi_i}{\phi_i}, \label{eq:FD2} \end{align}\tag{23}\] where \(\mathcal{M}_\mathcal{E}\) is viewed as an operator acting on vectorized operators via \(\mathcal{M}_\mathcal{E}\dket{A} = \dket{\mathcal{M}_\mathcal{E}(A)}\). This representation makes the positive semidefiniteness of \(\mathcal{M}_\mathcal{E}\) manifest and facilitates spectral analysis and inversion of the channel. By definition, \(\mathcal{M}_\mathcal{E}(\mathbb{1}) = \mathbb{1}\), so \(\mathbb{1}\) is an eigenoperator of \(\mathcal{M}_\mathcal{E}\) with eigenvalue \(1\). With a slight abuse of notation, we use \(\mathcal{M}_\mathcal{E}\) to denote both representations of the measurement channel when no confusion arises. Let \(\bar{\mathbf{I}}\) denote the projector onto the space of traceless Hermitian operators. The restricted channel is \[\begin{align} \bar{\mathcal{M}}_\mathcal{E}\mathrel{\vcenter{:}}= \bar{\mathbf{I}}\, \mathcal{M}_\mathcal{E}\, \bar{\mathbf{I}}= d \sum_i w_i \dketbra{\phi_{i,0}}{\phi_{i,0}}, \end{align}\] where \(\phi_{i,0} = \phi_i - \mathbb{1}/d\) is the traceless part of \(\phi_i\). Because \(\mathcal{E}\) forms a \(1\)-design, this simplifies to \[\begin{align} \bar{\mathcal{M}}_\mathcal{E}= \mathcal{M}_\mathcal{E}- \frac{1}{d}\dketbra{\mathbb{1}}{\mathbb{1}}. \end{align}\]

For any observable \(O \in \mathcal{L}^{\mathrm{H}}(\mathcal{H})\) and an IC-POVM \(\mathcal{M}= \{E_i\}_i\), the expectation value \(\mathop{\mathrm{tr}}(\rho O)\) can be estimated as \[\begin{align} \mathop{\mathrm{tr}}(\rho O) = \sum_i \mathop{\mathrm{tr}}(E_i \rho)\, \hat{o}_i, \end{align}\] where \(\hat{o}_i = \mathop{\mathrm{tr}}(\hat{\rho}_i O)\) and \(\hat{\rho}_i\) is the canonical reconstruction operator for outcome \(i\). The single-shot estimation variance reads \[\begin{align} \operatorname{Var}(\hat{o}) = \sum_i \mathop{\mathrm{tr}}(E_i \rho)\, \hat{o}_i^2 - [\mathop{\mathrm{tr}}(\rho O)]^2 = \sum_i \mathop{\mathrm{tr}}(E_i \rho)\, \hat{o}_{0,i}^2 - [\mathop{\mathrm{tr}}(\rho O_0)]^2, \end{align}\] where \(O_0 = O - \mathop{\mathrm{tr}}(O)\mathbb{1}/d\) is the traceless part of \(O\) and \(\hat{o}_{0,i} = \mathop{\mathrm{tr}}(\hat{\rho}_i O_0)\). The second equality shows that the variance depends solely on \(O_0\). The dominant term defines the state-dependent squared shadow norm: \[\begin{align} \|O_0\|_{\mathcal{E},\rho}^2 \mathrel{\vcenter{:}}= \sum_i \mathop{\mathrm{tr}}(E_i \rho)\, \hat{o}_{0,i}^2 = d \sum_i w_i \mathop{\mathrm{tr}}(\rho \phi_i) \left\{ \mathop{\mathrm{tr}}\left[ \phi_i\, \mathcal{M}_\mathcal{E}^{-1}(O_0) \right] \right\}^2=d\mathop{\mathrm{tr}}\left\{Q_3(\mathcal{E}) \left[\rho \otimes \mathcal{M}_{\mathcal{E}}^{-1}(O_0)\otimes \mathcal{M}_{\mathcal{E}}^{-1}(O_0)\right]\right\}, \label{eq:ShadowNormSD} \end{align}\tag{24}\] where \(\mathcal{M}_\mathcal{E}^{-1}\) denotes the inverse of the measurement channel. The (state-independent) squared shadow norm is obtained by maximizing \(\|O\|_{\mathcal{E},\rho}^2\) over all states: \[\begin{align} \|O_0\|_\mathcal{E}^2 \mathrel{\vcenter{:}}= \max_{\rho\in\mathcal{D}(\mathcal{H})} \|O_0\|_{\mathcal{E},\rho}^2 = \left\| d \sum_i w_i \phi_i \left\{ \mathop{\mathrm{tr}}\left[ \phi_i\, \mathcal{M}_\mathcal{E}^{-1}(O_0) \right] \right\}^2 \right\|=\left\|d\mathop{\mathrm{tr}}_{2,3}\left\{Q_3(\mathcal{E}) \left[\mathbb{1}\otimes \mathcal{M}_{\mathcal{E}}^{-1}(O_0)\otimes \mathcal{M}_{\mathcal{E}}^{-1}(O_0)\right]\right\}\right\|, \label{eq:norm2} \end{align}\tag{25}\] which applies to any traceless operator \(O_0 \in \mathcal{L}^{\mathrm{H}}_0(\mathcal{H})\).

If \(\mathcal{E}\) forms a state \(2\)-design, the measurement channel takes the simple form \[\begin{align} \mathcal{M}_\mathcal{E}= \frac{\mathbf{I}+ \dketbra{\mathbb{1}}{\mathbb{1}}}{d+1}, \end{align}\] where \(\mathbf{I}\) is the identity superoperator on \(\mathcal{L}^{\mathrm{H}}(\mathcal{H})\). Restricted to traceless operators, its inverse gives \[\begin{align} \mathcal{M}_\mathcal{E}^{-1}(O_0) = \bar{\mathcal{M}}_\mathcal{E}^{-1}(O_0) = (d+1)\, O_0. \end{align}\] Consequently, the squared shadow norm reduces to \[\begin{align} \|O_0\|_\mathcal{E}^2 = \left\| d(d+1)^2 \sum_i w_i \phi_i \left[ \mathop{\mathrm{tr}}(\phi_i O_0) \right]^2 \right\|=\left\|d(d+1)^2\mathop{\mathrm{tr}}_{2,3}\left[Q_3(\mathcal{E}) \left(\mathbb{1}\otimes O_0\otimes O_0\right)\right]\right\|. \end{align}\] If \(\mathcal{E}\) further forms a state \(3\)-design, then \(Q_3(\mathcal{E})=6P_{[3]}/[d(d+1)(d+2)]\), and we obtain the closed-form expression \[\begin{align} \|O_0\|_\mathcal{E}^2 = \frac{d+1}{d+2}\left( 2\|O_0\|^2 + \|O_0\|_2^2 \right) \le 3\|O_0\|_2^2. \end{align}\] For fidelity estimation, where the observable is a pure-state projector \(\psi\) with traceless part \(\psi_0 = \psi - \mathbb{1}/d\), the shadow norm evaluates to \[\begin{align} \|\psi_0\|_\mathcal{E}^2 = \frac{(3d-2)(d+1)(d-1)}{d^2(d+2)}. \label{eq:3design95pure} \end{align}\tag{26}\]

3 Proofs of results on worst-case optimal shadow estimation↩︎

3.1 Proof of Proposition 2↩︎

3.2 Auxiliary results on the combined phase-design ensemble based on MUBs↩︎

In this section, we clarify the basic properties of the combined phase 3-design ensemble \(\mathcal{E}_N\) with \(2\le N\le d+1\), as introduced in the main text, and provide a proof of Theorem 2. This ensemble is a uniform mixture of \(N\) phase 3-design ensembles \(\mathcal{E}_{\mathcal{B}_j}\) associated with \(N\) mutually unbiased bases (MUBs), denoted by \(\mathcal{B}_j=\{\ket{k}_{\mathcal{B}_j}\}_{k=0}^{d-1}\) for \(j=1,2,\ldots,N\). More precisely, \(\mathcal{E}_N\) can be expressed as follows: \[\begin{align} \mathcal{E}_N = \bigsqcup_{j=1}^{N} \frac{1}{N}\mathcal{E}_{\mathcal{B}_j}. \end{align}\]

Proposition 7 is a direct corollary of Lemma 1, and Proposition 8 follows from Proposition 7, given that the bases \(\mathcal{B}_1, \mathcal{B}_2, \ldots, \mathcal{B}_N\) are mutually unbiased. When \(N = d+1\), the \(N\) bases form a complete set of MUBs and thus constitute a 2-design, which implies that \[\frac{1}{Nd}\sum_{j=1}^{N}\sum_{k=0}^{d-1}(\ket{kk}\mkern-2mu\bra{kk})_{\mathcal{B}_j} = \frac{2P_{[2]}}{d(d+1)}.\] As a corollary, Proposition 7 yields \(Q_2(\mathcal{E}_N) = 2P_{[2]}/[d(d+1)]\), consistent with \(\mathcal{E}_N\) forming a 2-design.

Next, we decompose any operator \(O \in \mathcal{L}^{\mathrm{H}}(\mathcal{H})\) into orthogonal parts as \[\begin{align} O =\frac{\mathop{\mathrm{tr}}(O)}{d}\mathbb{1}+O_{\perp}+ \sum_{j=1}^{N} O_{\mathcal{B}_j} , \end{align}\] where \(O_{\mathcal{B}_j}\) denotes the traceless diagonal part of \(O\) with respect to basis \(\mathcal{B}_j\), and \(O_{\perp}\) is the remaining orthogonal component. When \(N=d+1\), we have \(O_{\perp}=0\).

3.3 Proof of Theorem 2↩︎

4 Fourth moments of Haar-random observables and Clifford orbits↩︎

4.1 Fourth moments of Haar-random observables↩︎

In preparation for studying the average shadow norm achieved by 2-design POVMs, we recall some basic results about Schur–Weyl duality for the unitary group.

Let \(\mathrm{U}(\mathcal{H})\) be the unitary group on \(\mathcal{H}\) and \(S_t\) the symmetric group of \(t\) numbers. According to Schur–Weyl duality, the \(t\)-th tensor power \(\mathcal{H}^{\otimes t}\) decomposes into a multiplicity-free direct sum of irreducible representations of \(\mathrm{U}(\mathcal{H}) \times S_t\): \[\begin{align} \mathcal{H}^{\otimes t}=\bigoplus_\lambda \mathcal{H}_\lambda=\bigoplus_\lambda \mathcal{W}_\lambda\otimes \mathcal{S}_\lambda, \end{align}\] where each \(\lambda\) labels a nonincreasing partition of \(t\) into at most \(d\) parts, \(\mathcal{W}_\lambda\) is the Weyl module carrying an irreducible representation of \(\mathrm{U}(\mathcal{H})\), and \(\mathcal{S}_\lambda\) is the Specht module carrying an irreducible representation of \(S_t\). The dimensions of \(\mathcal{W}_\lambda\) and \(\mathcal{S}_\lambda\) are denoted by \(D_\lambda\) and \(d_\lambda\), respectively. The projector \(P_{\lambda}\) onto \(\mathcal{H}_\lambda\) can be expressed as \[\begin{align} P_{\lambda}=\frac{d_\lambda}{24}\sum_{\sigma\in S_4}\chi_\lambda(\sigma)R(\sigma), \label{eq:Plambda} \end{align}\tag{35}\] where \(\chi_\lambda(\sigma)\) is the character of \(\sigma\) in the representation \(\lambda\), and \(R(\sigma)\) is the unitary operator representing the permutation \(\sigma\). By definition, \(\mathop{\mathrm{tr}}(P_\lambda)=\mathop{\mathrm{rank}}(P_\lambda)=d_\lambda D_\lambda\).

In the rest of this section, we focus on the case \(t = 4\). There are five potential partitions: \([4]\), \([2,2]\), \([2,1,1]\), \([3,1]\), and \([1,1,1,1]\), where \([2,1,1]\) is relevant when \(d\geq 3\), and \([1,1,1,1]\) is relevant when \(d\geq 4\). The dimensions of the Specht and Weyl modules for these partitions are presented in Table 1, and the corresponding characters in Table 2. Using Table 2 and Eq. (35 ), we obtain the following lemma.

4.2 Fourth moments of Clifford orbits↩︎

In this appendix, we focus on an \(n\)-qubit system, whose Hilbert space \(\mathcal{H}\) has dimension \(d = 2^n\).

Let \(\{I,X,Y,Z\}^{\otimes n}\) be the set of \(n\)-qubit Pauli operators. Then \(\{W^{\otimes 4}\mid W\in \{I,X,Y,Z\}^{\otimes n}\}\) forms a stabilizer group with stabilizer projector \[P_n=\frac{1}{d^2}\sum_{W\in \{I,X,Y,Z\}^{\otimes n}} W^{\otimes 4}.\] For a pure state \(\psi \in \mathcal{P}(\mathcal{H})\), the stabilizer 2-Rényi entropy [62] is defined as \[\begin{align} M_2(\psi)\mathrel{\vcenter{:}}=-\log_2\sum_{W\in\{I,X,Y,Z\}^{\otimes n}}\left[\mathop{\mathrm{tr}}(W\psi)\right]^4+\log_2 d = -\log_2\mathop{\mathrm{tr}}\left(P_n\psi^{\otimes 4}\right)-\log_2 d. \end{align}\] By definition, \(\mathop{\mathrm{tr}}\left(P_n\psi^{\otimes 4}\right)=2^{-M_2(\psi)}/d\). As established in Ref. [51], the stabilizer 2-Rényi entropy satisfies \[\begin{align} 0\le M_2(\psi)\le \log_2(d+1)-1 \quad \forall \psi\in \mathcal{P}(\mathcal{H}), \label{eq:stab95bound} \end{align}\tag{36}\] where the lower bound is saturated if and only if \(\psi\) is a stabilizer state. Under the action of the Clifford group, the symmetric subspace of \(\mathcal{H}^{\otimes 4}\) decomposes into two inequivalent irreducible components with projectors \[\begin{align} P_+=P_{[4]}P_n=P_nP_{[4]},\quad P_-=P_{[4]}(\mathbb{1}-P_n)=(\mathbb{1}-P_n)P_{[4]}, \end{align}\] and dimensions \[\begin{align} D^{+}_{[4]}=\mathop{\mathrm{tr}}(P_+)=\frac{(d+1)(d+2)}{6},\quad D^{-}_{[4]}=\mathop{\mathrm{tr}}(P_-)=\frac{(d^2-1)(d+2)(d+4)}{24}. \label{eq:D4pm} \end{align}\tag{37}\] By construction, we have \[\begin{align} \mathop{\mathrm{tr}}\left(P_+\psi^{\otimes 4}\right)=\mathop{\mathrm{tr}}\left(P_n\psi^{\otimes 4}\right)=\frac{2^{-M_2(\psi)}}{d},\quad \mathop{\mathrm{tr}}\left(P_-\psi^{\otimes 4}\right)=1-\frac{2^{-M_2(\psi)}}{d}\quad \forall \psi\in \mathcal{P}(\mathcal{H}). \label{eq:PpPmProb} \end{align}\tag{38}\]

The following lemma is a simple corollary of Lemma 11.

5 Proofs of results on average-case optimal shadow estimation↩︎

In this section, we prove our main results on optimal shadow estimation in the average-case setting, including Theorem 3 and Proposition 3 in the main text as well as Proposition 6 in the End Matter.

5.1 Auxiliary results on shadow norms↩︎

By definition in Eq. (?? ) and Lemma 14, it is straightforward to verify that \[\label{eq:func2} \frac{1}{d}\le r\le \frac{d-1}{d},\quad f(d,r) \le \frac{24}{d} - \frac{26}{d^2},\quad g(d,r) \le 4-\frac{g_d}{d},\quad g_d\mathrel{\vcenter{:}}=\begin{cases} 18 & d=2,\\ 22 & d=3,\\ 25 & d=4,5,\\ 29 &d\geq 6,\\ 30 &d\geq 7. \end{cases}\tag{39}\]

5.2 Proof of Theorem 3↩︎

5.3 Auxiliary results on shadow norms for fidelity estimation↩︎

Suppose \(\mathcal{E}=\{\ket{\phi_i},w_i\}_i\) is a state 2-design on \(\mathcal{H}\), \(\psi \in \mathcal{P}(\mathcal{H})\), and \(\psi_0=\psi-{\mathbb{1}}/{d}\). To better understand the properties of the squared shadow norm \(\|\psi_0\|_\mathcal{E}^2\) tied to fidelity estimation, we introduce some auxiliary results. Define \[J(\mathcal{E},\psi)\mathrel{\vcenter{:}}= d(d + 1)^2\sum_iw_i\left[\mathop{\mathrm{tr}}\left(\phi_i\psi\right)\right]^2\phi_{i},\quad \eta(\mathcal{E},\psi)\mathrel{\vcenter{:}}=\left\|J(\mathcal{E},\psi)\right\|. \label{eq:JN}\tag{43}\]

5.4 Proofs of Proposition 3 and Proposition 6↩︎

6 Further numerical results on mean squared shadow norms↩︎

In this appendix, we present additional numerical results on the mean squared shadow norms for several families of observables and state ensembles.

6.1 Shadow norms for fidelity estimation of Haar-random states↩︎

Here we provide additional results on shadow norms for fidelity estimation based on SIC-POVMs and complete sets of MUBs (available for prime-power dimensions). As in the main text, SIC-POVMs are generated by the Heisenberg–Weyl group from fiducial states listed in Ref. [57]; complete sets of MUBs are constructed according to Refs. [25], [27]. To complement Fig. 2 in the main text, Fig. 4 provides a refined comparison between SIC-POVMs and MUBs for Haar-random pure states, with error bars quantifying statistical fluctuations. Both measurement schemes exhibit convergence of the squared shadow norms toward their ensemble averages with increasing \(d\), indicating suppressed variability in higher dimensions. MUBs yield slightly narrower error bars at small \(d\), while the dispersion becomes comparable to that of SIC-POVMs at large \(d\), implying asymptotically similar performance.

6.2 Shadow norms for fidelity estimation of states in Clifford orbits↩︎

Next, we consider fidelity estimation of states in orbits of the \(n\)-qubit Clifford group using SIC-POVMs. Figure 5 (a) displays the ensemble averages \(\mathbb{E}_{U\sim\mathrm{Cl}(n)}\bigl\|U\psi_0 U^{\dagger}\bigr\|_{\mathcal{E}}^2\) for the stabilizer orbit and a random Clifford orbit. The mean values for the two orbits nearly coincide, especially for \(n\geq 3\). SIC-POVMs are generated by the Heisenberg–Weyl group from fiducial states listed in Ref. [57]; for the special case \(n=7\) (\(d=128\)), in which no fiducial is tabulated in that reference, we adopt the online database linked in Ref. [43].

6.3 Shadow norms for fidelity estimation of uniform random phase states↩︎

Next, we consider the ensemble \(\mathcal{T}\) of uniform random phase (URP) states defined over the computational basis. Figure 5 displays the mean squared shadow norms \(\mathbb{E}_{\psi\sim\mathcal{T}}\bigl\|\psi_0\bigr\|_{\mathcal{E}}^2\) for both SIC-POVMs and MUBs (one of the bases coincides with the computational basis). Both schemes exhibit similar scaling behavior, with SIC-POVMs maintaining a slight advantage across all dimensions shown except for \(d=2\).

6.4 Shadow norms of observables from the Gaussian unitary ensemble↩︎

Finally, we extend the analysis beyond pure-state observables to Hermitian operators sampled from the Gaussian unitary ensemble (GUE). For a state 2-design \(\mathcal{E}\), we introduce the normalized mean squared shadow norm \(\mathbb{E}_{O\sim\mathrm{GUE}}\bigl[\|O_0\|_{\mathcal{E}}^2/\|O_0\|_2^2\bigr]\), where \(O_0 = O - \mathop{\mathrm{tr}}(O)\,\mathbb{1}/d\) and the expectation is taken over the GUE. The following result parallels Proposition 10.

Numerical results in Fig. 6 (a) suggest that the mean moment ratio \(r\) converges to \(2/d\) as \(d\) increases, with negligible deviation for \(d\geq 10\). Figure 6 presents mean squared shadow norms over normalized traceless GUE observables for SIC-POVMs and MUBs. As benchmarks, the figure also displays the analytical upper bounds from Proposition 13 evaluated at \(r=2/d\) for the worse 2-design (Proposition 1) as well as SIC-POVMs and MUBs.

References↩︎