[GEB23] Elies Gil-Fuster, Jens Eisert, and Carlos Bravo-Prieto. *Understanding quantum machine learning also requires rethinking generalization*, 2023. arXiv: 2306.13461 [quant-ph] (cited on pages 3, 42).

[GLM06] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. “Quantum metrology”. *Physical review letters*, 96(1):010401, 2006 (cited on pages 4, 39).

[Gol11] Oded Goldreich. “On the average-case complexity of property testing”, *Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation*, pages 124–135. Springer, 2011 (cited on page 44).

[GK10] Mădălin Guță and Wojciech Kotłowski. “Quantum learning: asymptotically optimal classification of qubit states”. *New Journal of Physics*, 12(12):123032, 2010 (cited on pages 3, 11, 20).

[GVD23] Casper Gyurik, Dyon Vreumingen van, and Vedran Dunjko. “Structural risk minimization for quantum linear classifiers”. *Quantum*, 7:893, 2023 (cited on page 42).

[HHJ$^{+}$16] Jeongwan Haah, Aram W Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu. “Sample-optimal tomography of quantum states”. *Proceedings of the forty-eighth annual ACM symposium on Theory of Computing*, pages 913–925, 2016 (cited on page 3).

[HHJ$^{+}$17] Jeongwan Haah, Aram W Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu. “Sample-optimal tomography of quantum states”. *IEEE Transactions on Information Theory*, 63(9):5628–5641, 2017 (cited on page 10).

[HKO$^{+}$23] Jeongwan Haah, Robin Kothari, Ryan O’Donnell, and Ewin Tang. “Query-optimal estimation of unitary channels in diamond distance”. arXiv preprint arXiv:2302.14066, 2023 (cited on page 3).

[HNK$^{+}$20] Mahdi Haghifam, Jeffrey Negrea, Ashish Khisti, Daniel M Roy, and Gintare Karolina Dziugaite. “Sharpened generalization bounds based on conditional mutual information and an application to noisy, iterative algorithms”. H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, *Advances in Neural Information Processing Systems*, volume 33, pages 9925–9935. Curran Associates, Inc., 2020 (cited on page 12).

[HRS$^{+}$21] Hrayr Harutyunyan, Maxim Raginsky, Greg Ver Steeg, and Aram Galstyan. “Information-theoretic generalization bounds for black-box learning algorithms”. A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, *Advances in Neural Information Processing Systems*, 2021 (cited on page 12).

[HK23] Tobias Haug and M. S. Kim. *Generalization with quantum geometry for learning unitaries*, 2023. arXiv: 2303.13462 [quant-ph] (cited on page 42).

[HJS$^{+}$96] Paul Hausladen, Richard Jozsa, Benjamin Schumacher, Michael Westmoreland, and William K Wootters. “Classical information capacity of a quantum channel”. *Physical Review A*, 54(3):1869, 1996 (cited on page 11).

[HW94] Paul Hausladen and William K Wootters. “A ‘pretty good’measurement for distinguishing quantum states”. *Journal of Modern Optics*, 41(12):2385–2390, 1994 (cited on page 11).

[HCT$^{+}$19] Vojtěch Havlíček, Antonio D Córcoles, Kristan Temme, Aram W Harrow, Abhinav Kandala, Jerry M Chow, and Jay M Gambetta. “Supervised learning with quantum-enhanced feature spaces”. *Nature*, 567(7747):209–212, 2019 (cited on page 3).

[HZ11] Teiko Heinosaari and Mário Ziman. *The Mathematical Language of Quantum Theory*. Cambridge University Press, 2011 (cited on page 20).

[HD21] Fredrik Hellström and Giuseppe Durisi. “Fast-rate loss bounds via conditional information measures with applications to neural networks”. *2021 IEEE International Symposium on Information Theory (ISIT)*, pages 952–957, Melbourne, Australia. IEEE Press, 2021 (cited on page 12).
[HD22] Fredrik Hellström and Giuseppe Durisi. “A new family of generalization bounds using samplewise evaluated cmi”. S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, *Advances in Neural Information Processing Systems*, volume 35, pages 10108–10121. Curran Associates, Inc., 2022 (cited on page 12).

[HDG$^{+23}$] Fredrik Hellström, Giuseppe Durisi, Benjamin Guedj, and Maxim Raginsky. *Generalization bounds: perspectives from information theory and pac-bayes*, 2023. arXiv: 2309.04381 [cs.LG] (cited on pages 3, 12, 45).

[Hel69] Carl W Helstrom. “Quantum detection and estimation theory”. *Journal of Statistical Physics*, 1:231–252, 1969 (cited on pages 3, 10).

[HRF23] Christoph Hirche, Cambyse Rouzé, and Daniel Stilck França. “Quantum differential privacy: an information theory perspective”. *IEEE Transactions on Information Theory*, 2023 (cited on pages 32, 45, 46).

[Hoe63] Wassily Hoeffding. “Probability inequalities for sums of bounded random variables”. *Journal of the American Statistical Association*, 58(301):13–30, 1963 (cited on pages 28, 29, 34).

[Hol73] A. S. Holevo. “Statistical decision theory for quantum systems”. *J. Multivariate Anal.*, 3:337–394, 1973 (cited on page 10).

[Hol74] Alexander Semenovich Holevo. “Remarks on optimal quantum measurements”. *Problemy Peredachi Informatsii*, 10(4):51–55, 1974 (cited on pages 3, 10).

[HBC$^{+22a}$] Hsin-Yuan Huang, Michael Broughton, Jordan Cotler, Sitan Chen, Jerry Li, Masoud Mohseni, Hartmut Neven, Ryan Babbush, Richard Kueng, John Preskill, et al. “Quantum advantage in learning from experiments”. *Science*, 376(6598):1182–1186, 2022 (cited on page 3).

