Pith. sign in

REVIEW 2 minor 69 references

Θ(d²) measurement bases are necessary and sufficient for worst-case optimal shadow estimation.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.3

2026-06-26 17:24 UTC pith:I4XJWGBA

load-bearing objection The paper closes the open question by proving Θ(d²) bases are necessary and sufficient for worst-case optimal shadow estimation with an explicit construction, while any 2-design suffices for average-case with concentration bounds.

arxiv 2606.20003 v1 pith:I4XJWGBA submitted 2026-06-18 quant-ph math-phmath.MP

Optimal Shadow Estimation with Minimal Measurement Settings

Zhiyao Yang , Datong Chen , Huangjun Zhu This is my paper
classification quant-ph math-phmath.MP
keywords shadow estimationrandomized measurementsmeasurement bases2-design3-designshadow normworst-case optimalityaverage-case performance
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that for shadow estimation to achieve optimal performance in the worst case over all states and observables, Θ(d²) distinct measurement bases are both required and sufficient, and it supplies an explicit construction of such a family. This matters because shadow estimation extracts quantum properties from randomized measurements, yet the number of distinct settings directly limits experimental feasibility on current hardware. By comparison, average-case optimality over typical states requires only a state 2-design, which bounds the mean squared shadow norm of normalized observables by a universal constant and yields strong concentration for Haar-random states. The result produces a clean complexity separation: worst-case protocols scale quadratically while average-case protocols scale linearly with dimension.

Core claim

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 enable optimal average-case protocols with remarkably simple measurement strategies.

What carries the argument

The number of distinct measurement bases required to reach the performance of a 3-design protocol in the shadow norm for worst-case optimality versus the performance of a 2-design for average-case optimality.

Load-bearing premise

That the shadow norm under 3-design protocols correctly captures the experimental requirements for worst-case optimality in randomized measurements.

What would settle it

An explicit protocol using o(d²) bases that achieves the same worst-case shadow-norm bound as a full 3-design, or a 2-design whose mean squared shadow norm for normalized observables grows with d.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • An explicit family of Θ(d²) bases realizes worst-case optimal shadow estimation.
  • Any state 2-design bounds the mean squared shadow norm of normalized observables by a universal constant.
  • Haar-random states exhibit strong concentration, giving constant sample complexity for generic pure-state fidelity estimation.
  • Mutually unbiased bases, cyclic measurements, and shallow O(log n)-depth circuits all suffice for average-case optimal protocols.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Near-term experiments can safely adopt 2-design protocols when worst-case guarantees are unnecessary, cutting the number of distinct settings from quadratic to linear in d.
  • The same separation between quadratic worst-case and linear average-case requirements may appear in other randomized quantum estimation tasks.
  • The explicit Θ(d²) constructions offer a concrete benchmark for testing whether real devices can approach information-theoretic limits in shadow estimation.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 2 minor

Summary. The manuscript proves that Θ(d²) measurement bases are both necessary and sufficient to achieve worst-case optimal shadow estimation (via the shadow norm), providing an explicit basis family construction. It shows that any state 2-design already suffices for average-case optimality, with the mean squared shadow norm of normalized observables bounded by a universal constant, strong concentration bounds for Haar-random states, and resulting constant sample complexity for generic pure-state fidelity estimation. Easily implementable 2-designs (MUBs, cyclic measurements, shallow circuits) are highlighted for practical use.

Significance. If the necessity/sufficiency proofs and concentration results hold, the work establishes a clear complexity separation (Θ(d²) bases for worst-case vs. Θ(d) for average-case) with direct implications for experimental design in shadow estimation. Credit is due for the explicit construction, the parameter-free average-case bound, and the concentration result enabling constant sample complexity; these are load-bearing strengths under standard shadow-norm definitions.

minor comments (2)
  1. [Abstract] Abstract, first sentence: the notation 'Θ(d²)' is standard but could briefly note that d is the Hilbert-space dimension to aid readers outside the subfield.
  2. [Abstract] The abstract states proofs of necessity, sufficiency, and concentration; ensure the main text includes explicit theorem statements with equation references for the lower-bound argument and the 2-design average-case bound.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript, the accurate summary of our results on the Θ(d²) necessity and sufficiency for worst-case shadow estimation, and the recommendation for minor revision. The referee correctly highlights the complexity separation and the practical implications of 2-designs for average-case optimality.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The central claims rest on standard external definitions of the shadow norm, 3-design optimality for worst-case performance, and 2-designs for average-case bounds. The necessity lower bound, explicit basis construction for sufficiency, and concentration results for Haar-random states are derived directly from these modeling choices without reducing to fitted parameters, self-definitional loops, or load-bearing self-citations. The separation between Θ(d²) worst-case and Θ(d) average-case bases follows from the stated assumptions and proofs rather than circular renaming or imported uniqueness theorems.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on standard quantum information axioms regarding unitary designs and the definition of shadow norms; no free parameters or invented entities are introduced in the abstract.

axioms (2)
  • domain assumption 3-design protocols achieve optimal worst-case shadow estimation performance
    Invoked to frame the optimality question for the minimal number of bases.
  • domain assumption Shadow norm provides the relevant figure of merit for estimation performance
    Used to define both worst-case and average-case optimality.

pith-pipeline@v0.9.1-grok · 5708 in / 1246 out tokens · 18882 ms · 2026-06-26T17:24:58.580284+00:00 · methodology

0 comments
read the original abstract

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 $\Theta(d^2)$ 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 $\Theta(d^2)$ bases, whereas average-case performance requires only $\Theta(d)$ bases, with broad implications for quantum information theory and near-term experiments.

Figures

Figures reproduced from arXiv: 2606.20003 by Datong Chen, Huangjun Zhu, Zhiyao Yang.