[HBC$^{+22b}$] Hsin-Yuan Huang, Michael Broughton, Jordan Cotler, Sitan Chen, Jerry Li, Masoud Mohseni, Hartmut Neven, Ryan Babbush, Richard Kueng, John Preskill, and Jarrod R. McClean. “Quantum advantage in learning from experiments”. *Science*, 376(6598):1182–1186, 2022 (cited on page 11).

[HCP23] Hsin-Yuan Huang, Sitan Chen, and John Preskill. *Learning to predict arbitrary quantum processes*, 2023. arXiv: 2210.14894 [quant-ph] (cited on page 20).

[HKP20] Hsin-Yuan Huang, Richard Kueng, and John Preskill. “Predicting many properties of a quantum system from very few measurements”. *Nature Physics*, 16(10):1050–1057, 2020 (cited on pages 3, 11).

[HKP21] Hsin-Yuan Huang, Richard Kueng, and John Preskill. “Information-theoretic bounds on quantum advantage in machine learning”. *Physical Review Letters*, 126(19):190505, 2021 (cited on pages 3, 11).

[HTF$^{+23}$] Hsin-Yuan Huang, Yu Tong, Di Fang, and Yuan Su. “Learning many-body hamiltonians with heisenberg-limited scaling”. *Physical Review Letters*, 130(20):200403, 2023 (cited on page 11).

[JHW17] Jiantao Jiao, Yanjun Han, and Tsachy Weissman. “Dependence measures bounding the exploration bias for general measurements”. *2017 IEEE International Symposium on Information Theory (ISIT)*, pages 1475–1479. IEEE, 2017 (cited on page 26).

[KS94] Michael J. Kearns and Robert E. Schapire. “Efficient distribution-free learning of probabilistic concepts”. *Journal of Computer and System Sciences*, 48(3):464–497, 1994 (cited on pages 3, 10, 35).

[KS20] Tomotaka Kuwahara and Keiji Saito. “Gaussian concentration bound and ensemble equivalence in generic quantum many-body systems including long-range interactions”. *Annals of Physics*, 421:168278, 2020 (cited on page 27).

[Lie73] Elliott H. Lieb. “Convex Trace Functions and the Wigner-Yanase-Dyson Conjecture”. en. *Les rencontres physiciens-mathématiciens de Strasbourg -RCP25*, 19, 1973. talk:4 (cited on page 57).
[LW86] Nick Littlestone and Manfred Warmuth. *Relating data compression and learnability*. 1986. URL: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.37.7589&rep=rep1&type=pdf. Technical report, University of California Santa Cruz (cited on page 3).

[LN22] Gabor Lugosi and Gergely Neu. "Generalization bounds via convex analysis". Po-Ling Loh and Maxim Raginsky, editors, *Proceedings of Thirty Fifth Conference on Learning Theory*, volume 178 of *Proceedings of Machine Learning Research*, pages 3524–3546. PMLR, 2022 (cited on page 12).

[LN23] Gábor Lugosi and Gergely Neu. *Online-to-pac conversions: generalization bounds via regret analysis*. Version 1. May 31, 2023. arXiv: 2305.19674 [stat.ML] (cited on page 12).

[McA99] David A. McAllester. "Some pac-bayesian theorems". *Machine Learning*, 37(3):355–363, 1999 (cited on page 3).

[McD89] Colin McDiarmid. "On the method of bounded differences", *Surveys in combinatorics, 1989 (Norwich, 1989)*. Volume 141, London Math. Soc. Lecture Note Ser. Pages 148–188. Cambridge Univ. Press, Cambridge, 1989 (cited on pages 16, 31).

[MV03] Shahar Mendelson and Roman Vershynin. "Entropy and the combinatorial dimension". *Inventiones mathematicae*, 152(1):37–55, 2003 (cited on page 35).

[MSW17] Alex Monras, Gael Sentís, and Peter Wittek. "Inductive supervised quantum learning". *Physical review letters*, 118(19):190503, 2017 (cited on pages 47, 48).

[MW16] Ashley Montanaro and Ronald de Wolf. *A Survey of Quantum Property Testing*, number 7 in Graduate Surveys. Theory of Computing Library, 2016, pages 1–81 (cited on page 43).

[NHD$^{+}$19] Jeffrey Negrea, Mahdi Haghifam, Gintare Karolina Dziugaite, Ashish Khisti, and Daniel M Roy. "Information-theoretic generalization bounds for sgld via data-dependent estimates". H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, *Advances in Neural Information Processing Systems*, volume 32. Curran Associates, Inc., 2019 (cited on page 39).

[NC10] Michael A. Nielsen and Isaac L. Chuang. *Quantum Computation and Quantum Information*. Cambridge University Press, 2010 (cited on page 16).

[NGW23] Theshani Nuradha, Ziv Goldfeld, and Mark M Wilde. "Quantum pufferfish privacy: a flexible privacy framework for quantum systems". arXiv preprint arXiv:2306.13054, 2023 (cited on page 45).

[OW16] Ryan O'Donnell and John Wright. "Efficient quantum tomography", STOC '16, pages 899–912, Cambridge, MA, USA. Association for Computing Machinery, 2016 (cited on pages 3, 10).

[Pet88] Dénes Petz. "A variational expression for the relative entropy". *Communications in Mathematical Physics*, 114(2):345–349, 1988 (cited on pages 15, 23).

[Pol84] David Pollard. *Convergence of stochastic processes*. Springer, 1984 (cited on page 3).

[Pop21] Claudiu Marius Popescu. "Learning bounds for quantum circuits in the agnostic setting". *Quantum Information Processing*, 20(9):1–24, 2021 (cited on page 42).

[Rag19] Maxim Raginsky. *Information, concentration, and learning*, 2019. 2019 IEEE North American School of Information Theory (NASIT 2019) (cited on pages 24, 26, 39).

[Ros22] Matteo Rosati. "A learning theory for quantum photonic processors and beyond". *arXiv preprint arXiv:2209.03075*, 2022 (cited on page 11).

[RZ19] Daniel Russo and James Zou. "How much does your data exploration overfit? controlling bias via information usage". *IEEE Transactions on Information Theory*, 66(1):302–323, 2019. eprint: arXiv:1511.05219 (cited on pages 3, 12).

[SMM$^{+}$19] Gael Sentís, Alex Monràs, Ramon Muñoz-Tapia, John Calsamiglia, and Emilio Bagan. "Unsupervised classification of quantum data". *Phys. Rev. X*, 9:041029, 4, 2019 (cited on pages 3, 11).
[SSS$^{+10}$] Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. "Learnability, stability and uniform convergence". *Journal of Machine Learning Research*, 11(90):2635–2670, 2010 (cited on pages 16, 32).

[SZ20] Thomas Steinke and Lydia Zakynthinou. "Reasoning about generalization via conditional mutual information". *Conference on Learning Theory*, pages 3437–3452. PMLR, 2020 (cited on page 12).

[SBT17] David Sutter, Mario Berta, and Marco Tomamichel. "Multivariate trace inequalities". *Communications in Mathematical Physics*, 352:37–58, 2017 (cited on page 57).

[VC71] Vladimir N. Vapnik and Alexei Ya. Chervonenkis. "On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities". *Theory of Probability & Its Applications*, 16(2):264–280, 1971 (cited on pages 3, 45).

[Ver18] Roman Vershynin. *High-dimensional probability: An introduction with applications in data science*. Cambridge University Press, 2018 (cited on pages 28, 34, 45, 62).

[Vid03] Mathukumalli Vidyasagar. *A Theory of Learning and Generalization: With Applications to Neural Networks and Control Systems*. Springer, 2003 (cited on page 35).

[WZC$^{+23}$] Qisheng Wang, Zhicheng Zhang, Kean Chen, Ji Guan, Wang Fang, Junyi Liu, and Mingsheng Ying. "Quantum algorithm for fidelity estimation". *IEEE Transactions on Information Theory*, 69(1):273–282, January 2023 (cited on page 45).

[Wil13] Mark M Wilde. *Quantum information theory*. Cambridge University Press, 2013 (cited on page 16).

[XR17] Aolin Xu and Maxim Raginsky. "Information-theoretic analysis of generalization capability of learning algorithms". I. Guyon, U. Von Luxburg, S. Bengio, H. Walach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, *Advances in Neural Information Processing Systems*, volume 30. Curran Associates, Inc., 2017 (cited on pages 3, 6, 10, 12–14, 20, 22, 24, 27, 30, 33, 36–39).

[YKL75] Horace Yuen, Robert Kennedy, and Melvin Lax. "Optimum testing of multiple hypotheses in quantum detection theory". *IEEE transactions on information theory*, 21(2):125–134, 1975 (cited on pages 3, 10).

[ZA23] Behnoosh Zamanlooy and Shahab Asoodeh. "Strong data processing inequalities for locally differentially private mechanisms". *2023 IEEE International Symposium on Information Theory (ISIT)*, pages 1794–1799. IEEE, 2023 (cited on page 45).

[ZBH$^{+17}$] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. "Understanding deep learning requires rethinking generalization". *5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings*. OpenReview.net, 2017 (cited on pages 3, 42).

[ZBH$^{+21}$] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. "Understanding deep learning (still) requires rethinking generalization". *Commun. ACM*, 64(3):107–115, 2021 (cited on pages 3, 42).

[ZLK$^{+23}$] Haimeng Zhao, Laura Lewis, Ishaan Kannan, Yihui Quek, Hsin-Yuan Huang, and Matthias C. Caro. "Learning quantum states and unitaries of bounded gate complexity". *arXiv:2310.19882*, 2023 (cited on page 3).

[ZY17] Li Zhou and Mingsheng Ying. "Differential privacy in quantum computation". *2017 IEEE 30th Computer Security Foundations Symposium (CSF)*, pages 249–262. IEEE, 2017 (cited on page 45).
A. Auxiliary Results and Proofs

**Lemma A.1.** Let $H$ be a Hermitian $m$-qudit observable. Let $\rho = \bigotimes_{i=1}^m \rho_i$ be an $m$-fold tensor product of qudit states. Then, for any $\lambda \in \mathbb{R}$,

$$ \mathrm{Tr}[e^{\log(\rho)+\lambda H}] \le e^{\frac{\lambda^2 m \|H\|_{\mathrm{Lip}}^2}{2}}. \qquad (A.1) $$

*Proof.* For the proof, we use the following pieces of notation: $\rho_{1...m-1} = \bigotimes_{i=1}^{m-1} \rho_i$ and $\mathrm{Tr}_{1...m-1}$ denotes the partial trace over all but the $m$th subsystem. With this notation (and suppressing identity tensor factors), we can rewrite our expression of interest as follows:

$$ \mathrm{Tr}[e^{\log(\rho)+\lambda H}] = \mathrm{Tr}[\exp(\log(\rho_{1...m-1}) + \log(\rho_m) + \lambda H - \mathrm{Tr}_m[\rho_m \cdot \lambda H] + \mathrm{Tr}_m[\rho_m \cdot \lambda H])] \quad (A.2) $$

$$ \le \int_0^\infty \mathrm{Tr} \left[ e^{\log(\rho_{1...m-1})+\mathrm{Tr}_m[\rho_m \cdot \lambda H]} (\rho_m^{-1} + t1_d)^{-1} e^{\lambda H - \mathrm{Tr}_m[\rho_m \cdot \lambda H]} (\rho_m^{-1} + t1_d)^{-1} \right] dt \quad (A.3) $$