Figure 1
Figure 1. Figure 1: FIG. 1. Construction of the optimal measurement ensemble [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2. Mean squared shadow norm for fidelity estimation [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3. Probability that [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

69 extracted references · 6 canonical work pages · 2 internal anchors

  1. [1]

    Huang, R

    H.-Y. Huang, R. Kueng, and J. Preskill, Predicting many properties of a quantum system from very few measure- ments, Nat. Phys.16, 1050 (2020)

    2020

  2. [2]

    Elben, B

    A. Elben, B. Vermersch, R. van Bijnen, C. Kokail, T. Brydges, C. Maier, M. K. Joshi, R. Blatt, C. F. Roos, and P. Zoller, Cross-platform verification of intermedi- ate scale quantum devices, Phys. Rev. Lett.124, 010504 (2020)

    2020

  3. [3]

    Z. Yang, D. Chen, Z. Li, and H. Zhu, High-precision fidelity estimation with common randomized measure- ments (2025), arXiv:2511.22509 [quant-ph]

    work page arXiv 2025

  4. [4]

    Eisert, D

    J. Eisert, D. Hangleiter, N. Walk, I. Roth, D. Markham, R. Parekh, U. Chabaud, and E. Kashefi, Quantum certifi- cation and benchmarking, Nat. Rev. Phys.2, 382 (2020)

    2020

  5. [5]

    Kliesch and I

    M. Kliesch and I. Roth, Theory of quantum system cer- tification, PRX Quantum2, 010201 (2021)

    2021

  6. [6]

    Brydges, A

    T. Brydges, A. Elben, P. Jurcevic, B. Vermersch, C. Maier, B. P. Lanyon, P. Zoller, R. Blatt, and C. F. Roos, Probing R´ enyi entanglement entropy via random- ized measurements, Science364, 260 (2019)

    2019

  7. [7]

    Elben, R

    A. Elben, R. Kueng, H.-Y. R. Huang, R. van Bij- nen, C. Kokail, M. Dalmonte, P. Calabrese, B. Kraus, J. Preskill, P. Zoller, and B. Vermersch, Mixed-state en- tanglement from local randomized measurements, Phys. Rev. Lett.125, 200501 (2020)

    2020

  8. [8]

    Y. Zhou, P. Zeng, and Z. Liu, Single-copies estimation of entanglement negativity, Phys. Rev. Lett.125, 200502 (2020)

    2020

  9. [9]

    Neven, J

    A. Neven, J. Carrasco, V. Vitale, C. Kokail, A. El- ben, M. Dalmonte, P. Calabrese, P. Zoller, B. Vermer- sch, R. Kueng, and B. Kraus, Symmetry-resolved entan- glement detection using partial transpose moments, npj Quantum Inf.7, 152 (2021)

    2021

  10. [10]

    S. Liu, Q. He, M. Huber, O. G¨ uhne, and G. Vitagliano, Characterizing entanglement dimensionality from ran- domized measurements, PRX Quantum4, 020324 (2023)

    2023

  11. [11]

    C. Yi, X. Li, and H. Zhu, Certifying entanglement di- mensionality byk-reduction moments, PRX Quantum7, 010356 (2026)

    2026

  12. [12]

    Bairey, I

    E. Bairey, I. Arad, and N. H. Lindner, Learning a local Hamiltonian from local measurements, Phys. Rev. Lett. 122, 020504 (2019)

    2019

  13. [13]

    Anshu, S

    A. Anshu, S. Arunachalam, T. Kuwahara, and M. Soleimanifar, Sample-efficient learning of quantum many-body systems, in2020 IEEE 61st Annual Sym- posium on Foundations of Computer Science (FOCS) (2020) pp. 685–691

    2020

  14. [14]

    Hadfield, S

    C. Hadfield, S. Bravyi, R. Raymond, and A. Mezzacapo, Measurements of quantum Hamiltonians with locally- biased classical shadows, Commun. Math. Phys.391, 951 (2022)

    2022

  15. [15]

    Huang, Y

    H.-Y. Huang, Y. Tong, D. Fang, and Y. Su, Learning many-body Hamiltonians with Heisenberg-limited scal- ing, Phys. Rev. Lett.130, 200403 (2023)

    2023

  16. [16]

    G. I. Struchalin, Y. A. Zagorovskii, E. V. Kovlakov, S. S. Straupe, and S. P. Kulik, Experimental estimation of quantum state properties from classical shadows, PRX Quantum2, 010307 (2021)

    2021

  17. [17]

    Zhang, J

    T. Zhang, J. Sun, X.-X. Fang, X.-M. Zhang, X. Yuan, and H. Lu, Experimental quantum state measurement with classical shadows, Phys. Rev. Lett.127, 200501 (2021)

    2021

  18. [18]

    Huang, M

    H.-Y. Huang, M. Broughton, J. Cotler, S. Chen, J. Li, M. Mohseni, H. Neven, R. Babbush, R. Kueng, J. Preskill, and J. R. McClean, Quantum advantage in learning from experiments, Science376, 1182 (2022)

    2022

  19. [19]

    H.-Y. Hu, A. Gu, S. Majumder, H. Ren, Y. Zhang, D. S. Wang, Y.-Z. You, Z. Minev, S. F. Yelin, and A. Seif, Demonstration of robust and efficient quantum property learning with shallow shadows, Nat. Commun.16, 2943 (2025)

    2025

  20. [20]

    Stricker, M

    R. Stricker, M. Meth, L. Postler, C. Edmunds, C. Ferrie, R. Blatt, P. Schindler, T. Monz, R. Kueng, and M. Ring- bauer, Experimental single-setting quantum state tomog- raphy, PRX Quantum3, 040310 (2022)

    2022

  21. [21]

    Innocenti, S

    L. Innocenti, S. Lorenzo, I. Palmisano, F. Albarelli, A. Ferraro, M. Paternostro, and G. M. Palma, Shadow tomography on general measurement frames, PRX Quan- tum4, 040328 (2023)

    2023

  22. [22]

    H. C. Nguyen, J. L. B¨ onsel, J. Steinberg, and O. G¨ uhne, Optimizing shadow tomography with generalized mea- surements, Phys. Rev. Lett.129, 220502 (2022)

    2022

  23. [23]

    Zhu, Multiqubit Clifford groups are unitary 3-designs, Phys

    H. Zhu, Multiqubit Clifford groups are unitary 3-designs, Phys. Rev. A96, 062336 (2017)

    2017

  24. [24]

    Webb, The Clifford group forms a unitary 3-design, Quantum Inf

    Z. Webb, The Clifford group forms a unitary 3-design, Quantum Inf. Comput.16, 1379 (2016)

    2016

  25. [25]

    Durt, B.-G

    T. Durt, B.-G. Englert, I. Bengtsson, and K. ˙Zyczkowski, 6 On mutually unbiased bases, Int. J. Quantum Inf.8, 535 (2010)

    2010

  26. [26]

    I. D. Ivanovic, Geometrical description of quantal state determination, J. Phys. A14, 3241 (1981)

    1981

  27. [27]

    W. K. Wootters and B. D. Fields, Optimal state- determination by mutually unbiased measurements, An- nals of Physics191, 363 (1989)

    1989

  28. [28]

    Gonzalez Avella, J

    V. Gonzalez Avella, J. Czartowski, D. Goyeneche, and K. ˙Zyczkowski, Cyclic measurements and simplified quantum state tomography, Quantum9, 1763 (2025)

    2025

  29. [29]

    Elben, S

    A. Elben, S. T. Flammia, H.-Y. Huang, R. Kueng, J. Preskill, B. Vermersch, and P. Zoller, The randomized measurement toolbox, Nat. Rev. Phys.5, 9 (2023)

    2023

  30. [30]

    H.-Y. Hu, S. Choi, and Y.-Z. You, Classical shadow tomography with locally scrambled quantum dynamics, Phys. Rev. Res.5, 023027 (2023)

    2023

  31. [31]

    K. Bu, D. E. Koh, R. J. Garcia, and A. Jaffe, Classi- cal shadows with Pauli-invariant unitary ensembles, npj Quantum Inf.10, 6 (2024)

    2024

  32. [32]

    Hu and Y.-Z

    H.-Y. Hu and Y.-Z. You, Hamiltonian-driven shadow to- mography of quantum states, Phys. Rev. Res.4, 013054 (2022)

    2022

  33. [33]

    Z. Liu, Z. Hao, and H.-Y. Hu, Predicting arbitrary state properties from single Hamiltonian quench dynamics, Phys. Rev. Res.6, 043118 (2024)

    2024

  34. [34]

    Zhang, Q

    Q. Zhang, Q. Liu, and Y. Zhou, Minimal-Clifford shadow estimation by mutually unbiased bases, Phys. Rev. Appl. 21, 064001 (2024)

    2024

  35. [35]

    Wang and W

    Y. Wang and W. Cui, Classical shadow tomography with mutually unbiased bases, Phys. Rev. A109, 062406 (2024)

    2024

  36. [36]

    G. Park, Y. S. Teo, and H. Jeong, Resource-efficient shadow tomography using equatorial stabilizer measure- ments, Phys. Rev. Res.7, 033097 (2025)

    2025

  37. [37]

    Y. Wu, C. Wang, J. Yao, H. Zhai, Y.-Z. You, and P. Zhang, Contractive unitary and classical shadow to- mography, npj Quantum Inf.12, 86 (2026)

    2026

  38. [38]

    Ippoliti, Classical shadows based on locally-entangled measurements, Quantum8, 1293 (2024)

    M. Ippoliti, Classical shadows based on locally-entangled measurements, Quantum8, 1293 (2024)

    2024

  39. [39]

    M. West, F. Sauvage, A. Sen, R. Forestano, D. Wierichs, N. Killoran, D. Grinko, M. Cerezo, and M. Larocca, Classical shadows with arbitrary group representations (2026), arXiv:2604.01429 [quant-ph]

    work page arXiv 2026

  40. [40]

    Cleve, D

    R. Cleve, D. Leung, L. Liu, and C. Wang, Near-linear constructions of exact unitary 2-designs, Quantum Inf. Comput.16, 721 (2016)

    2016

  41. [41]

    Bertoni, J

    C. Bertoni, J. Haferkamp, M. Hinsche, M. Ioannou, J. Eisert, and H. Pashayan, Shallow shadows: Expecta- tion estimation using low-depth random Clifford circuits, Phys. Rev. Lett.133, 020602 (2024)

    2024

  42. [42]

    Schuster, J

    T. Schuster, J. Haferkamp, and H.-Y. Huang, Random unitaries in extremely low depth, Science389, 92 (2025)

    2025

  43. [43]

    C. A. Fuchs, M. C. Hoang, and B. C. Stacey, The SIC question: History and state of play, Axioms6, 21 (2017)

    2017

  44. [44]

    Zauner, Quantum designs: Foundations of a non- commutative design theory, Int

    G. Zauner, Quantum designs: Foundations of a non- commutative design theory, Int. J. Quantum Inf.9, 445 (2011)

    2011

  45. [45]

    J. M. Renes, R. Blume-Kohout, A. J. Scott, and C. M. Caves, Symmetric informationally complete quantum measurements, J. Math. Phys.45, 2171 (2004)

    2004

  46. [46]

    A. J. Scott, Tight informationally complete quantum measurements, J. Phys. A39, 13507 (2006)

    2006

  47. [47]

    Ambainis and J

    A. Ambainis and J. Emerson, Quantumt-designs:t-wise independence in the quantum world, inTwenty-Second Annual IEEE Conference on Computational Complexity (CCC’07)(2007) pp. 129–140

    2007

  48. [48]

    Qubit stabilizer states are complex projective 3-designs

    R. Kueng and D. Gross, Qubit stabilizer states are complex projective 3-designs (2015), arXiv:1510.02767 [quant-ph]

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  49. [49]

    See Supplemental Material for proofs and additional re- sults

  50. [50]

    S. G. Hoggar,t-designs in projective spaces, Eur. J. Comb.3, 233 (1982)

    1982

  51. [51]

    H. Zhu, R. Kueng, M. Grassl, and D. Gross, The Clifford group fails gracefully to be a unitary 4-design (2016), arXiv:1609.08172 [quant-ph]

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  52. [52]

    J. T. Iosue, T. C. Mooney, A. Ehrenberg, and A. V. Gor- shkov, Projective toric designs, quantum state designs, and mutually unbiased bases, Quantum8, 1546 (2024)

    2024

  53. [53]

    Chen and H

    D. Chen and H. Zhu, Nonstabilizerness enhances thrifty shadow estimation (2024), arXiv:2410.23977 [quant-ph]

    work page arXiv 2024

  54. [54]

    Jasper and D

    J. Jasper and D. G. Mixon, Nearly tight weighted 2- designs in complex projective spaces of every dimension, in2025 International Conference on Sampling Theory and Applications (SampTA)(2025) pp. 1–5

    2025

  55. [55]

    Roy and A

    A. Roy and A. Scott, Weighted complex projective 2- designs from bases: optimal state determination by orthogonal measurements, J. Math. Phys.48, 072110 (2007)

    2007

  56. [56]

    McConnell and D

    G. McConnell and D. Gross, Efficient 2-designs from bases exist, Quantum Inf. Comput.8, 0734 (2008)

    2008

  57. [57]

    A. J. Scott and M. Grassl, Symmetric informationally complete positive-operator-valued measures: A new com- puter study, J. Math. Phys.51, 042203 (2010)

    2010

  58. [58]

    C. Mao, C. Yi, and H. Zhu, Qudit shadow estimation based on the Clifford group and the power of a single magic gate, Phys. Rev. Lett.134, 160801 (2025)

    2025

  59. [59]

    H. Zhu, C. Mao, and C. Yi, Third moments of qudit Clif- ford orbits and 3-designs based on magic orbits (2024), arXiv:2410.13575 [quant-ph]

    work page arXiv 2024

  60. [60]

    G. H. Hardy and E. M. Wright,An Introduction to the Theory of Numbers, 6th ed. (Oxford University Press, Oxford, 2008)

    2008

  61. [61]

    D. K. Mark, F. Surace, A. Elben, A. L. Shaw, J. Choi, G. Refael, M. Endres, and S. Choi, Maximum entropy principle in deep thermalization and in hilbert-space er- godicity, Phys. Rev. X14, 041051 (2024)

    2024

  62. [62]

    Leone, S

    L. Leone, S. F. E. Oliviero, and A. Hamma, Stabilizer R´ enyi entropy, Phys. Rev. Lett.128, 050402 (2022). 7 End Matter Appendix A: Reconstruction map for the combined phase-design ensembleE N—ConsiderN≥2 MUBs B1,B 2, . . . ,BN and the ensembleE N used in Theorem 2. Any operatorO∈ L(H) can be decomposed as O= tr(O)1 d +O ⊥ + NX j=1 OBj ,(15) whereO Bj den...

    2022

  63. [63]

    (S84), this equation means ∥O∥2 EN ≤ 3N+ 1 N d2 · N 2d2 (N−1) 2 ∥O∥2 2 = N(3N+ 1) (N−1) 2 ∥O∥2 2,(S87) which completes the proof of Theorem 2

    Together with Eq. (S84), this equation means ∥O∥2 EN ≤ 3N+ 1 N d2 · N 2d2 (N−1) 2 ∥O∥2 2 = N(3N+ 1) (N−1) 2 ∥O∥2 2,(S87) which completes the proof of Theorem 2. 12 TABLE S1. Dimensions of the Specht moduleS λ and Weyl moduleW λ. λ d λ Dλ

  64. [64]

    FOURTH MOMENTS OF HAAR-RANDOM OBSERVABLES AND CLIFFORD ORBITS A

    1 d(d+ 1)(d+ 2)(d+ 3) 24 [1,1,1,1] 1 d(d−1)(d−2)(d−3) 24 [2,2] 2 d2(d2 −1) 12 [2,1,1] 3 d(d−2)(d 2 −1) 8 [3,1] 3 d(d+ 2)(d 2 −1) 8 S4. FOURTH MOMENTS OF HAAR-RANDOM OBSERVABLES AND CLIFFORD ORBITS A. 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 ...

  65. [65]

    = tr(P+) = (d+ 1)(d+ 2) 6 , D −

  66. [66]

    = tr(P−) = (d2 −1)(d+ 2)(d+ 4) 24 .(S97) By construction, we have tr P+ψ⊗4 = tr Pnψ⊗4 = 2−M2(ψ) d ,tr P−ψ⊗4 = 1− 2−M2(ψ) d ∀ψ∈ P(H).(S98) 14 Lemma S11.Supposeψ, ϕ∈ P(H). Then E U∼Cl(n) U ψU† ⊗4 = 2−M2(ψ) d D+ [4] P+ + 1 D− [4] 1− 2−M2(ψ) d P−,(S99) E U∼Cl(n) tr ϕ U ψU† 4 = 2−M2(ψ)−M2(ϕ) d2 D+ [4] + 1 D− [4] 1− 2−M2(ϕ) d 1− 2−M2(ψ) d ≤ 5(d+ 3) 4(d+ 4)D [4]...

  67. [67]

    Proof of Lemma S11.Equation (S99) follows from Schur’s lemma and Eq

    are given in Eq.(S97), andD [4] is given in Table S1. Proof of Lemma S11.Equation (S99) follows from Schur’s lemma and Eq. (S98); it was essentially proved in Ref. [51], though without the concept of stabilizer 2-R´ enyi entropy. The equality in Eq. (S100) is a direct corollary of Eqs. (S98) and (S99). The first inequality in Eq. (S100) follows from Eq. (...

  68. [68]

    This completes the proof of Proposition S4. B. Proof of Theorem 3 Proof of Theorem 3.By virtue of Proposition S4 and the inequalities in Eq. (S112), we deduce that ∥Ξ(O,U)∥ 2 E ≤ d+ 1 d + s 24 d − 26 d2 ¯Φ3(E) + 4− gd d ! ∥O∥2 2 ≤ d+ 1 d + r 24 d ¯Φ3(E) + 4− 26 d2 − gd d ∥O∥2 2 ≤ d+ 1 d + r 24 d ¯Φ3(E) + 4− 30 d ∥O∥2 2 ≤ 1 + r 24 d [¯Φ3(E)−1] + 4 ∥O∥2 2 ≤...

  69. [69]

    (S119) Here the second inequality holds because ¯Φ3(E)≥1, the third holds because (26/d) +g d ≥30 by Eq. (S112), the last holds because ¯Φ3(E)≤(d+ 2)(d 2 + 2d−1)/(6d 2) by Proposition 1, which implies that 24[ ¯Φ3(E)−1]/d≤4, and the fourth inequality follows from the concavity of the square root: r 24 d ¯Φ3(E) + 4− 30 d ≤ r 24 d [¯Φ3(E)−1] + 4− 3 d q 24 d...

    2000