$$ = \mathrm{Tr}_{1...m-1} \left[ e^{\log(\rho_{1...m-1})+\mathrm{Tr}_m[\rho_m \cdot \lambda H]} \mathrm{Tr}_m \left[ e^{\lambda H - \mathrm{Tr}_m[\rho_m \cdot \lambda H]} \int_0^\infty (\rho_m^{-1} + t1_d)^{-2} dt \right] \right] \quad (A.4) $$

$$ = \mathrm{Tr}_{1...m-1} \left[ e^{\log(\rho_{1...m-1})+\mathrm{Tr}_m[\rho_m \cdot \lambda H]} \mathrm{Tr}_m \left[ \rho_m e^{\lambda H - \mathrm{Tr}_m[\rho_m \cdot \lambda H]} \right] \right], \quad (A.5) $$

where the inequality uses Lieb's triple matrix inequality [Lie73] (see also [SBT17]). Here, by a continuity and density argument, we w.l.o.g. assume that $\rho_i$ is invertible for every $i$, so that $\rho_i^{-1}$ is well-defined. Next, as we prove in Lemma A.2, because the map $H \mapsto \mathrm{Tr}_m[\rho_m \cdot \lambda H] = (\mathrm{id}_{1...m} \otimes \mathrm{Tr}_m[\rho_m(\cdot)])(H)$ is a 1-local completely positive and unital (CPU) map, we have

$$ \|\lambda H - \mathrm{Tr}_m[\rho_m \cdot \lambda H]\|_{\infty} \le \|\lambda H\|_{\mathrm{Lip}} = |\lambda| \|H\|_{\mathrm{Lip}}. \quad (A.6) $$

Now, we observe that $e^x \le \sinh(x) + e^{x^2/2} \le \frac{\sinh(y)}{y}x + e^{y^2/2}$ holds for $|x| \le y$. Here, the first inequality can be seen from the series expansions of the exponential and the hyperbolic sine, and the second inequality follows because $z \mapsto \frac{\sinh(z)}{z}$ is non-decreasing for $z \ge 0$ and symmetric around the y-axis. Therefore,

$$ e^{\lambda H - \mathrm{Tr}_m[\rho_m \cdot \lambda H]} \le \frac{\sinh(|\lambda| \|H\|_{\mathrm{Lip}})}{|\lambda| \|H\|_{\mathrm{Lip}}} (\lambda H - \mathrm{Tr}_m[\rho_m \cdot \lambda H]) + e^{\frac{(|\lambda| \|H\|_{\mathrm{Lip}})^2}{2}}. \quad (A.7) $$

Plugging this back into our bound above, we get

$$ \mathrm{Tr}[e^{\log(\rho)+\lambda H}] \le e^{\frac{(|\lambda|\|H\|_{\mathrm{Lip}})^2}{2}} \mathrm{Tr}_{1...m-1} \left[ e^{\log(\rho_{1...m-1})+\mathrm{Tr}_m[\rho_m \cdot \lambda H]} \right]. \quad (A.8) $$

Iterating this reasoning and arguing inductively, we obtain

$$ \mathrm{Tr}[e^{\log(\rho)+\lambda H}] \le e^{\frac{m(|\lambda|\|H\|_{\mathrm{Lip}})^2}{2}} \le e^{\frac{\lambda^2 m \|H\|_{\mathrm{Lip}}^2}{2}}, \quad (A.9) $$

as claimed. Here, we also used that the Lipschitz constant remains bounded by that of $H$ throughout the iteration. This can be seen as follows: The map $H \mapsto \mathrm{Tr}_m[\rho_m \cdot \lambda H] =$
(id$_{1...m} \otimes \text{Tr}_m[\rho_m(\cdot)])(H)$ is a 1-local CPU map and any tensor product $\Phi = \bigotimes_{i=1}^m \Phi_i$ of 1-local CPU maps is contractive w.r.t. $\|\cdot\|_{\text{Lip}}$ because, by [DMT$^{+}$21, Proposition 8],

$$ \|\Phi(H)\|_{\text{Lip}} = 2 \max_{1 \le i \le m} \min_{H^{(i)} = H^{(i)\dagger} \in \mathcal{B}((\mathbb{C}^d)^{\otimes (m-1)})} \left\| \Phi(H) - 1_i \otimes H^{(i)} \right\| \quad (A.10) $$

$$ \le 2 \max_{1 \le i \le m} \min_{H^{(i)} = H^{(i)\dagger} \in \mathcal{B}((\mathbb{C}^d)^{\otimes (m-1)})} \left\| \Phi(H) - 1_i \otimes \left( \bigotimes_{j \ne i} \Phi_j \right) (H^{(i)}) \right\| \quad (A.11) $$

$$ = 2 \max_{1 \le i \le m} \min_{H^{(i)} = H^{(i)\dagger} \in \mathcal{B}((\mathbb{C}^d)^{\otimes (m-1)})} \left\| \Phi(H) - \Phi_i(1_i) \otimes \left( \bigotimes_{j \ne i} \Phi_j \right) (H^{(i)}) \right\| \quad (A.12) $$

$$ = 2 \max_{1 \le i \le m} \min_{H^{(i)} = H^{(i)\dagger} \in \mathcal{B}((\mathbb{C}^d)^{\otimes (m-1)})} \left\| \Phi(H - 1_i \otimes H^{(i)}) \right\| \quad (A.13) $$

$$ \le 2 \max_{1 \le i \le m} \min_{H^{(i)} = H^{(i)\dagger} \in \mathcal{B}((\mathbb{C}^d)^{\otimes (m-1)})} \left\| H - 1_i \otimes H^{(i)} \right\| \quad (A.14) $$

$$ = \|H\|_{\text{Lip}}, \quad (A.15) $$

where we used contractivity of the CPU map $\Phi$ w.r.t. the operator norm. $\square$

**Lemma A.2.** Let $H$ be a Hermitian $m$-qudit observable. For some $1 \le i \le m$, let $\Phi_i$ be a single-qudit CPU map. Then,

$$ \|H - \Phi_i(H)\|_{\infty} \le \|H\|_{\text{Lip}}. \quad (A.16) $$

*Proof.* The proof is similar to the proof of the upper bound in [DMT$^{+}$21, Proposition 15]. Take $\rho$ to be an $m$-qudit state such that

$$ \|H - \Phi_i(H)\|_{\infty} = |\text{Tr}[(H - \Phi_i(H))\rho]| = |\text{Tr}[H(\rho - \Phi_i^*(\rho))]|, \quad (A.17) $$

which exists by duality of operator and trace norms. Using next the duality of Wasserstein-1 and Lipschitz norms, this gives the bound

$$ \|H - \Phi_i(H)\|_{\infty} = |\text{Tr}[H(\rho - \Phi_i^*(\rho))]| \le \|H\|_{\text{Lip}} \|\rho - \Phi_i^*(\rho)\|_{W_1}. \quad (A.18) $$

Now, as $\Phi_i^*$ is a 1-local CPTP map, [DMT$^{+}$21, Proposition 2] implies $\|\rho - \Phi_i^*(\rho)\|_{W_1} = \frac{1}{2}\|\rho - \Phi_i^*(\rho)\|_1 \le 1$. Combining our inequalities, we have shown

$$ \|H - \Phi_i(H)\|_{\infty} \le \|H\|_{\text{Lip}}, \quad (A.19) $$

as claimed. $\square$

*Proof of Corollary 4.21.* First, note that the sub-gaussianity assumption on the $L_i(z_i, w)$ implies

$$ \log \text{Tr} \left[ (\rho_{\text{test}}(s) \otimes \sigma_{\text{hyp}}^{A}(s, w)) \cdot e^{\lambda(L(s,w)-\text{Tr}[L(s,w)(\rho_{\text{test}}(s)\otimes\sigma_{\text{hyp}}^{A}(s,w))\mathbb{1}_{\text{test,hyp}}])} \right] \quad (A.20) $$

$$ = \sum_{i=1}^{m} \log \text{Tr} \left[ (\rho_{\text{test},i}(Z_i) \otimes \sigma_{\text{hyp},i}^{A}(z_i, w)) \cdot e^{\frac{\lambda}{m}(L_i(z_i, w) - \text{Tr}[L_i(z_i, w)(\rho_{\text{test},i}(Z_i) \otimes \sigma_{\text{hyp},i}^{A}(z_i, w))\mathbb{1}_{\text{test,hyp},i})} \right] \quad (A.21) $$

$$ \le \sum_{i=1}^{m} \frac{\alpha_i^2 \lambda^2}{2m^2}. \quad (A.22) $$

Therefore, $L(s, w)$ is $\alpha$-sub-gaussian w.r.t. $\rho_{\text{test}}(s) \otimes \sigma_{\text{hyp}}^{A}(s, w)$ with sub-gaussianity parameter $\alpha = m^{-1}\sqrt{\sum_{i=1}^{m} \alpha_i^2}$, for every $(s, w) \in \mathbb{Z}^m \times \mathcal{W}$.
Using the sub-gaussianity assumption on the Tr[$L_i(Z_i, w) (\rho_{test,i}(Z_i) \otimes \sigma_{hyp,i}^A(Z_i, w))$], we see that

$$ \log \mathbb{E}_{S \sim P^m} \left[ e^{\lambda(\mathrm{Tr}[L(S,w)(\rho_{\mathrm{test}}(S) \otimes \sigma_{\mathrm{hyp}}^A(S,w))])} - \mathbb{E}_{S \sim P^m} [\mathrm{Tr}[L(S,w)(\rho_{\mathrm{test}}(S) \otimes \sigma_{\mathrm{hyp}}^A(S,w))]] \right] \quad (A.23) $$

$$ = \sum_{i=1}^{m} \log \mathbb{E}_{Z_i \sim P} \left[ \frac{\lambda}{e^m} \left( \mathrm{Tr}[L_i(Z_i, w)(\rho_{\mathrm{test},i}(Z_i) \otimes \sigma_{\mathrm{hyp},i}^A(Z_i, w))] - \mathbb{E}_{Z_i \sim P} [\mathrm{Tr}[L_i(Z_i, w)(\rho_{\mathrm{test},i}(Z_i) \otimes \sigma_{\mathrm{hyp},i}^A(Z_i, w))]] \right) \right] \quad (A.24) $$

$$ \leq \sum_{i=1}^{m} \frac{\beta_i^2 \lambda^2}{2m^2}. \quad (A.25) $$

In other words, Tr[$L(S, w) (\rho_{test}(S) \otimes \sigma_{hyp}^A(S, w))$], with $S \sim P^m$, is $\beta$-sub-gaussian with sub-gaussianity parameter $\beta = m^{-1}\sqrt{\sum_{i=1}^m \beta^2}$, for every $w \in W$. Therefore, we can apply Corollary 4.20 and obtain the claimed bound, once we use that $\sigma^A(s, w) = \bigotimes_{i=1}^m \sigma_i^A(z_i, w)$ implies $I(\mathrm{test}; \mathrm{hyp})_{\sigma^A(s, w)} = \sum_{i=1}^m I(\mathrm{test}; \mathrm{hyp})_{\sigma_i^A(z_i, w)}$. $\square$

*Proof of Corollary 5.1.* On the one hand, we have

$$ \left| \mathbb{E}_{\hat{w}} \mathbb{E}_{\bar{Z}_{m+1}} \left[ \left| \mathrm{Tr}[E(\bar{Z}_{m+1})\rho_0] - \mathrm{Tr}[E(\bar{Z}_{m+1})\rho_0(\hat{w})] \right| \right] - R_{\rho}(\mathcal{A}) \right| \quad (A.26) $$

$$ \leq \mathbb{E}_{\bar{Z}_{m+1}} \mathbb{E}_{\bar{C}_{\ell}^{(m+1)} | \bar{Z}_{m+1}} \left[ \left| \mathrm{Tr}[E(\bar{Z}_{m+1})\rho_0] - \frac{1}{m_{\mathrm{test}}} \sum_{\ell=1}^{m_{\mathrm{test}}} \bar{C}_{\ell}^{(m+1)} \right| \right] \quad (A.27) $$

$$ \leq \frac{C}{\sqrt{m_{\mathrm{test}}}}, \quad (A.28) $$

where the first step is an application of the reverse triangle inequality and the second step is via first conditioning on $\bar{Z}_{m+1}$ and then using Hoeffding-based sub-gaussianity, as already argued in Section 5.1. On the other hand, we have

$$ \hat{R}_{\rho}(\mathcal{A}) = \mathbb{E}_{S \sim P^{2m}} \mathbb{E}_{C_{\ell}^{(i)} | S} \mathbb{E}_{\hat{W}} \left[ \hat{R}_{\mathrm{test}}^{S_{(m+1):2m}, C_{\ell}^{(i)}(\hat{W})} \right] \quad (A.29) $$

$$ = \mathbb{E}_{S \sim P^{2m}} \mathbb{E}_{C_{\ell}^{(i)} | S} \mathbb{E}_{\hat{W}} \left[ \frac{1}{m} \sum_{i=m+1}^{2m} \left| \mathrm{Tr}[E(Z_i)\rho_0(\hat{W})] - \frac{1}{m_{\mathrm{test}}} \sum_{\ell=1}^{m_{\mathrm{test}}} C_{\ell}^{(i)} \right| \right] \quad (A.30) $$

$$ \leq \mathbb{E}_{S \sim P^{2m}} \mathbb{E}_{B_{\ell}^{(i)} | S} \left[ \frac{1}{m} \sum_{i=m+1}^{2m} \left| \mathrm{Tr}[E(Z_i)\rho_0(\hat{W})] - \frac{1}{m_{\mathrm{train}}} \sum_{\ell=1}^{m_{\mathrm{train}}} B_{\ell}^{(i)} \right| \right] \quad (A.31) $$

$$ + \mathbb{E}_{S \sim P^{2m}} \mathbb{E}_{B_{\ell}^{(i)} | S} \left[ \frac{1}{m} \sum_{i=m+1}^{2m} \left| \mathrm{Tr}[E(Z_i)\rho_0] - \frac{1}{m_{\mathrm{train}}} \sum_{\ell=1}^{m_{\mathrm{train}}} B_{\ell}^{(i)} \right| \right] \quad (A.32) $$

$$ + \mathbb{E}_{S \sim P^{2m}} \mathbb{E}_{C_{\ell}^{(i)} | S} \left[ \frac{1}{m} \sum_{i=m+1}^{2m} \left| \mathrm{Tr}[E(Z_i)\rho_0] - \frac{1}{m_{\mathrm{test}}} \sum_{\ell=1}^{m_{\mathrm{test}}} C_{\ell}^{(i)} \right| \right] \quad (A.33) $$

$$ = \mathbb{E}_{S \sim P^{2m}} \mathbb{E}_{B_{\ell}^{(i)} | S} \left[ \inf_{w \in W_1} \frac{1}{m} \sum_{i=m+1}^{2m} \left| \mathrm{Tr}[E(Z_i)\rho_0(w)] - \frac{1}{m_{\mathrm{train}}} \sum_{\ell=1}^{m_{\mathrm{train}}} B_{\ell}^{(i)} \right| \right] \quad (A.34) $$

$$ + \mathbb{E}_{S \sim P^{2m}} \mathbb{E}_{B_{\ell}^{(i)} | S} \left[ \frac{1}{m} \sum_{i=m+1}^{2m} \left| \mathrm{Tr}[E(Z_i)\rho_0] - \frac{1}{m_{\mathrm{train}}} \sum_{\ell=1}^{m_{\mathrm{train}}} B_{\ell}^{(i)} \right| \right] \quad (A.35) $$

$$ + \mathbb{E}_{S \sim P^{2m}} \mathbb{E}_{C_{\ell}^{(i)} | S} \left[ \frac{1}{m} \sum_{i=m+1}^{2m} \left| \mathrm{Tr}[E(Z_i)\rho_0] - \frac{1}{m_{\mathrm{test}}} \sum_{\ell=1}^{m_{\mathrm{test}}} C_{\ell}^{(i)} \right| \right] \quad (A.36) $$
$$ \leq \mathbb{E}_{S \sim P^{2m}} \left[ \inf_{w \in W_1} \frac{1}{m} \sum_{i=m+1}^{2m} \left| \mathrm{Tr}[E(Z_i)\rho_0(w)] - \mathrm{Tr}[E(Z_i)\rho_0] \right| \right] \quad (A.37) $$

$$ + 2 \mathbb{E}_{S \sim P^{2m}} \mathbb{E}_{B_{\ell}^{(i)}|S} \left[ \frac{1}{m} \sum_{i=m+1}^{2m} \left| \mathrm{Tr}[E(Z_i)\rho_0] - \frac{1}{m_{\mathrm{train}}} \sum_{\ell=1}^{m_{\mathrm{train}}} B_{\ell}^{(i)} \right| \right] \quad (A.38) $$

$$ + \mathbb{E}_{S \sim P^{2m}} \mathbb{E}_{C_{\ell}^{(i)}|S} \left[ \frac{1}{m} \sum_{i=m+1}^{2m} \left| \mathrm{Tr}[E(Z_i)\rho_0] - \frac{1}{m_{\mathrm{test}}} \sum_{\ell=1}^{m_{\mathrm{test}}} C_{\ell}^{(i)} \right| \right] \quad (A.39) $$

$$ \leq \mathbb{E}_{S \sim P^{2m}} \left[ \inf_{w \in W_1} \frac{1}{m} \sum_{i=m+1}^{2m} \left| \mathrm{Tr}[E(Z_i)\rho_0(w)] - \mathrm{Tr}[E(Z_i)\rho_0] \right| \right] \quad (A.40) $$

$$ + C \left( \frac{1}{\sqrt{m_{\mathrm{train}}}} + \frac{1}{\sqrt{m_{\mathrm{test}}}} \right). \quad (A.41) $$

Here, the first step is plugging in the definition of $\hat{R}_{S(m+1):2m, C_{\ell}^{(i)}}(\cdot)$, the second step holds by applying the triangle inequality twice, the third step uses the definition of $\hat{W}$, the fourth step is one more triangle inequality, and the final step follows from Hoeffding-type sub-gaussianity bounds.

To finish the proof, we need the following fact:

**Claim A.3.** With the notation introduced above,

$$ \mathbb{E}_{S \sim P^{2m}} \left[ \inf_{w \in W_1} \frac{1}{m} \sum_{i=m+1}^{2m} \left| \mathrm{Tr}[E(Z_i)\rho_0(w)] - \mathrm{Tr}[E(Z_i)\rho_0] \right| \right] \quad (A.42) $$

$$ \leq \inf_{w \in W} \mathbb{E}_{\bar{Z}_{m+1}} \left[ \left| \mathrm{Tr}[E(\bar{Z}_{m+1})\rho_0] - \mathrm{Tr}[E(\bar{Z}_{m+1})\rho_0(w)] \right| \right] + \tilde{\epsilon} + C \sqrt{\frac{\log(|W_1|)}{m}}. \quad (A.43) $$

where $C > 0$ is some positive constant.

*Proof.* See below.

<figure><img src="image_5.png" /></figure>

Combining Claim A.3 with our previous upper bound on $\hat{R}_{\rho}(A)$, we have shown

$$ \hat{R}_{\rho}(A) \leq \inf_{w \in W} \mathbb{E} \left[ \left| \mathrm{Tr}[E(\bar{Z}_{m+1})\rho_0] - \mathrm{Tr}[E(\bar{Z}_{m+1})\rho_0(w)] \right| \right] + \tilde{\epsilon} \quad (A.44) $$

$$ + C \left( \sqrt{\frac{\log(|W_1|)}{m}} + \frac{1}{\sqrt{m_{\mathrm{train}}}} + \frac{1}{\sqrt{m_{\mathrm{test}}}} \right). \quad (A.45) $$

Finally, once we recall the bound $|W_1| \leq (2/\tilde{\epsilon})^{C \log(d)/\tilde{\epsilon}^2}$ on the size of the covering net, we can bring together our upper bound on $R_{\rho}(A)$, our upper bound on $\hat{R}_{\rho}(A)$, and our generalization error bound to obtain

$$ \mathrm{excess}_{\rho}(A) \leq \mathrm{gen}_{\rho}(A) + \tilde{\epsilon} + \mathcal{O} \left( \sqrt{\frac{\log(|W_1|)}{m}} + \sqrt{\frac{\log(|W_1|)}{m_{\mathrm{train}}}} + \frac{1}{\sqrt{m_{\mathrm{test}}}} \right) \quad (A.46) $$

$$ \leq \tilde{\epsilon} + \tilde{\mathcal{O}} \left( \sqrt{\frac{\log(d)}{m\tilde{\epsilon}^2}} + \frac{1}{\sqrt{m_{\mathrm{train}}}} + \frac{1}{\sqrt{m_{\mathrm{test}}}} \right), \quad (A.47) $$

as claimed.

<figure><img src="image_6.png" /></figure>
Proof of Claim A.3. First recall that the chosen covering net $W_1$ depends only on $Z_1, \dots, Z_m$, so that we can exchange $\mathbb{E}_{Z_{m+1}, \dots, Z_{2m} \sim P^m}$ and $\inf_{w \in W_1}$ to obtain the bound

$$ \mathbb{E}_{S \sim P^{2m}} \left[ \inf_{w \in W_1} \frac{1}{m} \sum_{i=m+1}^{2m} \left| \mathrm{Tr}[E(Z_i)\rho_0(w)] - \mathrm{Tr}[E(Z_i)\rho_0] \right| \right] \quad (A.48) $$

$$ \le \mathbb{E}_{(Z_1, \dots, Z_m) \sim P^m} \left[ \inf_{w \in W_1} \mathbb{E}_{(Z_{m+1}, \dots, Z_{2m}) \sim P^m} \left[ \frac{1}{m} \sum_{i=m+1}^{2m} \left| \mathrm{Tr}[E(Z_i)\rho_0(w)] - \mathrm{Tr}[E(Z_i)\rho_0] \right| \right] \right] \quad (A.49) $$

$$ = \mathbb{E}_{(Z_1, \dots, Z_m) \sim P^m} \left[ \inf_{w \in W_1} \mathbb{E}_{\bar{Z}_{m+1} \sim P} \left[ \left| \mathrm{Tr}[E(\bar{Z}_{m+1})\rho_0(w)] - \mathrm{Tr}[E(\bar{Z}_{m+1})\rho_0] \right| \right] \right]. \quad (A.50) $$

Next, we define the following pieces of notation for the true risk with perfectly accurately evaluated quantum expectation values

$$ R(w) := \mathbb{E}_{\bar{Z}_{m+1} \sim P} \left[ \left| \mathrm{Tr}[E(\bar{Z}_{m+1})\rho_0(w)] - \mathrm{Tr}[E(\bar{Z}_{m+1})\rho_0] \right| \right], \quad (A.51) $$

the empirical risk with perfectly accurately evaluated quantum expectation values

$$ \hat{R}_s(w) := \frac{1}{m} \sum_{j=1}^{m} \left| \mathrm{Tr}[E(z_j)\rho_0(w)] - \mathrm{Tr}[E(z_j)\rho_0] \right|, \quad (A.52) $$

and the corresponding true risk minimizers

$$ w_{W_1} \in \operatorname{argmin}_{w \in W_1} R(w), \quad w_W \in \operatorname{argmin}_{w \in W} R(w), \quad (A.53) $$

and empirical risk minimizers

$$ \hat{w}_{W_1} \in \operatorname{argmin}_{w \in W_1} \hat{R}_s(w), \quad \hat{w}_W \in \operatorname{argmin}_{w \in W} \hat{R}_s(w). \quad (A.54) $$

With this, we can rewrite and bound

$$ \mathbb{E}_{(Z_1, \dots, Z_m) \sim P^m} \left[ \inf_{w \in W_1} \mathbb{E}_{\bar{Z}_{m+1} \sim P} \left[ \left| \mathrm{Tr}[E(\bar{Z}_{m+1})\rho_0(w)] - \mathrm{Tr}[E(\bar{Z}_{m+1})\rho_0] \right| \right] \right] \quad (A.55) $$

$$ - \inf_{w \in W} \mathbb{E}_{\bar{Z}_{m+1}} \left[ \left| \mathrm{Tr}[E(\bar{Z}_{m+1})\rho_0] - \mathrm{Tr}[E(\bar{Z}_{m+1})\rho_0(w)] \right| \right] \quad (A.56) $$

$$ = \mathbb{E}_{(Z_1, \dots, Z_m) \sim P^m} [R(w_{W_1})] - R(w_W) \quad (A.57) $$

$$ = \mathbb{E}_{(Z_1, \dots, Z_m) \sim P^m} [R(w_{W_1}) - R(w_W)] \quad (A.58) $$

$$ = \mathbb{E}_{(Z_1, \dots, Z_m) \sim P^m} [R(w_{W_1}) - R(w_W)] + \mathbb{E}_{(Z_1, \dots, Z_m) \sim P^m} [\hat{R}(\hat{w}_{W_1}) - \hat{R}(w_W)] \quad (A.59) $$

$$ - \mathbb{E}_{(Z_1, \dots, Z_m) \sim P^m} [\hat{R}(\hat{w}_{W_1}) - \hat{R}(w_W)] \quad (A.60) $$

$$ = \mathbb{E}_{(Z_1, \dots, Z_m) \sim P^m} [R(w_{W_1}) - \hat{R}(\hat{w}_{W_1})] + \mathbb{E}_{(Z_1, \dots, Z_m) \sim P^m} [\hat{R}(\hat{w}_{W_1}) - \hat{R}(w_W)] \quad (A.61) $$

$$ + \underbrace{\mathbb{E}_{S \sim P^m} [\hat{R}(w_W) - R(w_W)]}_{=0} \quad (A.62) $$

$$ = \underbrace{\mathbb{E}_{(Z_1, \dots, Z_m) \sim P^m} [R(w_{W_1}) - R(\hat{w}_{W_1})] + \mathbb{E}_{(Z_1, \dots, Z_m) \sim P^m} [R(\hat{w}_{W_1}) - \hat{R}(\hat{w}_{W_1})]}_{\le 0} \quad (A.63) $$
$$ + \underbrace{\mathbb{E}_{(Z_1, \dots, Z_m) \sim P^m} [\hat{R}(\hat{w}_W) - \hat{R}(w_W)]}_{\le 0} + \underbrace{\mathbb{E}_{(Z_1, \dots, Z_m) \sim P^m} [\hat{R}(\hat{w}_{W_1}) - \hat{R}(w_W)]}_{\le 0} \quad (A.64) $$

$$ \le \underbrace{\mathbb{E}_{(Z_1, \dots, Z_m) \sim P^m} \left[ \sup_{w \in W_1} R(w) - \hat{R}(w) \right]}_{\le 0} + \underbrace{\mathbb{E}_{(Z_1, \dots, Z_m) \sim P^m} \left[ \|\hat{w}_{W_1} - \hat{w}_W\|_{1, \{Z_j\}_{j=1}^m} \right]}_{\le 0} \quad (A.65) $$

$$ \le \underbrace{\mathbb{E}_{(Z_1, \dots, Z_m) \sim P^m} \left[ \sup_{w \in W_1} R(w) - \hat{R}(w) \right]}_{\le 0} + \tilde{\epsilon}. \quad (A.66) $$

Here, the second-to-last step used a reverse triangle inequality, and the final step holds because $W_1$ is by definition a $\tilde{\epsilon}$-covering net for W w.r.t. $\|\cdot\|_{2, \{Z_j\}_{j=1}^m}$ and thus also w.r.t. $\|\cdot\|_{1, \{Z_j\}_{j=1}^m}$.

Next, observe that, for any fixed $w \in W_1$, the random variable $R(w) - \hat{R}(w)$ is an average of $m$ i.i.d. centered 2-bounded random variables and thus is $(\frac{C}{\sqrt{m}})$-sub-gaussian by Hoeffding's Lemma. Using the equivalence of sub-gaussianity in terms of MGF bounds and tail bounds [Ver18, Proposition 2.5.2], this can now be combined with a union bound over $W_1$ to see that the random variable $\sup_{w \in W_1} R(w) - \hat{R}(w)$ is $(C\sqrt{\frac{\log(|W_1|)}{m}})$-sub-gaussian. Therefore, using again the $L_p$ bound version of sub-gaussianity [Ver18, Proposition 2.5.2], we conclude

$$ \mathbb{E}_{S \sim P^m} \left[ \sup_{w \in W_1} R(w) - \hat{R}(w) \right] \le C \sqrt{\frac{\log(|W_1|)}{m}}. \quad (A.67) $$

Plugging this into our previous bound and rearranging, we get the claimed inequality. $\square$