††thanks: This work was done when interned at JD Explore Academy.††thanks:
<EMAIL_ADDRESS>
# Transition role of entangled data in quantum machine learning

Xinbiao Wang  Institute of Artificial Intelligence, School of Computer
Science, Wuhan University, Hubei 430070, China  JD Explore Academy, Beijing
101111, China  Yuxuan Du  JD Explore Academy, Beijing 101111, China  Zhuozhuo
Tu  School of Computer Science, Faculty of Engineering, University of Sydney,
NSW 2008, Australia  Yong Luo  Institute of Artificial Intelligence, School of
Computer Science, Wuhan University, Hubei 430070, China  Xiao Yuan  Center on
Frontiers of Computing Studies, Peking University, Beijing 100871, China
Dacheng Tao  School of Computer Science, Faculty of Engineering, University of
Sydney, NSW 2008, Australia

(August 28, 2024)

###### Abstract

Entanglement serves as the resource to empower quantum computing. Recent
progress has highlighted its positive impact on learning quantum dynamics,
wherein the integration of entanglement into quantum operations or
measurements of quantum machine learning (QML) models leads to substantial
reductions in training data size, surpassing a specified prediction error
threshold. However, an analytical understanding of how the entanglement degree
in data affects model performance remains elusive. In this study, we address
this knowledge gap by establishing a quantum no-free-lunch (NFL) theorem for
learning quantum dynamics using entangled data. Contrary to previous findings,
we prove that the impact of entangled data on prediction error exhibits a dual
effect, depending on the number of permitted measurements. With a sufficient
number of measurements, increasing the entanglement of training data
consistently reduces the prediction error or decreases the required size of
the training data to achieve the same prediction error. Conversely, when few
measurements are allowed, employing highly entangled data could lead to an
increased prediction error. The achieved results provide critical guidance for
designing advanced QML protocols, especially for those tailored for execution
on early-stage quantum computers with limited access to quantum resources.

##  I Introduction

Quantum entanglement, an extraordinary characteristic of the quantum realm,
drives the superiority of quantum computers beyond classical computers
feynman2018simulating . Over the past decade, diverse quantum algorithms
leveraging entanglement have been designed to advance cryptography
shor1999polynomial ; lanyon2007experimental  and optimization deutsch1992rapid
; grover1996fast ; harrow2009quantum ; lloyd2014quantum ; du2020quantum_dp ,
delivering runtime speedups over classical approaches. Motivated by the
exceptional abilities of quantum computers and the astonishing success in
machine learning, a nascent frontier known as quantum machine learning (QML)
has emerged schuld2015introduction ; biamonte2017quantum ;
ciliberto2018quantum ; dunjko2018machine ; li2022recent ; tian2022recent ;
cerezo2022challenges , seeking to outperform classical models in specific
learning tasks peruzzo2014variational ; moll2018quantum ;
havlivcek2019supervised ; abbas2021power ; huang2021power ; liu2021rigorous ;
wang2021towards ; du2021exploring ; du2022power ; du2022demystify .
Substantial progress has been made in this field, exemplified by the
introduction of QML protocols that offer provable advantages in terms of query
or sample complexity for learning quantum dynamics huang2021information ;
buadescu2021improved ; aharonov2022quantum ; chen2022exponential ;
huang2022quantum ; fanizza2022learning , as a fundamental problem toward
understanding the laws of nature 111In quantum dynamics learning, sample
complexity refers to the size of training data, or equivalently, the number of
quantum states in the training data; query complexity refers to the total
number of queries of the explored quantum system.. Most of these protocols
share a common strategy to gain advantages: the incorporation of entanglement
into quantum operations and measurements, leading to reduced complexity.
Nevertheless, an overlooked aspect in prior works is the impact of
incorporating entanglement in quantum input states, or entangled data, on the
advancement of QML in learning quantum dynamics. Due to the paramount role of
data in learning polyzotis2021can ; jakubik2022data ; jarrahi2022principles ;
whang2023data ; zha2023data ; zha2023data_survey , addressing this question
will significantly enhance our comprehension of the capabilities and
limitations of QML models.

A fundamental concept in machine learning that characterizes the capabilities
of learning models in relation to datasets is the No-Free-Lunch (NFL) theorem
wolpert1997no ; ho2002simple ; wolf2018mathematical ; adam2019no . The NFL
theorem yields a key insight: regardless of the optimization strategy
employed, the ultimate performance of models is contingent upon the size and
types of training data. This observation has spurred recent breakthroughs in
large language models, as extensive and meticulously curated training data
consistently yield superior results brown2020language ; ouyang2022training ;
bai2022training ; touvron2023llama ; zhao2023survey . In this regard,
establishing the quantum NFL theorem enables us to elucidate the specific
impact of entangled data on the efficacy of QML models in learning quantum
dynamics. Concretely, the achieved theorem can shed light on whether the
utilization of entangled data empowers QML models to achieve comparable or
even superior performance compared to low-entangled or unentangled data, while
simultaneously reducing the sample complexity required 222Although initial
attempts poland2020no ; sharma2022reformulation  have been made to establish
quantum NFL theorems, they have relied on infinite sample complexity, thus
failing to address our concerns adequately. See SM A and SM B for details..
Building upon prior findings on the role of entanglement and the classical NFL
theorem, a reasonable speculation is that high-entangled data contributes to
the improved performance of QML models associated with the reduced sample
complexity, albeit at the cost of using extensive quantum resources to prepare
such data that may be unaffordable in the early stages of quantum computing
preskill2018quantum .

Figure 1: Illustration of quantum NFL setting with the entangled data. The
goal of the quantum learner is to learn a unitary $V_{\mathcal{X}}$ that can
accurately predict the output of the target unitary $U_{\mathcal{X}}$ under a
fixed observable $O$, where the subscript $\mathcal{X}$ refers to the quantum
system in which the operator $O$ act on. The learning process is as follows.
(a) A total number of $N$ entangled bipartite quantum states living in Hilbert
space $\mathcal{H}_{\mathcal{X}}\otimes\mathcal{H}_{\mathcal{R}}$
($\mathcal{R}$ denotes the reference system) are taken as inputs, dubbed
entangled data. (b) Quantum learner proceeds incoherent learning. The
entangled data separately interacts with the target unitary $U_{\mathcal{X}}$
(agnostic) and the candidate hypothesis $V_{\mathcal{X}}$ extracted from the
same Hypothesis set $H$. (c) The quantum learner is restricted to leverage the
finite measured outcomes of the observable $O$ on the output states of
$U_{\mathcal{X}}$ and $V_{\mathcal{X}}$ to conduct learning. (d) A classical
computer is exploited to infer $V^{*}$ that best estimates $U_{\mathcal{X}}$
according to the measurement outcomes. For example, in the case of variational
quantum algorithms, the classical computer serves as an optimizer to update
the tunable parameters of the ansatz $V_{\mathcal{X}}$. (e) The learned
unitary $V^{*}$ is used to predict the output of unseen quantum states in
Hilbert space $\mathcal{H}_{\mathcal{X}}$ under the evolution of the target
unitary $U_{\mathcal{X}}$ and the measurement of $O$. A large Schmidt rank $r$
can enhance the prediction accuracy when combined with a large number of
measurements $m$, but may lead to a decrease in accuracy when $m$ is small.

In this study, we negate the above speculation and exhibit the transition role
of entangled data when QML models incoherently learn quantum dynamics, as
shown in Fig. 1. In the incoherent learning scenario, the quantum learner is
restricted to utilizing datasets with varying degrees of entanglement to
operate on an unknown unitary and inferring its dynamics using the finite
measurement outcomes collected under the projective measurement. The entangled
data refers to quantum states that are entangled with a reference system, with
the degree of entanglement quantitatively characterized by the Schmidt rank
$r$. We rigorously show that within the context of NFL, the entangled data has
a dual effect on the prediction error according to the number of measurements
$m$ allowed. Particularly, with sufficiently large $m$, increasing $r$ can
consistently reduce the required size of training data for achieving the same
prediction error. On the other hand, when $m$ is small, the train data with
large $r$ not only requires a significant volume of quantum resources for
states preparation, but also amplifies the prediction error. As a byproduct,
we prove that the lower bound of the query complexity for achieving a
sufficiently small prediction error matches the optimal lower bound for
quantum state tomography with nonadaptive measurements. Numerical simulations
are conducted to support our theoretical findings. In contrast to the previous
understanding that entanglement mostly confers benefits to QML in terms of
sample complexity, the transition role of entanglement identified in this work
deepens our comprehension of the relation between quantum information and QML,
which facilitates the design of QML models with provable advantages.

##  II Main results

We first recap the task of learning quantum dynamics. Let
$U\in\mathbb{S}\mathbb{U}(2^{n})$ be the target unitary and
$O\in\mathbb{C}^{2^{n}\times 2^{n}}$ be the observable which is a Hermitian
matrix acting on an $n$-qubit quantum system. Here we specify the observable
as the projective measurement $O=\ket{o}\bra{o}$ since any observable reads
out the classical information from the quantum system via their eigenvectors.
The goal of the quantum dynamics learning is to predict the functions of the
form

$f_{U}(\psi)=\operatorname{Tr}(OU\ket{\psi}\bra{\psi}U^{\dagger}),$ (1)

where $\ket{\psi}$ is an $n$-qubit quantum state living in a
$2^{n}$-dimensional Hilbert space $\mathcal{H}_{\mathcal{X}}$. This task can
be done by employing the training data $\mathcal{S}$ to construct a unitary
$V_{\mathcal{S}}$, i.e., the learned hypothesis has the form of
$h_{{\mathcal{S}}}(\psi)=\operatorname{Tr}(OV_{\mathcal{S}}\ket{\psi}\bra{\psi}V_{\mathcal{S}}^{\dagger})$,
which is expected to accurately approximate $f_{U}(\psi)$ for the unseen data.
While the learned unitary acts on an $n$-qubit system
$\mathcal{H}_{\mathcal{X}}$, the input state could be entangled with a
reference system $\mathcal{H}_{\mathcal{R}}$, i.e.,
$\ket{\psi}\in\mathcal{H}_{\mathcal{X}}\otimes\mathcal{H}_{\mathcal{R}}$. We
suppose that all input states have the same Schmidt rank
$r\in\\{1,\cdots,2^{n}\\}$. Then the response of the state $\ket{\psi_{j}}$ is
given by the measurement output $\bm{o}_{j}=\sum_{k=1}^{m}\bm{o}_{jk}/m$,
where $m$ is the number of measurements and $\bm{o}_{jk}$ is the output of the
$k$-th measurement of the observable $O$ on the output quantum state
$(U\otimes\mathbb{I}_{\mathcal{R}})\ket{\psi_{j}}$. In this manner, the
training data with $N$ examples takes the form
$\mathcal{S}=\\{(\ket{\psi_{j}},{\bm{o}}_{j}):\ket{\psi_{j}}\in\mathcal{H}_{\mathcal{X}}\otimes\mathcal{H}_{\mathcal{R}},\mathbb{E}[\bm{o}_{j}]=u_{j}\\}_{j=1}^{N}$
with
$u_{j}=\operatorname{Tr}((U^{\dagger}OU\otimes\mathbb{I}_{\mathcal{R}})\ket{\psi_{j}}\bra{\psi_{j}})$
being the expectation value of the observable $O$ on the state
$(U\otimes\mathbb{I}_{\mathcal{R}})\ket{\psi_{j}}$ and $N$ being the size of
the training data.

The risk function is a crucial measure in statistical learning theory to
quantify how well the hypothesis function $h_{{\mathcal{S}}}$ performs in
predicting $f_{U}$, defined as

$R_{U}(V_{{\mathcal{S}}})=\int\mathrm{d}{\psi}\left(f_{U}(\psi)-h_{{\mathcal{S}}}(\psi)\right)^{2},$
(2)

where the integral is over the uniform Haar measure $\mathrm{d}{\psi}$ on the
state space. Intuitively, $R_{U}(V_{{\mathcal{S}}})$ amounts to the average
square error distance between the true output $f(\psi)$ and the hypothesis
output $h_{\mathcal{S}}(\psi)$.

Under the above setting, we prove the following quantum NFL theorem in
learning quantum dynamics, where the formal statement and proof are deferred
to SM C.

######  Theorem 1 (Quantum NFL theorem in learning quantum dynamics,
informal).

Following the settings in Eqn. (1), suppose that the training error of the
learned hypothesis on the training data $\mathcal{S}$ is less than
$\varepsilon=\mathcal{O}(1/2^{n})$. Then the lower bound of the averaged
prediction error in Eqn. (2) yields

$\mathbb{E}_{U,\mathcal{S}}R_{U}(V_{\mathcal{S}})=\Omega\left(\frac{\tilde{\varepsilon}^{2}}{4^{n}}\left(1-\frac{N\cdot\min\\{m/(rc_{1}),rn\\}}{2^{n}c_{2}}\right)\right),$

where $c_{1}=128(2^{n}+1)/\tilde{\varepsilon}^{2}$,
$c_{2}=\min\\{(1-2\tilde{\varepsilon})^{2},(64\tilde{\varepsilon}^{2}-1)^{2}\\}$,
$\tilde{\varepsilon}=\Theta(2^{n}\varepsilon)$, and the expectation is taken
over all target unitary $U$, entangled states $\ket{\psi_{j}}$ and measurement
outputs $\bm{o_{j}}$.

The achieved results indicate the transition role of the entangled data in
determining the prediction error. Particularly, when a sufficient number of
measurements $m$ is allowed such that the Schmidt rank $r$ obeys
$r<\sqrt{m/(c_{1}n)}$, the prediction error is determined by the term $rn$ and
hence increasing $r$ can constantly decrease the prediction error.
Accordingly, in the two extreme cases of $r=1$ and $r=2^{n}$, achieving zero
averaged risk requires $N=2^{n}c_{2}/n$ and $N=1$ training input states, where
the latter achieves an exponential reduction in the number of training data
compared with the former. This observation implies that the entangled data
empower QML with provable quantum advantage, which accords with the achieved
results of Ref. sharma2022reformulation  in the ideal coherent learning
protocol with infinite measurements.

By contrast, in the scenario with $r\geq\sqrt{m/(c_{1}n)}$, increasing $r$
could enlarge the prediction error. This result indicates that the entangled
data can be harmful to achieving quantum advantages, which contrasts with
previous results where the entanglement (e.g., entangled operations or
measurements) is believed to contribute to the quantum advantage jozsa2003role
; yoganathan2019one ; sharma2022reformulation . This counterintuitive
phenomenon stems from the fact that when incoherently learning quantum
dynamics, information obtained from each measurement decreases with the
increased $r$ and hence a small $m$ is incapable of extracting all information
of the target unitary carried by the entangled state.

Another implication of Theorem 1 is that although the number of measurements
$m$ contributes to a small prediction error, it is not decisive to the
ultimate performance of the prediction error. Specifically, when $m\geq
r^{2}c_{1}n$, further increasing $m$ could not help decrease the prediction
error which is determined by the entanglement and the size of the training
data, i.e., $r$ and $N$. Meanwhile, at least $r^{2}c_{1}n$ measurements are
required to fully utilize the power of entangled data. These results suggest
that the value of $m$ should be adaptive to $r$ to pursue a low prediction
error.

We next comprehend the scenario in which the lower bound of averaged risk in
Theorem 1 reaches zero and correlate with the results in quantum state
learning and quantum dynamics learning huang2021information ; huang2022quantum
; chen2022exponential ; buadescu2021improved ; yuen2023improved ;
anshu2023survey . In particular, the main focus of those studies is proving
the minimum query complexity of the target unitary to warrant zero risk. The
results in Theorem 1 indicate that the minimum query complexity is
$Nm={\Omega}(2^{n}rc_{1}c_{2})$, implying the proportional relation between
the entanglement degree $r$ and the query complexity. Notably, this lower
bound is tighter than that achieved in Ref. huang2021information  in the same
setting. The advance of our results stems from the fact that Ref.
huang2021information  simply employs Holevo’s theorem to give an upper bound
on the extracted information in a single measurement, while our bound
integrates more refined analysis such as the consideration of Schmidt rank
$r$, the direct use of a connection between the mutual information of the
target unitary $U$ and the measurement outputs $\bm{o}_{j}$, and the KL-
divergence of related distributions (Refer to SM C for more details).
Moreover, the adopted projective measurement $O$ in Eqn. (1) hints that the
learning task explored in our study amounts to learning a pure state
$U^{\dagger}OU$. From the perspective of state learning, the derived lower
bound in Theorem 1 is optimal for the nonadaptive measurement with a constant
number of outcomes lowe2022lower . Taken together, while the entangled data
hold the promise of gaining advantages in terms of the prediction error, they
may be inferior to the training data without entanglement in terms of the
query complexity.

The transition role of entanglement explained above leads to the following
construction rule of quantum learning models. First, when a large number of
measurements is allowed, the entangled data is encouraged to be used for
improving the prediction performance. To this end, initial research efforts
wu2004preparation ; basharov2006decay ; lemr2008preparation ;
lin2016preparation ; klco2020minimally ; schatzki2021entangled , which develop
effective methods for preparing and storing entangled states, may contribute
to QML. Second, when the total number of measurements is limited, it is
advised to refrain from using entangled data for learning quantum dynamics.

Figure 2: Simulation results of quantum NFL theorem when incoherently learning
quantum dynamics. (a) The averaged prediction error with a varied number of
measurements $m$ and Schmidt rank $r$ when $N=2$ and $N=8$. The z-axis refers
to the averaged prediction error defined in Eqn. (1). (b) The averaged
prediction error with the varied sizes of training data. The label
‘$r=a\leavevmode\nobreak\ \&\leavevmode\nobreak\ m=b$‘ refers that the Schmidt
rank is $a$ and the number of measurements is $b$. The label ‘($\times
2/d^{2}$)’ refers that the plotted prediction error is normalized by a
multiplier factor $2/d^{2}$.

Remark. The results of the transition role for entangled data achieved in
Theorem 1 can be generalized to the mixed states because the mixed state can
be produced by taking the partial trace of a pure entangled state.

##  III Numerical simulations

We conduct numerical simulations to exhibit the transition role of entangled
data, the effect of the number of measurements, and the training data size in
determining the prediction error. The omitted construction details and results
are deferred to SM D.

We focus on the task of learning an $n$-qubit unitary under a fixed projective
measurement $O=(\ket{0}\bra{0})^{\otimes n}$. The number of qubits is $n=4$.
The target unitary $U_{X}$ is chosen uniformly from a discrete set
$\\{U_{i}\\}_{i=1}^{M}$, where $M={2^{n}}$ refers to the set size and the
operators $U_{j}^{\dagger}OU_{j}$ with $U_{j}$ in this set are orthogonal. The
entangled states in $\mathcal{S}$ is uniformly sampled from the set
$\\{\sum_{j=1}^{r}\sqrt{c_{j}}U_{j}\ket{0}\otimes\ket{\xi_{j}}\leavevmode\nobreak\
|\leavevmode\nobreak\
(\sqrt{c_{1}},\cdots,\sqrt{c_{r}})^{\top}\in\text{SU}(r),\leavevmode\nobreak\
\ket{\xi_{j}}\in\text{SU}(2^{n})\\}$. The size of training data is
$N\in\\{1,2,\cdots,16\\}$ and the Schmidt rank takes
$r=\\{2^{0},\cdots,2^{4}\\}$. The number of measurements takes
$m\in\\{10,100,300,\cdots,5000,20000\\}$. We record the averaged prediction
error by learning four different $4$-qubit unitaries for $10$ training data.

The simulation results are displayed in Fig. 2. Particularly, Fig. 2(a) shows
that for both the cases of $N=2$ and $N=8$, the prediction error constantly
decreases with respect to an increased number of measurements $m$ and
increased Schmidt rank $r$ when the number of measurements is large enough,
namely $m>1000$. On the other hand, for a small number of measurements with
$m\leq 100$ in the case of $N=8$, as the Schmidt rank is continually
increased, the averaged prediction error initially decreases and then
increases after the Schmidt rank surpasses a critical point which is $r=3$ for
$m=10$ and $r=4$ for $m=100$. This phenomenon accords with the theoretical
results in Theorem 1 in the sense that the entangled data play a transition
role in determining the prediction error for a limited number of measurements.
This observation is also verified in Fig. 2(b) for the varied sizes of
training data, where for the small measurement times $m=100$, increasing the
Schmidt rank could be not helpful for decreasing the prediction error. By
contrast, a large training data size consistently contributes to a small
prediction error, which echoes with Theorem 1.

##  IV Discussion and outlook

In this study, we exploited the effect of the Schmidt rank of entangled data
on the performance of learning quantum dynamics with a fixed observable.
Within the framework of the quantum NFL theorem, our theoretical findings
reveal the transition role of entanglement in determining the ultimate model
performance. Specifically, increasing the Schmidt rank below a threshold
controlled by the number of measurements can enhance model performance,
whereas surpassing this threshold can lead to a deterioration in model
performance. Our analysis suggests that a large number of measurements is the
precondition to use entangled data to gain potential quantum advantages. In
addition, our results demystify the negative role of entangled data in the
measure of query complexity. Last, as with classical NFL theorem, we prove
that increasing the size of the training data always contributes to a better
performance in QML.

Our results motivate several important issues and questions needed to be
further investigated. The first research direction is exploring whether the
transition role of entangled data exists for other QML tasks such as learning
quantum unitaries or learning quantum channels with the response being
measurement output huang2021information ; huang2022quantum ; caro2022out ;
jerbi2023power ; caro2021generalization ; bisio2010optimal ; khatri2019quantum
; jones2022robust ; heya2018variational ; cirstoiu2020variational ;
gibbs2022dynamical ; huang2022learning ; caro2022learning . These questions
can be considered in both the coherent and incoherent learning protocols,
which are determined by whether the target and model system can coherently
interact and whether quantum information can be shared between them. Obtaining
such results would have important implications for using QML models to solve
practical tasks with provable advantages.

A another research direction is inquiring whether there exists a similar
transition role when exploiting entanglement in quantum dynamics and
measurements through the use of an ancillary quantum system. The answer for
the case of entangled measurement has been given under many specific learning
tasks bubeck2020entanglement ; huang2021information ; chen2022exponential ;
huang2022quantum  where the learning protocols with entangled measurements are
shown to achieve an exponential advantage over those without in terms the
access times to the target unitary. This quantum advantage arises from the
powerful information-extraction capabilities of entangled measurements. In
this regard, it is intriguing to investigate the effect of quantum
entanglement on model performance when entanglement is introduced in both the
training states and measurements, as entangled measurements offer a potential
solution to the negative impact of entangled data resulting from insufficient
information extraction via weak projective measurements. A positive result
could further enhance the quantum advantage gained through entanglement
exploitation.

## References

  * (1) Richard P Feynman.  Simulating physics with computers.  In Feynman and computation, pages 133–153. CRC Press, 2018.
  * (2) Peter W Shor.  Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer.  SIAM review, 41(2):303–332, 1999.
  * (3) Ben P Lanyon, Till J Weinhold, Nathan K Langford, Marco Barbieri, Daniel FV James, Alexei Gilchrist, and Andrew G White.  Experimental demonstration of a compiled version of shor’s algorithm with quantum entanglement.  Physical Review Letters, 99(25):250505, 2007.
  * (4) David Deutsch and Richard Jozsa.  Rapid solution of problems by quantum computation.  Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences, 439(1907):553–558, 1992.
  * (5) Lov K Grover.  A fast quantum mechanical algorithm for database search.  In Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, pages 212–219. ACM, 1996.
  * (6) Aram W Harrow, Avinatan Hassidim, and Seth Lloyd.  Quantum algorithm for linear systems of equations.  Physical review letters, 103(15):150502, 2009.
  * (7) Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost.  Quantum principal component analysis.  Nature Physics, 10(9):631, 2014.
  * (8) Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu, Shan You, and Dacheng Tao.  Quantum differentially private sparse regression learning.  IEEE Transactions on Information Theory, 68(8):5217–5233, 2022\.
  * (9) Maria Schuld, Ilya Sinayskiy, and Francesco Petruccione.  An introduction to quantum machine learning.  Contemporary Physics, 56(2):172–185, 2015.
  * (10) Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd.  Quantum machine learning.  Nature, 549(7671):195, 2017.
  * (11) Carlo Ciliberto, Mark Herbster, Alessandro Davide Ialongo, Massimiliano Pontil, Andrea Rocchetto, Simone Severini, and Leonard Wossnig.  Quantum machine learning: a classical perspective.  Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 474(2209):20170551, 2018.
  * (12) Vedran Dunjko and Hans J Briegel.  Machine learning & artificial intelligence in the quantum domain: a review of recent progress.  Reports on Progress in Physics, 81(7):074001, 2018.
  * (13) Weikang Li and Dong-Ling Deng.  Recent advances for quantum classifiers.  Science China Physics, Mechanics & Astronomy, 65(2):220301, 2022\.
  * (14) Jinkai Tian, Xiaoyu Sun, Yuxuan Du, Shanshan Zhao, Qing Liu, Kaining Zhang, Wei Yi, Wanrong Huang, Chaoyue Wang, Xingyao Wu, et al.  Recent advances for quantum neural networks in generative learning.  arXiv preprint arXiv:2206.03066, 2022.
  * (15) M Cerezo, Guillaume Verdon, Hsin-Yuan Huang, Lukasz Cincio, and Patrick J Coles.  Challenges and opportunities in quantum machine learning.  Nature Computational Science, 2(9):567–576, 2022.
  * (16) Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J Love, Alán Aspuru-Guzik, and Jeremy L O’brien.  A variational eigenvalue solver on a photonic quantum processor.  Nature communications, 5:4213, 2014.
  * (17) Nikolaj Moll, Panagiotis Barkoutsos, Lev S Bishop, Jerry M Chow, Andrew Cross, Daniel J Egger, Stefan Filipp, Andreas Fuhrer, Jay M Gambetta, Marc Ganzhorn, et al.  Quantum optimization using variational algorithms on near-term quantum devices.  Quantum Science and Technology, 3(3):030503, 2018.
  * (18) 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, 2019.
  * (19) Amira Abbas, David Sutter, Christa Zoufal, Aurélien Lucchi, Alessio Figalli, and Stefan Woerner.  The power of quantum neural networks.  Nature Computational Science, 1(6):403–409, 2021.
  * (20) Hsin-Yuan Huang, Michael Broughton, Masoud Mohseni, Ryan Babbush, Sergio Boixo, Hartmut Neven, and Jarrod R McClean.  Power of data in quantum machine learning.  Nature communications, 12(1):1–9, 2021.
  * (21) Yunchao Liu, Srinivasan Arunachalam, and Kristan Temme.  A rigorous and robust quantum speed-up in supervised machine learning.  Nature Physics, 17(9):1013–1017, 2021.
  * (22) Xinbiao Wang, Yuxuan Du, Yong Luo, and Dacheng Tao.  Towards understanding the power of quantum kernels in the NISQ era.  Quantum, 5:531, 2021.
  * (23) Yuxuan Du and Dacheng Tao.  On exploring practical potentials of quantum auto-encoder with advantages.  arXiv preprint arXiv:2106.15432, 2021.
  * (24) Yuxuan Du, Zhuozhuo Tu, Bujiao Wu, Xiao Yuan, and Dacheng Tao.  Power of quantum generative learning.  arXiv preprint arXiv:2205.04730, 2022.
  * (25) Yuxuan Du, Yibo Yang, Dacheng Tao, and Min-Hsiu Hsieh.  Demystify problem-dependent power of quantum neural networks on multi-class classification.  arXiv preprint arXiv:2301.01597, 2022.
  * (26) Hsin-Yuan Huang, Richard Kueng, and John Preskill.  Information-theoretic bounds on quantum advantage in machine learning.  Physical Review Letters, 126(19):190505, 2021.
  * (27) Costin Bădescu and Ryan O’Donnell.  Improved quantum data analysis.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1398–1411, 2021.
  * (28) Dorit Aharonov, Jordan Cotler, and Xiao-Liang Qi.  Quantum algorithmic measurement.  Nature communications, 13(1):887, 2022.
  * (29) Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, and Jerry Li.  Exponential separations between learning with and without quantum memory.  In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 574–585. IEEE, 2022.
  * (30) 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.
  * (31) Marco Fanizza, Yihui Quek, and Matteo Rosati.  Learning quantum processes without input control.  arXiv preprint arXiv:2211.05005, 2022.
  * (32) In quantum dynamics learning, sample complexity refers to the size of training data, or equivalently, the number of quantum states in the training data; query complexity refers to the total number of queries of the explored quantum system.
  * (33) Neoklis Polyzotis and Matei Zaharia.  What can data-centric ai learn from data and ml engineering?  arXiv preprint arXiv:2112.06439, 2021.
  * (34) Johannes Jakubik, Michael Vössing, Niklas Kühl, Jannis Walk, and Gerhard Satzger.  Data-centric artificial intelligence.  arXiv preprint arXiv:2212.11854, 2022.
  * (35) Mohammad Hossein Jarrahi, Ali Memariani, and Shion Guha.  The principles of data-centric ai (dcai).  arXiv preprint arXiv:2211.14611, 2022.
  * (36) Steven Euijong Whang, Yuji Roh, Hwanjun Song, and Jae-Gil Lee.  Data collection and quality challenges in deep learning: A data-centric ai perspective.  The VLDB Journal, pages 1–23, 2023.
  * (37) Daochen Zha, Zaid Pervaiz Bhat, Kwei-Herng Lai, Fan Yang, and Xia Hu.  Data-centric ai: Perspectives and challenges.  arXiv preprint arXiv:2301.04819, 2023.
  * (38) Daochen Zha, Zaid Pervaiz Bhat, Kwei-Herng Lai, Fan Yang, Zhimeng Jiang, Shaochen Zhong, and Xia Hu.  Data-centric artificial intelligence: A survey.  arXiv preprint arXiv:2303.10158, 2023.
  * (39) David H Wolpert and William G Macready.  No free lunch theorems for optimization.  IEEE transactions on evolutionary computation, 1(1):67–82, 1997\.
  * (40) Yu-Chi Ho and David L Pepyne.  Simple explanation of the no-free-lunch theorem and its implications.  Journal of optimization theory and applications, 115:549–570, 2002\.
  * (41) Michael M Wolf.  Mathematical foundations of supervised learning.  Lecture notes from Technical University of Munich, 2018.
  * (42) Stavros P Adam, Stamatios-Aggelos N Alexandropoulos, Panos M Pardalos, and Michael N Vrahatis.  No free lunch theorem: A review.  Approximation and Optimization: Algorithms, Complexity and Applications, pages 57–82, 2019.
  * (43) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  Advances in neural information processing systems, 33:1877–1901, 2020.
  * (44) Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al.  Training language models to follow instructions with human feedback.  Advances in Neural Information Processing Systems, 35:27730–27744, 2022.
  * (45) Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, et al.  Training a helpful and harmless assistant with reinforcement learning from human feedback.  arXiv preprint arXiv:2204.05862, 2022.
  * (46) Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al.  Llama: Open and efficient foundation language models.  arXiv preprint arXiv:2302.13971, 2023.
  * (47) Wayne Xin Zhao, Kun Zhou, Junyi Li, Tianyi Tang, Xiaolei Wang, Yupeng Hou, Yingqian Min, Beichen Zhang, Junjie Zhang, Zican Dong, et al.  A survey of large language models.  arXiv preprint arXiv:2303.18223, 2023.
  * (48) Although initial attempts poland2020no ; sharma2022reformulation  have been made to establish quantum NFL theorems, they have relied on infinite sample complexity, thus failing to address our concerns adequately. See SM A and SM B for details.
  * (49) John Preskill.  Quantum computing in the nisq era and beyond.  Quantum, 2:79, 2018.
  * (50) Kunal Sharma, M Cerezo, Zoë Holmes, Lukasz Cincio, Andrew Sornborger, and Patrick J Coles.  Reformulation of the no-free-lunch theorem for entangled datasets.  Physical Review Letters, 128(7):070501, 2022.
  * (51) Richard Jozsa and Noah Linden.  On the role of entanglement in quantum-computational speed-up.  Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 459(2036):2011–2032, 2003.
  * (52) Mithuna Yoganathan and Chris Cade.  The one clean qubit model without entanglement is classically simulable.  arXiv preprint arXiv:1907.08224, 2019.
  * (53) Henry Yuen.  An improved sample complexity lower bound for (fidelity) quantum state tomography.  Quantum, 7:890, 2023.
  * (54) Anurag Anshu and Srinivasan Arunachalam.  A survey on the complexity of learning quantum states.  arXiv preprint arXiv:2305.20069, 2023.
  * (55) Angus Lowe and Ashwin Nayak.  Lower bounds for learning quantum states with single-copy measurements.  arXiv preprint arXiv:2207.14438, 2022.
  * (56) Ying Wu, Marvin G Payne, EW Hagley, and L Deng.  Preparation of multiparty entangled states using pairwise perfectly efficient single-probe photon four-wave mixing.  Physical Review A, 69(6):063803, 2004.
  * (57) AM Basharov, VN Gorbachev, and AA Rodichkina.  Decay and storage of multiparticle entangled states of atoms in collective thermostat.  Physical Review A, 74(4):042313, 2006.
  * (58) Karel Lemr and Jaromír Fiurášek.  Preparation of entangled states of two photons in several spatial modes.  Physical Review A, 77(2):023802, 2008.
  * (59) Yiheng Lin, John P Gaebler, Florentin Reiter, Ting R Tan, Ryan Bowler, Yong Wan, Adam Keith, Emanuel Knill, S Glancy, K Coakley, et al.  Preparation of entangled states through hilbert space engineering.  Physical review letters, 117(14):140502, 2016.
  * (60) Natalie Klco and Martin J Savage.  Minimally entangled state preparation of localized wave functions on quantum computers.  Physical Review A, 102(1):012612, 2020.
  * (61) Louis Schatzki, Andrew Arrasmith, Patrick J Coles, and Marco Cerezo.  Entangled datasets for quantum machine learning.  arXiv preprint arXiv:2109.03400, 2021.
  * (62) Matthias C Caro, Hsin-Yuan Huang, Nicholas Ezzell, Joe Gibbs, Andrew T Sornborger, Lukasz Cincio, Patrick J Coles, and Zoë Holmes.  Out-of-distribution generalization for learning quantum dynamics.  arXiv preprint arXiv:2204.10268, 2022.
  * (63) Sofiene Jerbi, Joe Gibbs, Manuel S Rudolph, Matthias C Caro, Patrick J Coles, Hsin-Yuan Huang, and Zoë Holmes.  The power and limitations of learning quantum dynamics incoherently.  arXiv preprint arXiv:2303.12834, 2023.
  * (64) Matthias C Caro, Hsin-Yuan Huang, M Cerezo, Kunal Sharma, Andrew Sornborger, Lukasz Cincio, and Patrick J Coles.  Generalization in quantum machine learning from few training data.  arXiv preprint arXiv:2111.05292, 2021.
  * (65) Alessandro Bisio, Giulio Chiribella, Giacomo Mauro D’Ariano, Stefano Facchini, and Paolo Perinotti.  Optimal quantum learning of a unitary transformation.  Physical Review A, 81(3):032324, 2010.
  * (66) Sumeet Khatri, Ryan LaRose, Alexander Poremba, Lukasz Cincio, Andrew T Sornborger, and Patrick J Coles.  Quantum-assisted quantum compiling.  Quantum, 3:140, 2019.
  * (67) Tyson Jones and Simon C Benjamin.  Robust quantum compilation and circuit optimisation via energy minimisation.  Quantum, 6:628, 2022.
  * (68) Kentaro Heya, Yasunari Suzuki, Yasunobu Nakamura, and Keisuke Fujii.  Variational quantum gate optimization.  arXiv preprint arXiv:1810.12745, 2018.
  * (69) Cristina Cirstoiu, Zoe Holmes, Joseph Iosue, Lukasz Cincio, Patrick J Coles, and Andrew Sornborger.  Variational fast forwarding for quantum simulation beyond the coherence time.  npj Quantum Information, 6(1):82, 2020.
  * (70) Joe Gibbs, Zoë Holmes, Matthias C Caro, Nicholas Ezzell, Hsin-Yuan Huang, Lukasz Cincio, Andrew T Sornborger, and Patrick J Coles.  Dynamical simulation via quantum machine learning with provable generalization.  arXiv preprint arXiv:2204.10269, 2022.
  * (71) Hsin-Yuan Huang, Sitan Chen, and John Preskill.  Learning to predict arbitrary quantum processes.  arXiv preprint arXiv:2210.14894, 2022.
  * (72) Matthias C Caro.  Learning quantum processes and hamiltonians via the pauli transfer matrix.  arXiv preprint arXiv:2212.04471, 2022.
  * (73) Sebastien Bubeck, Sitan Chen, and Jerry Li.  Entanglement is necessary for optimal quantum property testing.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 692–703. IEEE, 2020.
  * (74) Kyle Poland, Kerstin Beer, and Tobias J Osborne.  No free lunch for quantum machine learning.  arXiv preprint arXiv:2003.14103, 2020.
  * (75) Alexander S Holevo.  Probabilistic and statistical aspects of quantum theory, volume 1.  Springer Science & Business Media, 2011.
  * (76) John Duchi.  Lecture notes for statistics 311/electrical engineering 377.  URL: https://stanford. edu/class/stats311/Lectures/full notes. pdf. Last visited on, 2:23, 2016.
  * (77) Mark M Wilde.  Quantum information theory.  Cambridge University Press, 2013.
  * (78) John Watrous.  The theory of quantum information.  Cambridge university press, 2018.
  * (79) Benoît Collins and Piotr Śniady.  Integration with respect to the haar measure on unitary, orthogonal and symplectic group.  Communications in Mathematical Physics, 264(3):773–795, 2006.
  * (80) Zbigniew Puchała and Jarosław Adam Miszczak.  Symbolic integration with respect to the haar measure on the unitary group.  arXiv preprint arXiv:1109.4244, 2011.
  * (81) Marco Cerezo, Akira Sone, Tyler Volkoff, Lukasz Cincio, and Patrick J Coles.  Cost function dependent barren plateaus in shallow parametrized quantum circuits.  Nature communications, 12(1):1–12, 2021.
  * (82) David H Wolpert.  The existence of a priori distinctions between learning algorithms.  Neural computation, 8(7):1391–1420, 1996.
  * (83) David H Wolpert.  The lack of a priori distinctions between learning algorithms.  Neural computation, 8(7):1341–1390, 1996.
  * (84) Kai-Min Chung and Han-Hsuan Lin.  Sample efficient algorithms for learning quantum channels in pac model and the approximate state discrimination problem.  arXiv preprint arXiv:1810.10938, 2018.
  * (85) Leonardo Banchi, Jason Pereira, and Stefano Pirandola.  Generalization in quantum machine learning: A quantum information standpoint.  PRX Quantum, 2(4):040321, 2021.
  * (86) Matthias C Caro, Elies Gil-Fuster, Johannes Jakob Meyer, Jens Eisert, and Ryan Sweke.  Encoding-dependent generalization bounds for parametrized quantum circuits.  Quantum, 5:582, 2021.
  * (87) Haoyuan Cai, Qi Ye, and Dong-Ling Deng.  Sample complexity of learning parametric quantum circuits.  Quantum Science and Technology, 7(2):025014, 2022.
  * (88) Yuxuan Du, Zhuozhuo Tu, Xiao Yuan, and Dacheng Tao.  Efficient measure for the expressivity of variational quantum algorithms.  Physical Review Letters, 128(8):080506, 2022.
  * (89) Alexandre B. Tsybakov.  Introduction to Nonparametric Estimation.  Springer New York, 2009.
  * (90) Yihui Quek, Daniel Stilck França, Sumeet Khatri, Johannes Jakob Meyer, and Jens Eisert.  Exponentially tighter bounds on limitations of quantum error mitigation.  arXiv preprint arXiv:2210.11505, 2022.
  * (91) Steven T Flammia, David Gross, Yi-Kai Liu, and Jens Eisert.  Quantum tomography via compressed sensing: error bounds, sample complexity and efficient estimators.  New Journal of Physics, 14(9):095022, 2012.
  * (92) Jeongwan Haah, Aram W Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu.  Sample-optimal tomography of quantum states.  In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 913–925, 2016.
  * (93) Michel Loève.  Probability theory.  Courier Dover Publications, 2017.
  * (94) Jarrod R McClean, Sergio Boixo, Vadim N Smelyanskiy, Ryan Babbush, and Hartmut Neven.  Barren plateaus in quantum neural network training landscapes.  Nature communications, 9(1):1–6, 2018.
  * (95) Kaining Zhang, Min-Hsiu Hsieh, Liu Liu, and Dacheng Tao.  Toward trainability of deep quantum neural networks.  arXiv preprint arXiv:2112.15002, 2021.
  * (96) Scott Aaronson.  Shadow tomography of quantum states.  In Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, pages 325–338, 2018.
  * (97) Huzihiro Araki and Elliott H Lieb.  Entropy inequalities.  Communications in Mathematical Physics, 18(2):160–170, 1970.
  * (98) Ingemar Bengtsson and Karol Życzkowski.  Geometry of quantum states: an introduction to quantum entanglement.  Cambridge university press, 2017.
  * (99) Alexander Semenovich Holevo.  Bounds for the quantity of information transmitted by a quantum communication channel.  Problemy Peredachi Informatsii, 9(3):3–11, 1973.
  * (100) Ryszard Horodecki, Paweł Horodecki, Michał Horodecki, and Karol Horodecki.  Quantum entanglement.  Reviews of modern physics, 81(2):865, 2009.

###### Contents

  1. I Introduction
  2. II Main results
  3. III Numerical simulations
  4. IV Discussion and outlook
  5. A Preliminaries
    1. A.1 Notation
    2. A.2 Random variables
    3. A.3 Information theory
    4. A.4 Haar integration
    5. A.5 Related work
  6. B Problem setup of learning quantum dynamics in the view of quantum NFL theorem
    1. B.1 Quantum NFL theorem for learning quantum dynamics in the ideal setting
    2. B.2 Quantum NFL theorem for learning quantum dynamics in the realistic scenario
  7. C Results of Theorem 1
    1. C.1 Discretizing the class of target functions through $2\varepsilon$-packing
    2. C.2 Reducing the learning problem to hypothesis testing
    3. C.3 Proof of Theorem 1
    4. C.4 Proof of Lemma 7-reducing the learning problem to hypothesis testing
    5. C.5 Proof of Lemma 9—bounding the local $2\varepsilon$-packing cardinality $|\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}|$
    6. C.6 Proof of Lemma 10—bounding the mutual information $I({X};\hat{X})$
    7. C.7 The tightness of the derived lower bound in Theorem 1 from the perspective of quantum state tomography
  8. D Numerical Simulations for the quantum NFL theorem
    1. D.1 Details of numerical simulations
    2. D.2 More numerical results

Roadmap: Supplementary Material (SM) A provides preliminaries for the
necessary mathematical background and introduces the related work. The problem
setup of quantum dynamics learning in the framework of quantum no-free-lunch
(NFL) theorem is presented in SM B. We elucidate the results and the proof of
Theorem 1 in SM C. Finally, SM D exhibits the numerical details omitted in the
main text and more numerical results.

##  Appendix A Preliminaries

In this section, we will first present some essential mathematical foundations
for deriving the main results of this work. It encompasses several key
aspects, such as the introduction of pertinent notations, random variables,
information theory, and Haar integration, which are separately elaborated upon
in SM A.1 to SM A.4. Moreover, to contextualize our work within the existing
literature, we conduct a comprehensive review of relevant studies in SM A.5.

###  A.1 Notation

We unify the notations throughout the whole work. The number of qubits and
training data size is denoted by $n$ and $N$, respectively. Let
$\mathcal{H}_{d}$ denote a $d$-dimensional Hilbert space. The Hilbert space of
an $n$-qubit system is denoted by $\mathcal{H}_{2^{n}}$. The $d$-dimensional
unitary group and special unitary group are denoted as $\mathbb{U}(d)$ and
$\mathbb{S}\mathbb{U}(d)$, respectively. The notations $[N]$ refers to the set
$\\{1,2,\cdots,N\\}$. We denote $\|\cdot\|_{1}$ as the trace norm and
$\|\cdot\|_{\operatorname{F}}$ as the Frobenius norm. The cardinality of a set
is denoted as $|\cdot|$. We use the standard bra-ket notation for pure quantum
states. The identity operator on the $d$-dimensional Hilbert space is denoted
by $\mathbb{I}_{d}$. We denote $\ket{\bm{e}_{k}}$ as the computational basis
with the $k$-th entry being one and the other entries being zero.

###  A.2 Random variables

We denote random variables using the capital letter, i.e., $X$, including
matrix-valued random variables. We use the lowercase letters (e.g., $p,q$) and
the capital letters (e.g., $\mathbb{P}$) with appropriate subscripts to denote
the probability density function (PDF) and the corresponding cumulative
distribution function (CDF) which obey
$\mathrm{d}\mathbb{P}_{X}(x)=p_{X}(x)\mathrm{d}x$. For instance, suppose $X$
is a random variable taking values in $\mathcal{X}$ according to some
distribution $p_{X}:\mathcal{X}\to[0,1]$, where $\mathcal{A}$ is the set of
Borel-measurable subsets holevo2011probabilistic  of $\mathcal{X}$. Let
$\mathrm{g}:\mathcal{X}\to\mathbb{R}$ be any function of $x$. We denote
$\mathbb{E}_{X}\mathrm{g}(X)$ and $\mathbb{E}_{X\sim p_{X}}\mathrm{g}(X)$
interchangeably as the expectation of $\rm{g}(\cdot)$ with respect to the
distribution $p_{X}$, i.e.,

$\int_{\mathcal{X}}\mathrm{g}(X)\mathrm{d}\mathbb{P}_{X}(x)\leavevmode\nobreak\
\text{or}\leavevmode\nobreak\
\int_{\mathcal{X}}\mathrm{g}(X)p_{X}(x)\mathrm{d}x,$

where the latter notation is used when there may be some ambiguity about the
distribution is. When no confusion occurs, we drop all subscripts and write
$\mathbb{E}\mathrm{g}(X)$. Next suppose we have random variables $(X,Y)$
jointly distributed on $\mathcal{X}\times\mathcal{Y}$. We use $p_{Y|x}(y)$ and
$p(y|X=x)$ interchangeably to denote the conditional probability that $Y=y$
given $X=x$.

###  A.3 Information theory

In this subsection, we review the basic definitions in information theory,
including (Shannon) entropy, KL-divergence, mutual information, and their
conditional versions. Refer to Refs. duchi2016lecture ; wilde2013quantum ;
watrous2018theory  for a more deep understanding. Throughout the whole paper,
$\log$ denotes the logarithm with base $2$. We first consider the scenario of
discrete random variables taking values in the same space.

Entropy. We begin with a central concept in information theory—the (Shannon)
entropy. Let $\mathbb{P}$ be a distribution on a finite set $\mathcal{X}$.
Denote the PDF as $p$ associated with $\mathbb{P}$. Let $X$ be a random
variable distributed according to $\mathbb{P}$. The entropy of $X$ (or of $p$)
is defined as

$H(X):=-\sum_{x\in\mathcal{X}}p(x)\log p(x).$ (3)

This quantity is always positive when $p(x)<1$ for all $x$, and vanishes if
and only if $X$ is a deterministic variable, i.e., $p(x)=1$ with taking $0\log
0=0$. The Shannon entropy measures the uncertainty about the random variable
$X$.

Let us consider another discrete random variable, denoted by $Y$, which takes
values in the set $\mathcal{Y}$. The joint distribution of $X$ and $Y$ can be
given by $p_{X,Y}:\mathcal{X}\times\mathcal{Y}\to[0,1]$. The joint entropy of
these random variables is

$H(X,Y)=-\sum_{x\in\mathcal{X}}\sum_{y\in\mathcal{Y}}p_{X,Y}(x,y)\log(p_{X,Y}(x,y))$
(4)

and the conditional entropy of $X$ given $Y$ refers to

$H(X|Y)=H(X,Y)-H(Y),$ (5)

which can be intuitively interpreted as the total information of $X$ and $Y$,
and the amount of information left in the random variable $X$ after observing
the random variable $Y$, respectively.

We next review some important properties of Shannon entropy.

######  Property 1 (Subadditivity of entropy, duchi2016lecture ).

Let $X_{1},\cdots,X_{t}$ be any sequence of random variables, we have

$H(X_{1},\cdots,X_{t})\leq H(X_{1})+\cdots+H(X_{t}).$ (6)

######  Property 2 (Maximum Value, Property 10.1.5 in wilde2013quantum ).

The maximum value of the entropy $H(X)$ for a random variable $X$ taking
values in an alphabet $\mathcal{X}$ is $\log|\mathcal{X}|$:

$H(X)\leq\log(|\mathcal{X}|).$ (7)

######  Property 3.

Let $X,Y$ be any two random variables, we have

$H(Y)\leq H(X,Y).$ (8)

This property can be obtained by observing the definition of conditional
entropy that $H(Y)=H(X,Y)-H(X|Y)$ and the non-negativity of entropy.

KL-divergence. KL-divergence is used to measure the distance between
probability distributions. Consider two discrete distributions (PDFs)
$p,q:\mathcal{X}\to[0,1]$ with $\mathcal{X}$ being the value space of the
associated random variables, the KL-divergence between $p$ and $q$ is given by

$D_{\operatorname{KL}}(p\leavevmode\nobreak\ \|q)=\left\\{\begin{aligned}
&\sum_{x\in\mathcal{X}}p(x)\log\frac{p(x)}{q(x)},&\leavevmode\nobreak\
\operatorname{supp}(p)\subseteq\operatorname{supp}(q),\\\
&\infty,&\leavevmode\nobreak\ \mbox{otherwise.}\end{aligned}\right.$

Notably, the KL-divergence $D_{\operatorname{KL}}(p\|q)\geq 0$, where the
equality holds if and only if $p(x)=q(x)$ for all $x\in\mathcal{X}$.
Particularly, employing the convexity of $\log$ and Jensen’s inequality yields

$\displaystyle
D_{\operatorname{KL}}(p\|q)=-\mathbb{E}\left[\log\frac{q(X)}{p(X)}\right]\geq-\log\mathbb{E}\left[\frac{q(X)}{p(X)}\right]=-\log\left(\sum_{x\in\mathcal{X}}p(x)\frac{q(x)}{p(x)}\right)=-\log(1)=0.$
(9)

Mutual information. The mutual information $I(X;Y)$ between $X$ and $Y$ is
defined as the KL-divergence between their joint probability distribution
$p_{X,Y}$ and their product of (marginal) probability distributions
$p_{X}p_{Y}$. Mathematically,

$I(X;Y):=D_{\operatorname{KL}}(p_{X,Y}\|p_{X}p_{Y})=\sum_{x,y}p_{X,Y}(x,y)\log\frac{p_{X,Y}(x,y)}{p_{X}(x)p_{Y}(y)}.$
(10)

According to the non-negativity property of KL-divergence, it is easy to see
that $I(X;Y)\geq 0$ and the equality holds if and only if random variables $X$
and $Y$ are independent, i.e., $p_{X,Y}(x,y)=p_{X}(x)p_{Y}(y)$. The mutual
information between two random variables can be defined in several
mathematically equivalent ways. Another definition used in this work expresses
the mutual information in terms of the entropy of random variables. It may be
shown that the above equation is equal to

$I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)=H(X)+H(Y)-H(X,Y).$ (11)

We would give a brief derivation of the equivalence between the definition of
mutual information given in the first equality of Eqn. (11) and that in Eqn.
(10), while the second equality and the third equality in Eqn. (11) employs
the definition of conditional entropy in Eqn. (5). Particularly, using Bayes’
rule, we have $P_{X,Y}(x,y)=p_{Y}(y)p_{X|Y}(x|y)$, so

$\displaystyle I(X;Y)=$
$\displaystyle\sum_{x,y}P_{Y}(y)p_{X|Y}(x|y)\log\frac{p_{X|Y}(x|y)}{P_{X}(x)}$
$\displaystyle=$
$\displaystyle-\sum_{x,y}P_{Y}(y)p_{X|Y}(x|y)\log{P_{X}(x)}+\sum_{y}P_{Y}(y)\sum_{x}p_{X|Y}(x|y)\log
p_{X|Y}(x|y)$ $\displaystyle=$ $\displaystyle H(X)-H(X|Y).$ (12)

In this end, the mutual information can be thought of as the amount of entropy
removed (on average) in $X$ by observing $Y$.

Analogous to the definition of conditional entropy, the conditional mutual
information between $X$ and $Y$ given a third random variable $Z$ is defined
as

$I(X;Y|Z):=\sum_{z}I(X;Y|Z=z)p(z)=H(X|Z)-H(X|Y,Z)=H(Y|Z)-H(Y|X,Z),$ (13)

which refers to the mutual information between $X$ and $Y$ when $Z$ is
observed (on average).

We now present three fundamental properties about the mutual information.
These facts will be leveraged to derive more stronger lower bounds on the
prediction error than those obtained by using Holevo’s theorem when the
measurements are subject to certain restrictions.

######  Property 4 (Chain rule for mutual information).

Let $X,Y_{1},Y_{2},\cdots,Y_{t}$ be any $t+1$ random variables, the mutual
information between $X$ and $Y_{1},\cdots,Y_{t}$ obeys

$I(X;Y_{1},\cdots,Y_{t})=\sum_{j=1}^{t}I(X;Y_{j}|Y_{j-1},\cdots,Y_{1}).$ (14)

######  Property 5 (Subadditivity of mutual information).

If $Y_{1},\cdots,Y_{t}$ are independent given $X$, the mutual information
between $X$ and $Y_{1},\cdots,Y_{t}$ obeys

$I(X;Y_{1},\cdots,Y_{t})\leq\sum_{j=1}^{t}I(X;Y_{j}).$ (15)

######  Property 6 (Data processing inequality).

Let the random variables $X,Y,Z$ form a Markov chain $X\to Y\to Z$ such that
if given $Y$, the random variables $X$ and $Z$ are independent. Then we have

$I(X;Z)\leq I(X;Y).$ (16)

###  A.4 Haar integration

In this subsection, we present a set of lemmas that enable the analytical
computation of integrals of polynomial functions over the unitary group and
the quantum state with respect to the unique normalized Haar measure. For a
more comprehensive discussion on this subject matter, we refer the readers to
Refs. collins2006integration ; puchala2011symbolic ; cerezo2021cost .

######  Lemma 1.

Let $\\{W_{y}\\}_{y\in Y}\subset U(d)$ form a unitary $t$-design with $t\geq
1$, and let $A,B:\mathcal{H}_{d}\to\mathcal{H}_{d}$ be arbitrary linear
operators. Then

$\frac{1}{|Y|}\sum_{y\in
Y}\operatorname{Tr}\left(W_{y}AW_{y}^{\dagger}B\right)=\int_{W\sim\operatorname{Haar}}\mathrm{d}W\operatorname{Tr}\left(WAW^{\dagger}B\right)=\frac{\operatorname{Tr}(A)\operatorname{Tr}(B)}{d}.$
(17)

######  Lemma 2.

Let $\\{W_{y}\\}_{y\in Y}\subset U(d)$ form a unitary $t$-design with $t\geq
2$, and let $A,B,C,D:\mathcal{H}_{d}\to\mathcal{H}_{d}$ be arbitrary linear
operators. Then

$\displaystyle\frac{1}{|Y|}\sum_{y\in
Y}\operatorname{Tr}\left(W_{y}AW_{y}^{\dagger}B\right)\operatorname{Tr}\left(W_{y}CW_{y}^{\dagger}D\right)=$
$\displaystyle\int_{W\sim\operatorname{Haar}}\mathrm{d}W\operatorname{Tr}(WAW^{\dagger}B)\operatorname{Tr}(WCW^{\dagger}D)$
$\displaystyle=$
$\displaystyle\frac{1}{d^{2}-1}\Big{(}\operatorname{Tr}(A)\operatorname{Tr}(B)\operatorname{Tr}(C)\operatorname{Tr}(D)+\operatorname{Tr}(AC)\operatorname{Tr}(BD)\Big{)}$
$\displaystyle-\frac{1}{d(d^{2}-1)}\Big{(}\operatorname{Tr}(AC)\operatorname{Tr}(B)\operatorname{Tr}(D)+\operatorname{Tr}(A)\operatorname{Tr}(C)\operatorname{Tr}(BD)\Big{)}.$
(18)

######  Lemma 3.

Let the quantum state $\ket{\phi}\in\mathcal{H}_{d}$ follows the Haar
distribution, and let $A:\mathcal{H}_{d}\to\mathcal{H}_{d}$ be arbitrary
linear operators. Then

$\int_{\phi\sim\operatorname{Haar}}\ket{\phi}\bra{\phi}\mathrm{d}\phi=\frac{\mathbb{I}_{d}}{d},\leavevmode\nobreak\
\mbox{and hence}\leavevmode\nobreak\
\int_{\phi\sim\operatorname{Haar}}\mathrm{d}{\phi}\operatorname{Tr}\left(\ket{\phi}\bra{\phi}A\right)=\frac{\operatorname{Tr}(A)}{d}.$
(19)

######  Lemma 4.

Let the quantum state $\ket{\phi}\in\mathcal{H}_{d}$ follows the Haar
distribution, and let $A,B:\mathcal{H}_{d}\to\mathcal{H}_{d}$ be arbitrary
linear operators. Then

$\int_{\phi\sim\operatorname{Haar}}\ket{\phi}\bra{\phi}^{\otimes
2}\mathrm{d}\phi=\frac{\mathbb{I}_{d}^{\otimes
2}+\operatorname{SWAP}}{d(d+1)},\leavevmode\nobreak\
\mbox{and}\leavevmode\nobreak\
\int_{\phi\sim\operatorname{Haar}}\mathrm{d}{\phi}\operatorname{Tr}\left(\ket{\phi}\bra{\phi}A\right)\operatorname{Tr}\left(\ket{\phi}\bra{\phi}B\right)=\frac{\operatorname{Tr}(A)\operatorname{Tr}(B)+\operatorname{Tr}(AB)}{d(d+1)},$
(20)

where the notation $\operatorname{SWAP}$ refers to the swap operator on the
space $\mathcal{H}_{d}^{\otimes 2}$.

######  Lemma 5.

Let $A:\mathcal{H}_{d}\to\mathcal{H}_{d}$ be arbitrary traceless linear
operators, i.e., $\operatorname{Tr}(A)=0$. Let $\ket{\mu}$ and $\ket{\nu}$ be
two orthogonal Haar random states. Then

$\int_{\nu\sim\operatorname{Haar}}\int_{\mu\sim\operatorname{Haar}}\operatorname{Tr}(A\ket{\mu}\bra{\mu})\operatorname{Tr}(A\ket{\nu}\bra{\nu})\mathrm{d}\mu\mathrm{d}\nu=-\frac{1}{d(d^{2}-1)}\operatorname{Tr}\big{(}A^{2}\big{)}.$
(21)

While Lemma 1 to Lemma 4 have been established in many previous literature
collins2006integration ; puchala2011symbolic ; cerezo2021cost , Lemma 5 is
particularly tailored to derive the main results of this work in a specific
setting. To this end, here we provide a brief derivation of Lemma 5 by
employing the results of Lemma 2.

###### Proof of Lemma 5.

We first observe that the orthogonal Haar random states $\ket{\mu}$ and
$\ket{\nu}$ can be treated as the arbitrary two columns of a Haar random
unitary $W$ in $\mathbb{S}\mathbb{U}(d)$. With this regard, $\ket{\mu}$ and
$\ket{\nu}$ can be expressed in the form of $\ket{\mu}=W\ket{0}^{\otimes n}$
and $\ket{\nu}=W\ket{1}^{\otimes n}$, respectively. Therefore, we have

$\displaystyle\int_{\nu\sim\operatorname{Haar}}\int_{\mu\sim\operatorname{Haar}}\operatorname{Tr}(A\ket{\mu}\bra{\mu})\operatorname{Tr}(A\ket{\nu}\bra{\nu})\mathrm{d}\mu\mathrm{d}\nu$
$\displaystyle=$
$\displaystyle\int_{W\sim\operatorname{Haar}}\operatorname{Tr}\left(AW\ket{0}\bra{0}^{\otimes
n}W^{\dagger})\operatorname{Tr}(AW\ket{1}\bra{1}^{\otimes
n}W^{\dagger}\right)\mathrm{d}W$ $\displaystyle=$
$\displaystyle\frac{1}{d^{2}-1}\left(\operatorname{Tr}\big{(}A\big{)}^{2}+\operatorname{Tr}\big{(}A^{2}\big{)}\operatorname{Tr}\big{(}\ket{0}\bra{0}^{\otimes
n}\ket{1}\bra{1}^{\otimes
n}\big{)}\right)-\frac{1}{d(d^{2}-1)}\left(\operatorname{Tr}\big{(}A^{2}\big{)}+\operatorname{Tr}\big{(}A\big{)}^{2}\operatorname{Tr}\big{(}\ket{0}\bra{0}^{\otimes
n}\ket{1}\bra{1}^{\otimes n}\big{)}\right)$ $\displaystyle=$
$\displaystyle-\frac{1}{d(d^{2}-1)}\operatorname{Tr}\big{(}A^{2}\big{)},$ (22)

where the second equality employs Lemma 2, the second equality follows
$\operatorname{Tr}(A)=0$ and $\operatorname{Tr}(\ket{0}\bra{0}^{\otimes
n}\ket{1}\bra{1}^{\otimes n})=0$. This completes the proof. ∎

###  A.5 Related work

In this subsection, we review prior literature related to the quantum NFL
theorem, quantum dynamics learning, and the main methodologies employed in the
proof of this work.

Quantum NFL theorem. The no-free-lunch (NFL) theorem is a celebrated result in
learning theory that limits one’s ability to learn a function with a training
dataset. It is widely studied in classical learning theory
wolpert1996existence ; wolpert1996lack ; wolpert1997no ; ho2002simple ;
wolf2018mathematical ; adam2019no . Ref. poland2020no  made the initial
attempt to establish NFL theorem in the context of quantum machine learning
where the inputs and outputs are quantum states. Ref. sharma2022reformulation
reformulated the quantum NFL theorem in the quantum-assisted learning
protocols where the bipartite entangled states are prepared as the input
states by introducing a reference quantum system. They demonstrated that the
utilization of entangled data can remove the exponential cost of the training
data size for learning unitaries with unentangled data. However, their results
are established in the ideal setting with infinite measurements, which can not
apply to quantifying the practical power of entangled data.

Quantum dynamics learning. Quantum computers have the potential to enhance
classical machine-learning models. One such application is the utilization of
quantum dynamics learning, which involves the conversion of an analogue
quantum unitary into a digital form that can be subsequently examined on
either a quantum or classical computer. Numerous studies have delved into
understanding the provable quantum advantage in terms of sample complexity,
aiming to achieve approximate learning of quantum unitaries with small
prediction errors. For instance, Ref. chung2018sample ; huang2021power ;
liu2021rigorous ; caro2021generalization ; wang2021towards ; abbas2021power ;
banchi2021generalization ; caro2021encoding ; cai2022sample ; du2022efficient
; du2022demystify ; jerbi2023power  studied in variational quantum machine
learning how the sample complexity bounds are determined by the type of
datasets and the complexity of the quantum model which acts as an unknown
quantum unitary to be learned. These findings are obtained upon assumptions
regarding the complexity of the unknown unitaries or the type of datasets,
which are subsequently utilized to constrain the information-theoretic
complexity of the learning task. As a result, these approaches are typically
not applicable to general datasets and highly complex quantum unitaries
without specific conditions. Recently, a growing literatures prove the
exponential separation in sample complexity between learning unitaries with
and without quantum memory chen2022exponential ; huang2022learning ;
huang2021information ; buadescu2021improved . However, the proposed algorithms
heavily depend on the entanglement measurement for optimal tomography, which
may pose significant challenges from a practical standpoint.

Techniques employed in the proof. The main used tool for proving the lower
bound of the prediction error is Fano’s inequality. This inequality is widely
used for obtaining the lower bounds in both classical and quantum learning
theory with various formulations Tsybakov_2009 ; wilde2013quantum ;
duchi2016lecture ; quek2022exponentially . In the filed of quantum machine
learning, one of its applications involves utilizing Fano’s inequality to
derive the lower bound of sample complexity for quantum state tomography
flammia2012quantum ; haah2016sample ; lowe2022lower ; huang2021information .
Particularly, a fundamental framework for establishing such lower bounds
builds upon insights from Fano’s inequality Tsybakov_2009 ; wilde2013quantum ,
suggesting that performing tomography with sufficient precision accurately
reduces to distinguishing well-separated quantum states. However, the aim in
our work is to proving the lower bound of prediction errors for dynamics
learning. In this regard, we adopt another formulation of Fano’s inequality
given in Ref. duchi2016lecture , which is widely used in classical learning
theory for proving the lower bound of prediction errors. Such formulation
suggests that learning unitary with limited training data accurately reduces
to distinguishing well-separated PDF of the related measurement outputs.
Intuitively, the expression of Fano’s inequality used in this work and that
used in the context of quantum state tomography could be regarded as the dual
formulation in the sense that we employ the amount of training quantum states
to lower bound the prediction error while previous works exploited a pre-fixed
prediction error to lower bound the sample complexity.

Despite the various formulations of Fano’s inequality, a common and standard
technique in the field of density estimation involves “discretizing” the
learning problem. This technique is employed to achieve worst-case lower
bounds, which can be seen as the classical counterpart of quantum tomography
(see for example Chapter 2 of Ref. Tsybakov_2009 ). One way to rigorously
establish this argument is by utilizing Fano’s inequality in conjunction with
Holevo’s theorem, which offers an interpretation in terms of a communication
protocol between two parties, namely Alice and Bob. Holevo’s theorem is
conventionally employed to provide an upper bound on the mutual information
between the target message $X$, transmitted by Alice, and the decoded message
$\hat{X}$ received by Bob. However, there are two caveats to using Holevo’s
theorem in the context of the quantum NFL theorem. First, the utilization of
Holevo’s theorem does not take into account restrictions on the measurements
we are allowed to perform on the $N$ copies of the state. Second, it fails to
consider the limitations imposed by the availability of a limited number of
training states on the accessible information regarding $X$.

In contrast to previous studies, our approach distinguishes itself by directly
exploiting the connection between the mutual information of two random
variables and the Kullback-Leibler (KL) divergence of related distributions.
Additionally, we utilize techniques for Haar integration with respect to the
random training data and the random target unitary. Two crucial technical
steps in our approach involve analyzing the KL divergence instead of
individual measurement outcomes’ probabilities, as well as investigating the
maximal mutual information under the constraint of limited training states.
These steps enable us to establish tight lower bounds on prediction error
using a predetermined single-copy non-adaptive measurement strategy.

##  Appendix B Problem setup of learning quantum dynamics in the view of
quantum NFL theorem

For self-consistency, in this section we first recap the main results of the
quantum NFL theorem which is achieved in the ideal setting by the study
sharma2022reformulation . Then we introduce the learning problems of the
entanglement-assisted quantum NFL theorem in a realistic scenario for further
elucidation.

###  B.1 Quantum NFL theorem for learning quantum dynamics in the ideal
setting

In this subsection, we briefly recap the results achieved in Ref.
sharma2022reformulation  for self-consistency. The learning problem studied in
Ref. sharma2022reformulation  aims to learn the full representation of target
unitary operator $U$ through training a hypothesis unitary
$V_{\mathcal{S}_{Q}}$ on the training data

$\mathcal{S}_{Q}=\left\\{(\ket{\psi_{j}},\ket{\phi_{j}}):\ket{\psi_{j}},\ket{\phi_{j}}=(U\otimes\mathbb{I}_{d})\ket{\psi_{j}}\in\mathcal{H}_{\mathcal{X},\mathcal{R}}\right\\}_{j=1}^{N}.$
(23)

In this regard, they adopt the averaged error in the trace norm of the output
quantum states rather than the distance of classical measurement outputs
$R_{U}(V_{\mathcal{S}_{Q}})$ between the learned hypothesis and the target
hypothesis as the risk function $\widetilde{R}_{U}(V_{\mathcal{S}_{Q}})$ to
quantify the accuracy of the hypothesis $V_{\mathcal{S}_{Q}}$. Formally, the
risk function is defined as

$\displaystyle\widetilde{R}_{U}(V_{\mathcal{S}_{Q}}):=$
$\displaystyle\int_{\phi\sim\operatorname{Haar}}\mathrm{d}\phi\frac{1}{4}\left\|U\ket{\phi}\bra{\phi}U^{\dagger}-V_{\mathcal{S}_{Q}}\ket{\phi}\bra{\phi}V_{\mathcal{S}_{Q}}^{\dagger}\right\|_{1}^{2}$
$\displaystyle=$ $\displaystyle
1-\frac{d+|\operatorname{Tr}(U^{\dagger}V_{\mathcal{S}_{Q}})|^{2}}{d(d+1)},$
(24)

where $\ket{\phi}\in\mathcal{H}_{\mathcal{X}}$ and the second equality follows
directly Haar integration calculation. They showed that under the assumption
of perfect training on the output states with the infinite measurements, i.e.,
$(U\otimes\mathbb{I}_{d})\ket{\psi_{j}}=(V_{\mathcal{S}_{Q}}\otimes\mathbb{I}_{d})\ket{\psi_{j}}$
for $j\in[N]$, then the unitary operators $U^{\dagger}V_{\mathcal{S}_{Q}}$ can
be reduced to the form of

$U^{\dagger}V_{\mathcal{S}_{Q}}=\left(\begin{array}[]{cc}\mathbb{I}_{N\cdot
r}&0\\\ 0&\mathrm{Y}\end{array}\right)$ (25)

where $Y\in\mathbb{S}\mathbb{U}(d-Nr)$ follows Haar distribution when the
target unitary is Haar distributed. This leads to their main results as shown
in the following theorem.

######  Theorem 2 (Formulated theorem according to the results of
sharma2022reformulation ).

Let $U$ and $V_{\mathcal{S}_{Q}}$ be the target unitary sampled from Haar
distribution and the learned hypothesis unitary on the entangled data
$\mathcal{S}_{Q}$, such that the assumption of perfect training on the output
states holds. the averaged risk function defined in Eqn. (B.1) over all target
unitaries and training data yields

$\mathbb{E}_{U}\mathbb{E}_{\mathcal{S}_{Q}}\widetilde{R}_{U}(V_{\mathcal{S}_{Q}})\geq
1-\frac{d+r^{2}N^{2}}{d(d+1)}.$ (26)

It implies that the entangled data can remove the exponential cost of training
data size in learning unitaries. Specifically, in the extreme cases of $r=d$
and $r=1$, the required training data size for reaching the zero risk of the
former achieves an exponential advantage over that of the latter.

###  B.2 Quantum NFL theorem for learning quantum dynamics in the realistic
scenario

Let us first recall the required notations for the learning problems of
quantum NFL theorem. Let $U\in\mathbb{S}\mathbb{U}(d)$ denote the target
unitary and $O=\ket{o}\bra{o}$ be the fixed projective measurement which acts
on the quantum system $\mathcal{X}$. Denote $\mathcal{S}$ as the training data
with the size $|\mathcal{S}|=N$. The entanglement-assisted protocol introduces
a reference system $\mathcal{R}$ to prepare the entangled training states in
the Hilbert space
$\mathcal{H}_{\mathcal{X}\mathcal{R}}:=\mathcal{H}_{\mathcal{X}}\otimes\mathcal{H}_{\mathcal{R}}$
with $\dim(\mathcal{H}_{\mathcal{R}})=d$. The $m$-measurement outcomes
$(\bm{o}_{j1},\cdots,\bm{o}_{jm})$ of the observable $O$ on the output states
$(U\otimes\mathbb{I}_{d})\ket{\psi_{j}}$ are collected to construct the
response of the input $\ket{\psi}$ by taking the average value
$\bm{o}_{j}=\sum_{k=1}^{m}\bm{o}_{jk}/m$. This leads to the training data

$\mathcal{S}=\left\\{(\ket{\psi_{j}},\bm{o}_{j}):\ket{\psi_{j}}\in\mathcal{H}_{\mathcal{X}\mathcal{R}},\bm{o}_{j}=\frac{1}{m}\sum_{k=1}^{m}\bm{o}_{jk}\right\\}_{j=1}^{N},$
(27)

where $\bm{o}_{jk}$ is the $k$-th measurement outcome on the state
$(U\otimes\mathbb{I}_{d})\ket{\psi_{j}}$ and
$\mathbb{E}\bm{o}_{j}=\operatorname{Tr}[(U^{\dagger}OU\otimes\mathbb{I}_{d})\ket{\psi_{j}}\bra{\psi_{j}}]$.
From the Schmidt decomposition of a pure state, each $\ket{\psi_{j}}$ can be
represented as

$\ket{\psi_{j}}=\sum_{k=1}^{r}\sqrt{c_{j,k}}\ket{\xi_{j,k}}_{\mathcal{X}}\ket{\zeta_{j,k}}_{\mathcal{R}},$
(28)

where $\sum_{k=1}^{r}c_{j,k}=1$ and hence
$\ket{c_{j}}=(\sqrt{c_{j1}},\cdots,\sqrt{c_{jr}})^{\top}$ forms a state vector
in the Hilbert space $\mathcal{H}_{r}$. Suppose that all training states
$\ket{\psi_{j}}\in\mathcal{S}$ have the same Schmidt rank
$r\in\\{1,2,\cdots,d\\}$ across the cut
$\mathcal{H}_{\mathcal{X}}\otimes\mathcal{H}_{\mathcal{R}}$.

The problem of incoherent quantum dynamics learning aims to train a hypothesis
unitary $V_{\mathcal{S}}$ on the training data $\mathcal{S}$ such that it can
approximate the output of the target unitary $U$ under the observable $O$ for
given any unseen input state $\ket{\phi}\in\mathcal{H}_{d}$. In this regard,
we denote the target function and the learned hypothesis function with respect
to the input state $\ket{\psi}$ (or $\rho=\ket{\psi}\bra{\psi}$ in the density
matrix representation) as
$f_{U}(\psi)=\operatorname{Tr}(U^{\dagger}OU\ket{\psi}\bra{\psi})$ and
$h_{\mathcal{S}}(\psi)=\operatorname{Tr}(V_{\mathcal{S}}^{\dagger}OV_{\mathcal{S}}\ket{\psi}\bra{\psi})$,
respectively. Then to evaluate the quality of the learned unitary
$V_{\mathcal{S}}$, we define the risk function $R_{U}(V_{\mathcal{S}})$ as

$R_{U}(V_{\mathcal{S}})=\mathbb{E}_{\ket{\psi}\sim\operatorname{Haar}}\operatorname{Tr}\left(O\left(V_{\mathcal{S}}\ket{\psi}\bra{\psi}V_{\mathcal{S}}^{\dagger}-U\ket{\psi}\bra{\psi}U^{\dagger}\right)\right)^{2}.$
(29)

The standard quantum NFL theorem considers the averaged risk function over all
possible training data, target unitaries, and optimization algorithms from
which the learned hypothesis unitary has the same output as the target unitary
on the training input states, which has the form of
$\mathbb{E}_{\mathcal{S}}\mathbb{E}_{U}R_{U}(V_{\mathcal{S}})$. Particularly,
the uniform sampling of the target unitary in $\mathbb{S}\mathbb{U}(d)$
corresponds to the Haar distribution. While random pure states uniformly
sampled from the Hilbert space $\mathcal{H}_{\mathcal{X}\mathcal{R}}$ follow
Haar distribution, it can not be assumed that the states uniformly sampled
from the set of entangled states defined in Eqn. (28) follow Haar distribution
in $\mathbb{S}\mathbb{U}(d^{2})$ due to the restriction of fixed Schmidt
ranks. On the other hand, we observe that the uniform distribution of the
entangled training state $\ket{\psi_{j}}$ should satisfy the following
conditions: (i) the state vectors $\ket{\xi_{j}}$ and $\ket{\zeta_{j}}$ in the
subsystem $\mathcal{X}$ and $\mathcal{R}$ should be uniformly distributed in
the corresponding Hilbert space and are independent; (ii) the state vectors
$\ket{\xi_{j}}$ and $\ket{\xi_{k}}$ ($\ket{\zeta_{j}}$ and $\ket{\zeta_{k}}$)
in the subsystem $\mathcal{X}$ ($\mathcal{R}$) should be orthogonal for $j\neq
k$; (iii) the vector consisting of the coefficients $\ket{c_{j}}$ is also
uniformly distributed. We summarize these observations as the following
construction rules of the random entangled training states.

######  Construction Rule 1.

Each training entangled state $\ket{\psi_{j}}$ in the form of Eqn. (28) is
independently sampled by separately sampling the $r$ orthogonal Haar states
$\ket{\xi_{j1}},\cdots,\ket{\xi_{jr}}\in\mathbb{S}\mathbb{U}(d)$, $r$
orthogonal Haar states
$\ket{\zeta_{j1}},\cdots,\ket{\zeta_{jr}}\in\mathbb{S}\mathbb{U}(d)$ and the
Haar state $\ket{c_{j}}\in\mathbb{S}\mathbb{U}(r)$. The random variables
$\ket{\xi_{jk}}$, $\ket{\zeta_{jk^{\prime}}}$ and $\ket{c_{j}}$ are mutually
independent.

##  Appendix C Results of Theorem 1

In the realistic setting where the aim is to learn the target unitary under a
fixed observable $f_{U}(\rho)=\operatorname{Tr}(U^{\dagger}OU\rho)$ with a
limited number of measurements, the learned hypothesis
$h_{\mathcal{S}}(\rho)=\operatorname{Tr}(V_{\mathcal{S}}^{\dagger}OV_{\mathcal{S}}\rho)$
can not achieve zero training error on the training data $\mathcal{S}$ due to
the statistical error in measuring the quantum system. Consequently, the
assumption of perfect training, which is the pivotal condition in the proof of
the NFL theorem in previous literature poland2020no ; sharma2022reformulation
, is not applicable. With this regard, we adopt the information-theoretic
based technique, which does not rely on the perfect training assumption, to
prove the quantum NFL theorem when the number of measurements is finite. The
core idea is to “reduce” the learning problem to the multi-way hypothesis
testing problem. This is equivalent to showing that the risk error of the
quantum dynamics learning problem can be lower bounded by the probability of
error in testing problems, which can develop tools for. We then employ Fano’s
lemma to derive the information-theoretic bound for this hypothesis testing
problem.

The organization of this section is as follows. We first discretize the class
of target function through $2\varepsilon$-packing in SM C.1. We demystify in
SM C.2 how to reduce the learning problem to the hypothesis testing problem on
the $2\varepsilon$-packing with Fano’s inequality. In this regard, learning
the target unitary can be reduced to identifying the corresponding index $X$
in the $2\varepsilon$-packing. Then, we elucidate how to obtain the results of
Theorem 1 by separately bounding the related terms in the Fano’s inequality,
namely, the mutual information $I(X;\hat{X})$ between the target index $X$ and
the estimated index $\hat{X}$, and the cardinality of the
$2\varepsilon$-packing. The theoretical proof of Theorem 1 is given in SM C.3.
We provide the theoretical guarantee of the reduction from the learning
problem to the hypothesis testing problem in SM C.4. SM C.5 and SM C.6 present
the theoretical proofs for bounding the cardinality of the
$2\varepsilon$-packing and bounding the mutual information $I(X,\hat{X})$,
respectively. Finally, in SM C.7 we elucidate the tightness of the derived
lower bound through establishing the connection to the results of quantum
state tomography.

###  C.1 Discretizing the class of target functions through
$2\varepsilon$-packing

In the quantum dynamics learning problem under a fixed observable $O$
described in SM B.2, the goal is to identify the target function
$f_{U}(\rho)=\operatorname{Tr}(U^{\dagger}OU\rho)$ from the hypothesis set
$\mathcal{F}=\\{f_{U}(\rho)=\operatorname{Tr}(U^{\dagger}OU\rho)|U\in\mathbb{S}\mathbb{U}(d)\\}$
according to the measurement output $\bm{o}$. This task is hard when
$\mathcal{F}$ contains a large amount of very different operators. With this
regard, we discretize the set of target functions $\mathcal{F}$ by equipping
it with a local $\varepsilon$-packing, as shown in Fig. 3.

######  Definition 1 ($\varepsilon$-packing and local $\varepsilon$-packing).

For a given set of functionals $\mathcal{F}$ and a distance metric $\varrho$
on this set, the $\varepsilon$-packing
$\mathcal{M}_{\varepsilon}(\mathcal{F},\varrho)$ is a discrete subset of
$\mathcal{F}$ whose elements are guaranteed to be distant from each other by a
distance greater than or equal $2\varepsilon$. Namely, for any element
$f_{1},f_{2}\in\mathcal{M}_{\varepsilon}(\mathcal{F},\varrho)$, the distance
between $f_{1}$ and $f_{2}$ satisfies

$\varrho(f_{1},f_{2})\geq 2\varepsilon.$ (30)

Similarly, the local $\varepsilon$-packing
$\mathcal{M}_{\varepsilon}^{(\gamma\varepsilon)}(\mathcal{F},\varrho)$ is a
discrete subset of $\mathcal{F}$ such that for any element
$f_{1},f_{2}\in\mathcal{M}_{\varepsilon}^{(\gamma\varepsilon)}(\mathcal{F},\varrho)$,
the distance between $f_{1}$ and $f_{2}$ satisfies

$\gamma\varepsilon\geq\varrho(f_{1},f_{2})\geq 2\varepsilon,$ (31)

where $\gamma\geq 2$.

Figure 3: The $\varepsilon$-packing of the hypothesis space. The left panel
and the right panel refer to the $\varepsilon$-packing and the local
$\varepsilon$-packing with maximal distance $\gamma\varepsilon$ of
$\mathcal{F}$, respectively.

For a sufficient large $\gamma$ obeying
$\gamma\varepsilon\geq\max_{f_{1},f_{2}\in\mathcal{F}}\varrho(f_{1},f_{2})$,
the local $\varepsilon$-packing reduces to $\varepsilon$-packing. In this
work, we adopt the local $\varepsilon$-packing instead of the
$\varepsilon$-packing to obtain a tighter bound. This is because the learned
hypothesis $h_{\mathcal{S}}$ only needs to approximate
$f_{U}(\rho)=\operatorname{Tr}(U^{\dagger}OU\rho)$ on the training input
states $\\{\rho_{j}\\}_{j=1}^{N}$ up to a small training error, which can be
viewed as the relaxation of the perfect training assumption in the ideal
setting. In particular, a small bounded training error can restrict the
possible space in which the target unitary resides to the vicinity of the
learned hypothesis. Consequently, the local $\varepsilon$-packing suffices to
discretize the hypothesis set $\mathcal{F}$ in this context.

The packing cardinality
$|\mathcal{M}_{\varepsilon}^{(\gamma\varepsilon)}(\mathcal{F},\varrho)|$
heavily depends on the choice of the distance metric $\varrho$, which is
generally determined by the employed risk function. The following lemma gives
the analytical expression of the metric $\varrho$ for the risk function
defined in Eqn. (29).

######  Lemma 6 (Reformulation of the risk function).

For any given projective measurement $O=\ket{o}\bra{o}$ and any fixed random
Haar state $\rho$, the risk function defined in Eqn. (29) has the following
equivalent expression

$R_{U}(V_{\mathcal{S}})=\Phi\left(\varrho(h_{\mathcal{S}},f_{U})\right),$ (32)

where $f_{U}(\rho)=\operatorname{Tr}(U^{\dagger}OU\rho)$,
$h_{\mathcal{S}}(\rho)=\operatorname{Tr}(V_{\mathcal{S}}^{\dagger}OV_{\mathcal{S}}\rho)$,
$\Phi(t)=t^{2}$, and

$\varrho(h_{\mathcal{S}},f_{U})=\frac{1}{\sqrt{2d(d+1)}}\|U^{\dagger}OU-
V_{\mathcal{S}}^{\dagger}OV_{\mathcal{S}}\|_{1}.$ (33)

###### Proof of Lemma 6.

We recall that the risk function given in Eqn. (1) refers to

$R_{U}(V_{\mathcal{S}})=\mathbb{E}_{\ket{\phi}\sim\operatorname{Haar}}\operatorname{Tr}\left(O\left(V_{\mathcal{S}}\ket{\phi}\bra{\phi}V_{\mathcal{S}}^{\dagger}-U\ket{\phi}\bra{\phi}U^{\dagger}\right)\right)^{2}.$
(34)

Denote $G:=U^{\dagger}OU-V_{\mathcal{S}}^{\dagger}OV_{\mathcal{S}}$, we have

$\displaystyle R_{U}(V_{\mathcal{S}})$
$\displaystyle=\mathbb{E}_{\ket{\phi}\sim\operatorname{Haar}}\operatorname{Tr}\left(G\ket{\phi}\bra{\phi}\right)^{2}$
$\displaystyle=\operatorname{Tr}\left(G^{\otimes
2}\mathbb{E}_{\ket{\phi}\sim\operatorname{Haar}}\ket{\phi}\bra{\phi}^{\otimes
2}\right)$ $\displaystyle=\frac{1}{d(d+1)}\operatorname{Tr}\left(G^{\otimes
2}(\mathbb{I}^{\otimes 2}+\operatorname{SWAP})\right)$
$\displaystyle=\frac{1}{d(d+1)}\left(\operatorname{Tr}(G)^{2}+\operatorname{Tr}(G^{2})\right)$
$\displaystyle=\frac{1}{d(d+1)}\left(2\operatorname{Tr}(O^{2})-2\operatorname{Tr}(U^{\dagger}OUV_{\mathcal{S}}^{\dagger}OV_{\mathcal{S}})\right),$
(35)

where the second equality employs
$\operatorname{Tr}(A)^{2}=\operatorname{Tr}(A\otimes A)$, the third equality
exploits Lemma 4, and the $\operatorname{SWAP}$ is the swap operator on the
space $\mathcal{H}_{d}^{\otimes 2}$. When the observable $O$ takes the
projective measurement $\ket{o}\bra{o}$, the operators $U^{\dagger}OU$ and
$V_{\mathcal{S}}^{\dagger}OV_{\mathcal{S}}$ can be treated as density matrix
of the quantum state that we denote as $\ket{\mu}\bra{\mu}$ and
$\ket{\nu}\bra{\nu}$ with $\ket{\mu}=U\ket{o}$ and $\ket{\nu}=V\ket{o}$
respectively. With this observation, we can rewrite the risk function as

$\displaystyle R_{U}(V_{\mathcal{S}})$
$\displaystyle=\frac{1}{d(d+1)}\left(2\operatorname{Tr}(\ket{o}\bra{o}^{2})-2\braket{\mu}{\nu}^{2}\right)$
(36) $\displaystyle=\frac{2}{d(d+1)}\left(1-\braket{\mu}{\nu}^{2}\right)$
$\displaystyle=\frac{1}{2d(d+1)}\left\|U^{\dagger}OU-
V_{\mathcal{S}}^{\dagger}OV_{\mathcal{S}}\right\|_{1}^{2}.$

where the first equality comes from substituting the density matrix
representation of operators
$O,U^{\dagger}OU,V_{\mathcal{S}}^{\dagger}OV_{\mathcal{S}}$ into Eqn. (35),
the second equality is based on the fact $\operatorname{Tr}(\rho^{2})=1$ for
any pure state $\rho$, the third equality employs the relation between trace
distance and fidelity that
$1-\braket{u}{v}^{2}=\|\ket{u}\bra{u}-\ket{v}\bra{v}\|_{1}^{2}/4$. Eqn. (32)
can be directly obtained by denoting $\Phi(t)=t^{2}$, and
$\varrho(h_{\mathcal{S}},f_{U})=\|U^{\dagger}OU-
V_{\mathcal{S}}^{\dagger}OV_{\mathcal{S}}\|_{1}/\sqrt{2d(d+1)}$. ∎

The definition of $\varrho$ in Eqn. (33) satisfies the properties of the
distance metric, i.e., (1) non-negativity: $\varrho(f_{V},f_{U})\geq 0$, (2)
identity of indiscernible: $\varrho(f_{V},f_{U})\geq 0$ iff
$h_{\mathcal{S}}=f_{U}$, (3) symmetry:
$\varrho(f_{V},f_{U})=\varrho(f_{U},f_{V})$, (4) triangle inequality:
$\varrho(f_{V},f_{U})\leq\varrho(f_{U},f_{W})+\varrho(f_{V},f_{W})$. With this
well-defined distance metric $\varrho$ on the space $\mathcal{F}$, the local
$2\varepsilon$-packing is denoted as
$\mathcal{M}_{2\varepsilon}^{(\gamma\varepsilon)}$ with dropping the
dependence on $\mathcal{F}$ and $\varrho$ for simplification. Without loss of
generality, we employ the positive integer set
$\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}=[|\mathcal{M}_{2\varepsilon}^{(2\gamma\varepsilon)}|]$
to index the elements in the local $2\varepsilon$-packing, i.e.,
$\mathcal{M}_{2\varepsilon}^{(2\gamma\varepsilon)}=\\{f_{U_{x}}\\}_{x\in\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}}$,
where each index $x$ in $\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}$
uniquely corresponds to an element $f_{U_{x}}$ in the local packing
$\mathcal{M}_{2\varepsilon}^{(2\gamma\varepsilon)}$. In the following, we
refer the index set $\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}$ to the
local $2\varepsilon$-packing.

###  C.2 Reducing the learning problem to hypothesis testing

We now elucidate how to reduce the quantum dynamics learning problem
introduced in SM B.2 to the hypothesis testing problem by exploiting Fano’s
method, which is extensively used in deriving the lower bound of the
generalization error in statistical learning theory duchi2016lecture . Assume
that the target function is in the discrete local $2\varepsilon$-packing
$\\{f_{U_{x}}\\}_{x\in\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}}$,
then the learning problem aims to identify the underlying index $x$ from
$\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}$ according to the training
data $\mathcal{S}$, which is exactly described by the hypothesis testing.
Particularly, given the set of training input states
$\\{\rho_{j}\\}_{j=1}^{N}$, we refer the hypothesis testing to any measurable
mapping
$\Psi_{\rho_{1},\cdots,\rho_{N}}:\bm{o}\to\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}$.
The learning problem can be reduced to the following hypothesis testing
problem as shown in Fig. 4:

  * •

first, nature chooses $X=x$ according to the uniform distribution over
$\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}$ and the target function is
denoted as $f_{U_{x}}$ with $U_{x}$ being the unitary operator in
$\\{U_{x^{\prime}}\\}_{x^{\prime}\in\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}}$;

  * •

second, conditioned on the choice $X=x$, and given the Haar random input
states set $\\{\rho_{j}=\ket{\psi_{j}}\bra{\psi_{j}}\\}_{j=1}^{N}$, the
measurement outcome is drawn from distribution
$\mathbb{P}_{\bm{o}|x}=\prod_{j=1}^{N}\mathbb{P}_{\bm{o}|x}^{(j)}$, where
$\mathbb{P}_{\bm{o}|x}^{(j)}$ characterized the distribution of
$\bm{o}_{j}=\sum_{k=1}^{m}\bm{o}_{jk}/m$ conditional on $X=x$. The set of
input states $\\{\rho_{j}\\}_{j=1}^{N}$ and the measurement outcomes
$\\{\bm{o}_{j}\\}_{j=1}^{N}$ together form the training data
$\mathcal{S}=\\{(\rho_{j},\bm{o}_{j})\\}_{j=1}^{N}$;

  * •

third, the learning model performs the following optimization to minimize the
empirical training error

$h_{\mathcal{S}}=\mathop{\arg\min}\limits_{h\in\\{f_{U_{x^{\prime}}}|x^{\prime}\in\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}\\}}\frac{1}{N}\sum_{j=1}^{N}\left(h(\rho_{j})-\bm{o}_{j}\right)^{2};$
(37)

  * •

fourth, the hypothesis testing
$\Psi_{\rho_{1},\cdots,\rho_{N}}(\bm{o}):=\arg\min_{\tilde{x}\in\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}}\varrho(h_{\mathcal{S}},f_{U_{\tilde{x}}})$
is conducted to determine the randomly chosen index $X$. The associated error
probability of the hypothesis testing problem is denoted by
$\mathbb{P}_{\bm{o},X}(\Psi_{\rho_{1},\cdots,\rho_{N}}(\bm{o})\neq X)$.

Figure 4: The paradigm of the reduction from quantum dynamics learning to
hypothesis testing.

The choice of the uniform distribution over
$\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}$ in the first step is
because in the context of the quantum NFL theorem the target unitary is
assumed to be sampled from the Haar distribution. The distribution
$\mathbb{P}_{\bm{o}|x}^{(j)}$ of the measurement outcome $\bm{o}_{jk}$ in the
second step is assumed to be a Gaussian distribution whose mean
$u_{x}=\operatorname{Tr}((U_{x}^{\dagger}OU_{x}\otimes\mathbb{I}_{\mathcal{R}})\rho_{j})$
varies with the index $x$ and the input state $\rho_{j}$, and the variance
$\sigma^{2}$ is assumed to be an $n$-dependent constant which is identified
below (see Assumption 1). This learning algorithm in the third step is
arbitrary, as long as the learned function can achieve the minimal training
error (i.e., can be greater than $0$), which can be regarded as the relaxation
of the perfect training assumption with zero training error. In the fourth
step, the notation $\mathbb{P}_{\bm{o},X}$ denotes the joint distribution over
the random index $X$ and $\bm{o}$. In particular, define
$\bar{\mathbb{P}}_{\bm{o}}=\sum_{x\in\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}}\mathbb{P}_{\bm{o}|x}/|\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}|$
as the mixture distribution, the measurement output is drawn (marginally) from
$\bar{\mathbb{P}}_{\bm{o}}$, and our hypothesis testing problem is to
determine the randomly chosen index $X$ given the training data
$\mathcal{S}=\\{(\rho_{j},\bm{o}_{j})\\}_{j=1}^{N}$ with
$\bm{o}=(\bm{o}_{1},\cdots,\bm{o}_{N})$ sampled from this mixture
$\bar{\mathbb{P}}_{\bm{o}}$. Denote the average risk function over the
training sets $\mathcal{S}$ and target unitary $U$ as

$\mathbb{E}_{U}\mathbb{E}_{\mathcal{S}}R_{U}(V_{\mathcal{S}})=R_{N}(\Phi\odot\varrho):=\mathbb{E}_{U}\mathbb{E}_{\mathcal{S}}\Phi\left(\varrho(h_{\mathcal{S}},f_{U})\right),$
(38)

where the second equality follows Lemma 6. Notably, the randomness of
$\mathcal{S}$ comes from the randomness of the input states set
$\\{\rho_{j}\\}_{j=1}^{N}$ and the randomness of measurement outcomes
$\bm{o}_{j}$. For simplifying the calculation of Haar integration, we make the
following mild assumption on the distribution of the measurement output
$\bm{o}_{j}=\sum_{k=1}^{m}\bm{o}_{jk}/m$.

######  Assumption 1.

For any index $X=x$, the outcome $\bm{o}_{j}=\sum_{k=1}^{m}\bm{o}_{jk}/m$ of
the projective measurements $O=\ket{o}\bra{o}$ on the given output state
$(U_{X}\otimes\mathbb{I}_{\mathcal{R}})\ket{\psi_{j}}$ follows the binomial
distribution $\mathbb{B}(m,u_{x}^{(j)})$ with
$u_{x}=\mathbb{E}[\bm{o}_{j}]=\operatorname{Tr}((U_{x}^{\dagger}OU_{x}\otimes\mathbb{I}_{\mathcal{R}})\ket{\psi_{j}}\bra{\psi_{j}})$.
According to the central limit theorem, the binomial distribution is
approximated by the normal distribution
$\mathbb{N}(u_{x},(\sigma_{x}^{(j)})^{2})$ with the mean
$u_{x}=\operatorname{Tr}((U_{x}^{\dagger}OU_{x}\otimes\mathbb{I}_{\mathcal{R}})\ket{\psi_{j}}\bra{\psi_{j}})$
and the variance $(\sigma_{x}^{(j)})^{2}=u_{x}(1-u_{x})/m$. Furthermore, the
variance is assumed to take the expectation of $(\sigma_{x}^{(j)})^{2}$ over
the random input state $\ket{\psi_{j}}$, i.e.,
$\sigma^{2}=\mathbb{E}_{\ket{\psi_{j}}\sim\operatorname{Haar}}(\sigma_{x}^{(j)})^{2}$.

Remark. We note that Assumption 1 is mild, as the convergence of binomial
distribution to the normal distribution is guaranteed by the central limit
theorem for a large number of measurements loeve2017probability .
Additionally, the approximate proxy of the variance $\sigma_{x}^{2}$ with its
expectation $\sigma^{2}$ is based on the observation that the variance
$\sigma_{x}^{2}$ is smaller than the expectation of $u_{x}$ with at least a
multiplier factor of $1/m$ and is exponentially concentrated in the number of
qubits $n$ which is widely studied in barren plateaus of variation quantum
algorithms mcclean2018barren ; cerezo2021cost ; zhang2021toward . These
observations enable the effective discrimination of the normal distribution of
the measurement outputs corresponding to the different hypothesis unitaries in
the local $2\varepsilon$-packing.

With this setup, the following lemma whose proof is deferred to SM C.4 gives a
theoretical guarantee of the reduction from the quantum dynamics learning
problem to the hypothesis testing problem.

######  Lemma 7.

Given the local $2\varepsilon$-packing
$\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}$ of the functional class
$\mathcal{F}$, the average risk error in Eqn. (38) is lower bounded by

$R_{N}(\Phi\odot\varrho)\geq\mathbb{E}_{\rho_{1},\cdots,\rho_{N}}\Phi(\varepsilon)\mathbb{P}_{\bm{o},X}(\Psi_{\rho_{1},\cdots,\rho_{N}}(\bm{o})\neq
X),$ (39)

where the probability measure $\mathbb{P}$ refers to the joint distribution of
the random index $X$ and the measurement output $\bm{o}$.

Lemma 7 reduces the problem of lower bounding the risk function
$R_{N}(\Phi\odot\varrho)$ to the problem of lower bounding the error of
hypothesis testing. The Fano’s inequality gives an information-theoretical
bound to the latter.

######  Lemma 8 (Fano’s inequality).

Assume that $X$ is uniform in
$\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}$. The learning procedure
can be depicted by the Markov chain $X\to\mathcal{S}\to\hat{X}$, where
$\hat{X}$ is returned by the hypothesis testing, i.e.,
$\Phi_{\rho_{1},\cdots,\rho_{N}}(\bm{o})=\hat{X}$. Then we have

$\mathbb{P}_{\bm{o},X}(\Psi_{\rho_{1},\cdots,\rho_{N}}(\bm{o})\neq X)\geq
1-\frac{I(X;\hat{X})+\log
2}{\log(|\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}|)},$ (40)

where $I(X;\hat{X})$ refers to the mutual information between the estimated
index $\hat{X}$ and $X$.

The information-theoretic lower bound for the risk function defined in Eqn.
(38) can be achieved by using Fano’s method for multiple hypothesis testing
established in Lemma 7 and Lemma 8. Moreover, it is reduced to separately
bound the mutual information $I(X;\hat{X})$ and the local
$2\varepsilon$-packing cardinality
$|\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}|$, which are given by the
following two lemmas.

######  Lemma 9 (Lower bound of local $2\varepsilon$-packing cardinality for
the output under the projective measurement).

Let $O=\ket{o}\bra{o}$ be the projective measurement,
$\mathcal{F}=\\{f_{U}:\rho\to\operatorname{Tr}(U^{\dagger}OU\rho)|U\in\mathbb{S}\mathbb{U}(d)\\}$
be the function class of the output of quantum system given an arbitrary fixed
Haar state $\rho$, and
$\varrho(f_{U_{1}},f_{U_{2}})=\sqrt{\mathbb{E}_{\rho\sim
Haar}\operatorname{Tr}\left(O\left(U_{1}\rho U_{1}^{\dagger}-U_{2}\rho
U_{2}^{\dagger}\right)\right)^{2}}$ be the distance measure. Then there exist
a local $2\varepsilon$-packing
$\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}$ with
$\varepsilon=\mathcal{O}(1/d)$ in the $\varrho$-metric such that the packing
cardinality yields

$\left|\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}\right|\geq\exp\left(\frac{d\min\\{(1-2\tilde{\varepsilon})^{2},(4\gamma^{2}\tilde{\varepsilon}^{2}-1)^{2}\\}}{16}\right),$
(41)

where $\tilde{\varepsilon}=2\sqrt{2d(d+1)}\varepsilon$ and $\gamma$ refers to
an arbitrary constant obeying $0<4\gamma^{2}\tilde{\varepsilon}^{2}-1<1$ and
$\gamma>2$.

######  Lemma 10 (Upper bound of the mutual information $I(X,\hat{X})$).

Following the notations in Lemma 9 and Assumption 1, the average of mutual
information over the training states $\\{\rho_{j}\\}_{j=1}^{N}$ sampled from
the distribution described in Construction Rule 1 yields

$\mathbb{E}_{\rho_{1},\cdots,\rho_{N}}I(X;\hat{X})\leq
N\cdot\min\left\\{\frac{4md\gamma^{2}\varepsilon^{2}}{r},r\log\left(d\right)\right\\},$
(42)

where $\gamma$ refers to an arbitrary constant obeying
$0<4\gamma^{2}\tilde{\varepsilon}^{2}-1<1$ with
$\tilde{\varepsilon}=2\sqrt{2d(d+1)}{\varepsilon}$ and $\gamma>2$.

Hence, learning quantum dynamics in the framework of the quantum NFL theorem
taking consideration of the entangled quantum state and the finite
measurements is encapsulated in the following theorem.

######  Theorem (Formal statement of Theorem 1).

Let $\\{f_{U_{x}}\\}_{x\in\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}}$
be a local $2\varepsilon$-packing with the maximal distance being
$\gamma\varepsilon$ of the function class $\mathcal{F}$ in the
$\varrho$-metric. Assume that the index $X$ corresponding to the target
function $f_{U_{X}}$ is uniformly sampled from the set
$\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}$. Conditional on $X=x$, we
obtain the training set $\mathcal{S}=\\{\rho_{j},\bm{o}_{j}\\}_{j=1}^{N}$
where $\rho_{j}$ is the random entangled state of Schmidt rank $r$ sampled
from the distribution described in Construction Rule 1, and
$\bm{o}_{j}=\sum_{k=1}^{m}\bm{o}_{jk}/m$ is the measurement output of the
observable $O$ following Assumption 1. Then the averaged risk function defined
in Eqn. (38) is lower bounded by

$\mathbb{E}_{U}\mathbb{E}_{\mathcal{S}}R_{U}(V_{\mathcal{S}})\geq\frac{\tilde{\varepsilon}^{2}}{8d(d+1)}\left(1-\frac{N\cdot\min\\{128m\tilde{\varepsilon}^{2}/r(d+1),r\log(d))\\}+16\log
2}{d\min\\{(1-2\tilde{\varepsilon})^{2},(64\tilde{\varepsilon}^{2}-1)^{2}\\}}\right),$
(43)

where $\tilde{\varepsilon}=2\sqrt{2d(d+1)}{\varepsilon}$ and the expectation
is taken over all target unitaries $U$.

###  C.3 Proof of Theorem 1

We are now ready to prove Theorem 1.

###### Proof of Theorem 1.

Combining Lemma 8 with the reduction from learning to testing in Lemma 7, we
have

$\displaystyle\mathbb{E}_{U}\mathbb{E}_{\mathcal{S}}R_{U}(V_{\mathcal{S}})=$
$\displaystyle R_{N}(\Phi\odot\varrho)$ $\displaystyle\geq$
$\displaystyle\mathbb{E}_{\rho_{1},\cdots,\rho_{N}}\Phi(\varepsilon)\mathbb{P}(\Psi_{\rho_{1},\cdots,\rho_{N}}(\bm{o})\neq
X)$ $\displaystyle\geq$
$\displaystyle\varepsilon^{2}\cdot\left(1-\frac{\mathbb{E}_{\rho_{1},\cdots,\rho_{N}}I(X,\hat{X})+\log
2}{\log(|\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}|)}\right).$ (44)

Let $\gamma=4$ and $\varepsilon=\tilde{\varepsilon}/(2\sqrt{2d(d+1)})$ with
$\tilde{\varepsilon}$ taking any number satisfying
$\gamma\tilde{\varepsilon}\in(1/2,\sqrt{2}/2)$ such that
$0<4\gamma^{2}\tilde{\varepsilon}^{2}-1<1$. Employing the results of Lemma 9
and Lemma 10, we have

$\displaystyle R_{N}(\Phi\odot\varrho)$
$\displaystyle\geq\varepsilon^{2}\left(1-\frac{N\cdot\min\\{4md\gamma^{2}\varepsilon^{2}/r,r\log(d)\\}+\log
2}{d\min\\{(1-2\tilde{\varepsilon})^{2},(4\gamma^{2}\tilde{\varepsilon}^{2}-1)^{2}\\}/16}\right)$
$\displaystyle\geq\frac{\tilde{\varepsilon}^{2}}{8d(d+1)}\left(1-\frac{N\cdot\min\\{8md\tilde{\varepsilon}^{2}/rd(d+1),r\log(d)\\}+\log
2}{d\min\\{(1-2\tilde{\varepsilon})^{2},(64\tilde{\varepsilon}^{2}-1)^{2}\\}/16}\right)$
$\displaystyle=\frac{\tilde{\varepsilon}^{2}}{8d(d+1)}\left(1-\frac{N\cdot\min\\{128m\tilde{\varepsilon}^{2}/r(d+1),16r\log(d)\\}+16\log
2}{d\min\\{(1-2\tilde{\varepsilon})^{2},(64\tilde{\varepsilon}^{2}-1)^{2}\\}}\right).$
(45)

where the first inequality employs Lemma 9 that
$\log(|\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}|)\geq
d\min\\{(1-2\tilde{\varepsilon})^{2},(4\gamma^{2}\tilde{\varepsilon}^{2}-1)^{2}\\}/16$.
This completes the proof. ∎

###  C.4 Proof of Lemma 7-reducing the learning problem to hypothesis testing

###### Proof of Lemma 7.

To see this result, we first recall that the averaged risk given in Eqn. (38)
has the form

$R_{N}(\Phi\odot\varrho)=\mathbb{E}_{U}\mathbb{E}_{\mathcal{S}}[\Phi(\varrho(h_{\mathcal{S}},f_{U}))],$

where $\Phi(t)=t^{2}$, $\varrho$ is the distance metric on the functionals set
$\mathcal{F}$ with the definition given in Eqn. (33), and $h_{\mathcal{S}}$
refers to an arbitrary learned hypothesis on the training data $\mathcal{S}$.
Denote $\Theta$ as the value space of $\bm{o}$ and $\mathbb{P}_{\bm{o}}$ as
the cumulative distribution function (CDF) of $\bm{o}$. Decomposing the
integration with respect to $\mathcal{S}$ into that with respect to
$\\{\rho_{j}\\}_{j=1}^{N}$ and $\bm{o}$ yields

$\displaystyle R_{N}(\Phi\odot\varrho)=$
$\displaystyle\mathbb{E}_{U}\mathbb{E}_{\rho_{1},\cdots,\rho_{N}}\mathbb{E}_{\bm{o}}[\Phi(\varrho(h_{\mathcal{S}},f_{U}))]$
$\displaystyle=$
$\displaystyle\mathbb{E}_{U}\mathbb{E}_{\rho_{1},\cdots,\rho_{N}}\int_{\Theta}\Phi(\varrho(h_{\mathcal{S}},f_{U}))\mathrm{d}\mathbb{P}_{\bm{o}}$
$\displaystyle=$
$\displaystyle\mathbb{E}_{U}\mathbb{E}_{\rho_{1},\cdots,\rho_{N}}\int_{\\{\bm{o}:\varrho(h_{\mathcal{S}},f_{U})\geq
0\\}}\Phi(\varrho(h_{\mathcal{S}},f_{U}))\mathrm{d}\mathbb{P}_{\bm{o}}$
$\displaystyle\geq$
$\displaystyle\mathbb{E}_{U}\mathbb{E}_{\rho_{1},\cdots,\rho_{N}}\int_{\\{\bm{o}:\varrho(h_{\mathcal{S}},f_{U})\geq\varepsilon\\}}\Phi(\varepsilon)\mathrm{d}\mathbb{P}_{\bm{o}}$
$\displaystyle=$
$\displaystyle\mathbb{E}_{U}\mathbb{E}_{\rho_{1},\cdots,\rho_{N}}\Phi(\varepsilon)\mathbb{P}_{\bm{o}}(\varrho(h_{\mathcal{S}},f_{U})\geq\varepsilon),$
$\displaystyle=$
$\displaystyle\mathbb{E}_{\rho_{1},\cdots,\rho_{N}}\frac{1}{|\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}|}\sum_{x\in\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}}\Phi(\varepsilon)\mathbb{P}_{\bm{o}}(\varrho(h_{\mathcal{S}},f_{U_{X}})\geq\varepsilon|X=x),$
(46)

where the first equality follows that the randomness of $\mathcal{S}$ comes
from $\\{\rho_{j}\\}_{j=1}^{N}$ and $\bm{o}$, the second equality employs the
integral representation with respect to $\bm{o}$ over the integration area
$\Theta$, the third equality follows that the inequality
$\varrho(h_{\mathcal{S}},f_{U})\geq 0$ holds for any $\bm{o}\in\Theta$ and
hence $\Theta=\\{\bm{o}:\varrho(h_{\mathcal{S}},f_{U})\geq 0\\}$ with
$h_{\mathcal{S}}$ being $\bm{o}$-dependent, the first inequality follows that
$\Phi$ is non-negative and non-decreasing in the integral region, the fourth
equality uses the independence of $\Phi(\varepsilon)$ on $\bm{o}$ and the
probability representation
$\int_{A}\mathrm{d}\mathbb{P}_{\bm{o}}=\mathbb{P}_{\bm{o}}(A)$ with
$A=\\{\bm{o}:\varrho(h_{\mathcal{S}},f_{U_{x}})\geq\varepsilon\\}$, the final
equality follows the equivalence of the expectation under the Haar
distribution on $\mathbb{S}\mathbb{U}(d)$ and the uniform distribution on the
packing.

To obtain Eqn. (39) with Eqn. (46), we now only need to prove the inequality

$\mathbb{P}_{\bm{o}}(\varrho(h_{\mathcal{S}},f_{U_{X}})\geq\varepsilon|X=x)\geq\mathbb{P}_{\bm{o}}(\Psi_{\rho_{1},\cdots,\rho_{N}}(\bm{o})\neq
X|X=x)$

for any index $x\in\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}$. Denote
two events $A=\\{\bm{o}:\varrho(h_{\mathcal{S}},f_{U_{x}})\geq\varepsilon\\}$
and $B=\\{\bm{o}:\Psi_{\rho_{1},\cdots,\rho_{N}}(\bm{o})\neq x\\}$, the
inequality can be achieved by proving $B\subset A$ or equivalently
$A^{C}\subset B^{C}$, where $A^{C},B^{C}$ denote the complement of $A$ and
$B$. Particularly, the inequality
$\mathbb{P}_{\bm{o}}(A)\geq\mathbb{P}_{\bm{o}}(B)$ holds if and only if
$B\subset A$ or equivalently $A^{C}\subset B^{C}$. In the following, we
complete this proof by proving the inclusion relationship of $A^{C}\subset
B^{C}$, i.e., $\varrho(h_{\mathcal{S}},f_{U_{x}})<\varepsilon$ implies that
$\Psi_{\rho_{1},\cdots,\rho_{N}}(\bm{o})=x$.

Assume that there exists an index $x$ such that
$\varrho(h_{\mathcal{S}},f_{U_{x}})<\varepsilon$, then for any $x^{\prime}\neq
x$ with $x^{\prime}\in\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}$, we
have

$\varrho(h_{\mathcal{S}},f_{U_{x^{\prime}}})\geq\varrho(f_{U_{x^{\prime}}},f_{U_{x}})-\varrho(h_{\mathcal{S}},f_{U_{x}})\geq\varepsilon\geq\varrho(h_{\mathcal{S}},f_{U_{x}})$
(47)

where the first inequality employs the triangle inequality, the second
inequality follows that $\varrho(f_{U_{x^{\prime}}},f_{U_{x}})\geq
2\varepsilon$ for any $x\neq
x^{\prime}\in\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}$, the last
inequality is based on the presupposition. This implies that
$x=\arg\min_{\tilde{x}\in\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}}\varrho(h_{\mathcal{S}},f_{U_{\tilde{x}}})$
and hence $\Psi_{\rho_{1},\cdots,\rho_{N}}(\bm{o})=x$ according to the
definition of $\Psi_{\rho_{1},\cdots,\rho_{N}}(\bm{o})$. ∎

###  C.5 Proof of Lemma 9—bounding the local $2\varepsilon$-packing
cardinality $|\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}|$

The idea of lower bounding the local packing cardinality of the metric space
$(\mathcal{F},\varrho)$ in Lemma 9 can be decomposed into two steps. First, we
derive a lower bound of the local packing cardinality of the space consisting
of $n$-qubit pure states $\mathcal{H}_{d}$. This proof is given by Lemma 11
and Lemma 12 in a probabilistic existence argument. Second, the local packing
cardinality of metric spaces $(\mathcal{F},\varrho)$ can be obtained by
building the connection between metric spaces
$(\mathcal{H}_{d},\|\cdot\|_{1})$ and $(\mathcal{F},\varrho)$.

In the probabilistic method for bounding the local $\varepsilon$-packing
cardinality, a sequence of independent and identically distributed (i.i.d)
unitary operators $W_{1},W_{2},\cdots$ are sampled from the Haar distribution
on $\mathbb{S}\mathbb{U}(d)$ to construct the $\varepsilon$-packing with the
states $\rho_{\varepsilon,W_{i}}=W_{i}\ket{\phi}\bra{\phi}W_{i}^{\dagger}$
where $\ket{\phi}\in\mathcal{H}_{d}$ is any fixed quantum state. We then apply
standard concentration of measure results to argue that the probability of
selecting an undesirable state set (i.e., there exist two states whose trace
distance is less than $2\varepsilon$ or larger than $\gamma\varepsilon$) is
exponentially small. This in turn implies that such states set is a local
$\varepsilon$-packing with the maximal distance being $\gamma\varepsilon$. To
this end, we first exploit the concentration of projector overlaps, which have
been used in deriving the lower bounds for quantum state tomography
haah2016sample ; aaronson2018shadow ; huang2021information ; lowe2022lower .

######  Lemma 11 (Lemma 3.2, lowe2022lower ).

Let $W\in\mathbb{S}\mathbb{U}(d)$ be a Haar-random unitary operator and let
$\Pi_{1},\Pi_{2}:\mathcal{H}_{d}\to\mathcal{H}_{d}$ be orthogonal projection
operators with the rank $r_{1},r_{2}$ respectively. For all $t\in(0,1)$ it
holds that

$\displaystyle\mathbb{P}_{W\sim\operatorname{Haar}}\left[\operatorname{Tr}(\Pi_{1}W\Pi_{2}W^{\dagger})\leq(1-t)\frac{r_{1}r_{2}}{d}\right]\leq\exp\left(-\frac{r_{1}r_{2}t^{2}}{2}\right),$
$\displaystyle\mbox{and}\leavevmode\nobreak\ \leavevmode\nobreak\
\mathbb{P}_{W\sim\operatorname{Haar}}\left[\operatorname{Tr}(\Pi_{1}W\Pi_{2}W^{\dagger})\geq(1+t)\frac{r_{1}r_{2}}{d}\right]\leq\exp\left(-\frac{r_{1}r_{2}t^{2}}{4}\right).$
(48)

With this lemma, we can derive the lower bound of the local
$\varepsilon$-packing cardinality of $n$-qubit pure states, which is
encapsulated in the following lemma.

######  Lemma 12 (Lower bound of packing cardinality for $n$-qubit quantum
states).

Under the distance metric of trace norm $\|\cdot\|_{1}$, there exists a local
$\varepsilon$-packing $\mathcal{P}_{\varepsilon}^{(\gamma\varepsilon)}$ of the
set of all $n$-qubit pure quantum states $\ket{\psi}$ where the distance
between arbitrary two elements in
$\mathcal{P}_{\varepsilon}^{(\gamma\varepsilon)}$ is less than
$\gamma\varepsilon$ satisfying

$\left|\mathcal{P}_{\varepsilon}^{(\gamma\varepsilon)}\right|\geq\exp\left(\frac{d\min\\{(1-\varepsilon)^{2},(4\gamma^{2}\varepsilon^{2}-1)^{2}\\}}{16}\right),$
(49)

where $\gamma$ refers to an arbitrary constant obeying
$0<4\gamma^{2}\varepsilon^{2}-1<1$ and $\gamma>2$.

###### Proof of Lemma 12.

We give a probabilistic existence argument of the lower bound of local
$\varepsilon$-packing cardinality. Particularly, we first construct a local
$\varepsilon$-packing in which the distance between arbitrary two elements is
less than $\gamma\varepsilon$ by applying a probabilistic method. Let
$\rho_{0}=\ket{\phi}\bra{\phi}$ be any fixed quantum state and
$\rho_{i}=W_{i}\rho_{0}W_{i}^{\dagger}$ for each $i\in[L]$ with
$W_{1},W_{2},\cdots,W_{L}\in\mathbb{S}\mathbb{U}(d)$ being arbitrary unitary
operators sampled from Haar distribution. In the following, with the aim of
showing the existence of such local $\varepsilon$-packing with the desired
lower bound, we will show the event that there exists $i\neq j\in[L]$ such
that the trace distance between $\rho_{i}$ and $\rho_{j}$ is less than
$2\varepsilon$ or larger than $\gamma\varepsilon$ occurs with a small
probability. Mathematically, the probability of this event has the form of

$\displaystyle\mathbb{P}_{W_{1},\cdots,W_{L}\sim\operatorname{Haar}}\left[\bigcup_{i=1}^{L}\bigcup_{j=i+1}^{L}\left\\{\|\rho_{i}-\rho_{j}\big{\|}_{1}\leq
2\varepsilon\right\\}\bigcup\left\\{\|\rho_{i}-\rho_{j}\big{\|}_{1}\geq\gamma\varepsilon\right\\}\right]$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{L}\sum_{j=i+1}^{L}\bigg{(}\mathbb{P}_{W_{i},W_{j}\sim\operatorname{Haar}}\left[\|\rho_{i}-\rho_{j}\big{\|}_{1}\leq
2\varepsilon\right]+\mathbb{P}_{W_{i},W_{j}\sim\operatorname{Haar}}\left[\|\rho_{i}-\rho_{j}\big{\|}_{1}\geq\gamma\varepsilon\right]\bigg{)}$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{L}\sum_{j=i+1}^{L}\bigg{(}\mathbb{P}_{W_{i},W_{j}\sim\operatorname{Haar}}\left[\big{\|}\rho_{W}-\rho_{\mathbb{I}}\big{\|}_{1}\leq
2\varepsilon\right]+\mathbb{P}_{W_{i},W_{j}\sim\operatorname{Haar}}\left[\big{\|}\rho_{W}-\rho_{\mathbb{I}}\big{\|}_{1}\geq\gamma\varepsilon\right]\bigg{)}$
$\displaystyle=$
$\displaystyle\frac{L(L+1)}{2}\bigg{(}\mathbb{P}_{W\sim\operatorname{Haar}}\left[\big{\|}\rho_{W}-\rho_{\mathbb{I}}\big{\|}_{1}\leq
2\varepsilon\right]+\mathbb{P}_{W\sim\operatorname{Haar}}\left[\big{\|}\rho_{W}-\rho_{\mathbb{I}}\big{\|}_{1}\geq\gamma\varepsilon\right]\bigg{)}$
(50)

where the first inequality employs the subadditivity of probability measure,
the first equality exploits the definition of
$\rho_{W}=W\ket{\phi}\bra{\phi}W^{\dagger}$ and the invariance of trace
distance under arbitrary unitary transformations, i.e.,

$\left\|\rho_{i}-\rho_{j}\right\|_{1}=\left\|W_{i}\rho_{0}W_{i}^{\dagger}-W_{j}\rho_{0}W_{j}^{\dagger}\right\|_{1}=\left\|W_{j}^{\dagger}(W_{i}\rho_{0}W_{i}^{\dagger}-W_{j}\rho_{0}W_{j}^{\dagger})W_{j}\right\|_{1}=\|\rho_{W}-\rho_{\mathbb{I}}\|_{1},$
(51)

where the last equality follows that the unitary operator
$W=W_{j}^{\dagger}W_{i}$ follows Haar distribution as
$W_{i},W_{j}\in\mathbb{S}\mathbb{U}(d)$ are sampled from Haar distribution.
Next, we separately consider the probability of the events in Eqn. (50) of
$\|\rho_{W}-\rho_{\mathbb{I}}\big{\|}_{1}\leq 2\varepsilon$ and
$\|\rho_{W}-\rho_{\mathbb{I}}\big{\|}_{1}\geq\gamma\varepsilon$ under the Haar
distribution. Particularly, we first note that with the definition
$\rho_{W}=W\ket{\phi}\bra{\phi}W^{\dagger}$ for any
$W\in\mathbb{S}\mathbb{U}(d)$, we have

$\displaystyle\big{\|}\rho_{W}-\rho_{\mathbb{I}}\big{\|}_{1}=$
$\displaystyle\big{\|}W\ket{\phi}\bra{\phi}W^{\dagger}-\ket{\phi}\bra{\phi}\big{\|}_{1}$
$\displaystyle\geq$
$\displaystyle\frac{1}{2}\big{\|}W\ket{\phi}\bra{\phi}W^{\dagger}-\ket{\phi}\bra{\phi}\big{\|}_{1}$
$\displaystyle\geq$
$\displaystyle\operatorname{Tr}\left(\left(\frac{W\ket{\phi}\bra{\phi}W^{\dagger}-\ket{\phi}\bra{\phi}}{2}\right)\left(\mathbb{I}_{d}-2\ket{\phi}\bra{\phi}\right)\right)$
$\displaystyle=$
$\displaystyle\operatorname{Tr}\left(\left(\mathbb{I}_{d}-\ket{\phi}\bra{\phi}\right)W\ket{\phi}\bra{\phi}W^{\dagger}\right)$
$\displaystyle=$
$\displaystyle\operatorname{Tr}\left(\Pi_{1}W\Pi_{2}W^{\dagger}\right),$ (52)

where the second inequality employs the property of trace norm that
$\|A\|_{1}=\max\\{|\operatorname{Tr}(AW)|:W\in\mathbb{U}(d)\\}$ for any square
operator $A$, and $\mathbb{I}_{d}-2\ket{\phi}\bra{\phi}\in\mathbb{U}(d)$, and
the last equality is obtained by denoting $\Pi_{2}=\ket{\phi}\bra{\phi}$ and
$\Pi_{1}=\mathbb{I}_{d}-\Pi_{2}$. This leads to the conclusion that

$\mathbb{P}_{W\sim\operatorname{Haar}}\left[\|\rho_{W}-\rho_{\mathbb{I}}\big{\|}_{1}\leq
2\varepsilon\right]\leq\mathbb{P}_{W\sim\operatorname{Haar}}\left[\operatorname{Tr}(\Pi_{1}W\Pi_{2}W^{\dagger})\leq
2\varepsilon\right]\leq\exp\left(-\frac{(d-1)(1-2\varepsilon)^{2}}{2}\right)$
(53)

where the last inequality employs Lemma 11 with taking $t=1-2\varepsilon$.

On the other hand, employing the relation between trace distance and fidelity
of pure states yields

$\displaystyle\big{\|}\rho_{W}-\rho_{\mathbb{I}}\big{\|}_{1}=$
$\displaystyle\big{\|}W\ket{\phi}\bra{\phi}W^{\dagger}-\ket{\phi}\bra{\phi}\big{\|}_{1}$
$\displaystyle=$
$\displaystyle\frac{1}{2}\sqrt{1-\operatorname{Tr}(W\ket{\phi}\bra{\phi}W^{\dagger}\ket{\phi}\bra{\phi})}$
$\displaystyle=$
$\displaystyle\frac{1}{2}\sqrt{\operatorname{Tr}(W\ket{\phi}\bra{\phi}W^{\dagger}(\mathbb{I}_{d}-\ket{\phi}\bra{\phi}))}.$
(54)

This leads to the probability upper bound of the event
$\big{\|}\rho_{W}-\rho_{\mathbb{I}}\big{\|}_{1}\geq\gamma\varepsilon$ with
Lemma 11, i.e.,

$\displaystyle\mathbb{P}_{W\sim\operatorname{Haar}}\left[\|\rho_{W}-\rho_{\mathbb{I}}\big{\|}_{1}\geq\gamma\varepsilon\right]=$
$\displaystyle\mathbb{P}_{W\sim\operatorname{Haar}}\left[\operatorname{Tr}(W\ket{\phi}\bra{\phi}W^{\dagger}(\mathbb{I}_{d}-\ket{\phi}\bra{\phi}))\geq
4\gamma^{2}\varepsilon^{2}\right]$ $\displaystyle\leq$
$\displaystyle\exp\left(-\frac{(d-1)(4\gamma^{2}\varepsilon^{2}-1)^{2}}{2}\right),$
(55)

where the first inequality employs the condition
$0<4\gamma^{2}\varepsilon^{2}-1<1$, and the second equation in Lemma 11 with
taking $t=4\gamma^{2}\varepsilon^{2}-1$. In conjunction with Eqn. (50), Eqn.
(53), and Eqn. (55), we have

$\displaystyle\mathbb{P}_{W_{1},\cdots,W_{L}\sim\operatorname{Haar}}\left[\bigcup_{i=1}^{L}\bigcup_{j=i+1}^{L}\left\\{\|\rho_{i}-\rho_{j}\big{\|}_{1}\leq
2\varepsilon\right\\}\bigcup\left\\{\|\rho_{i}-\rho_{j}\big{\|}_{1}\geq\gamma\varepsilon\right\\}\right]$
$\displaystyle\leq$
$\displaystyle\frac{L(L+1)}{2}\left(\exp\left(-\frac{(d-1)(1-2\varepsilon)^{2}}{2}\right)+\exp\left(-\frac{(d-1)(4\gamma^{2}\varepsilon^{2}-1)^{2}}{2}\right)\right)$
$\displaystyle\leq$ $\displaystyle
L^{2}\exp\left(-\frac{d\min\\{(1-2\varepsilon)^{2},(4\gamma^{2}\varepsilon^{2}-1)^{2}\\}}{4}\right).$
(56)

This inequality implies that when taking $L=\exp(d(1-\varepsilon)^{2}/16)$,
the probability of the event that $\\{\rho_{i}\\}_{i=1}^{L}$ is not an
$\varepsilon$-packing or there exists $\rho_{i},\rho_{j}$ obeying
$\|\rho_{i}-\rho_{j}\|_{1}\leq\gamma\varepsilon$ is strictly less than one.
Therefore, we can conclude that there exists a local $\varepsilon$-packing
whose cardinality is larger than
$L=\exp(d\min\\{(1-2\varepsilon)^{2},(4\gamma^{2}\varepsilon^{2}-1)^{2}\\}/16)$.
This completes the proof.

∎

We are now ready to present the proof of Lemma 9.

###### Proof of Lemma 9.

To measure the local $2\varepsilon$-packing cardinality of $\mathcal{F}$, we
first consider the local packing cardinality of the operator group
$\mathcal{U}_{O}=\\{U^{\dagger}OU|U\in\mathbb{S}\mathbb{U}(d)\\}$ and then
employ the relation between
$\varrho(\operatorname{Tr}(U_{1}^{\dagger}OU_{1}\rho),\operatorname{Tr}(U_{2}^{\dagger}OU_{2}\rho))$
and
$\varrho_{A}(U_{1}^{\dagger}OU_{1},U_{2}^{\dagger}OU_{2})=\|U_{1}^{\dagger}OU_{1}-U_{2}^{\dagger}OU_{2}\|_{1}$
to obtain the local $2\varepsilon$-packing cardinality of $\mathcal{F}$ in the
$\varrho$-metric. Specifically, denote
$\tilde{\varepsilon}=2\sqrt{2d(d+1)}\varepsilon$, we first construct a local
$\tilde{\varepsilon}$-packing
$\mathcal{P}_{\tilde{\varepsilon}}^{(\gamma\tilde{\varepsilon})}(\mathcal{U}_{O},\varrho_{A})$
of the operator group $\mathcal{U}_{O}$ following the manner in Lemma 12 as
$U^{\dagger}OU$ is the density matrix representation of a quantum state for
the projective measurement $O=\ket{o}\bra{o}$. In this regard, it holds
according to Lemma 12 that for any
$U_{1}^{\dagger}OU_{1},U_{2}^{\dagger}OU_{2}\in\mathcal{P}_{\tilde{\varepsilon}}^{(\gamma\tilde{\varepsilon})}(\mathcal{U}_{O},\varrho_{A})$,

$2\tilde{\varepsilon}<\varrho_{A}(U_{1}^{\dagger}OU_{1},U_{2}^{\dagger}OU_{2})<\gamma\tilde{\varepsilon}.$
(57)

On the other hand, the $\varrho$-metric between the elements $f_{U_{1}}$ and
$f_{U_{2}}$ in $\mathcal{F}$ yields

$\displaystyle\varrho(f_{U_{1}},f_{U_{2}})$ $\displaystyle=$
$\displaystyle\sqrt{\mathbb{E}_{\rho\sim
Haar}\operatorname{Tr}\left(O\left(U_{1}^{\dagger}\rho
U_{1}-U_{2}^{\dagger}\rho U_{2}\right)\right)^{2}}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2d(d+1)}}\left\|U_{1}^{\dagger}OU_{1}-U_{2}^{\dagger}OU_{2}\right\|_{1}$
$\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2d(d+1)}}\varrho_{A}(U_{1}^{\dagger}OU_{1},U_{2}^{\dagger}OU_{2})$
(58)

where the second equality follows Eqn. (36). In conjunction with Eqn. (57) and
Eqn. (58), we have

$4\varepsilon<\varrho(f_{U_{1}},f_{U_{2}})=\frac{1}{\sqrt{2d(d+1)}}\varrho_{A}(U_{1}^{\dagger}OU_{1},U_{2}^{\dagger}OU_{2})<2\gamma\varepsilon,$
(59)

where the inequality employs the notation
$\tilde{\varepsilon}=2\sqrt{2d(d+1)}\varepsilon$. This implies that the set
$\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}=\\{f_{U_{1}}:U_{1}^{\dagger}OU_{1}\in\mathcal{P}_{\tilde{\varepsilon}}^{(\gamma\tilde{\varepsilon})}(\mathcal{U}_{O},\varrho_{A})\\}$
refers to the local $2\varepsilon$-packing of $\mathcal{F}$ where the
$\varrho$-metric distance between arbitrary elements in
$\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}$ is larger than
$4\varepsilon$ and less than $2\gamma\varepsilon$. Hence, the cardinality of
the local $2\varepsilon$-packing
$\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}$ is the same as that of
$\mathcal{P}_{\tilde{\varepsilon}}^{(\gamma\tilde{\varepsilon})}(\mathcal{U}_{O},\varrho_{A})$,
i.e.,

$\left|\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}\right|=\left|\mathcal{P}_{\tilde{\varepsilon}}^{(\gamma\tilde{\varepsilon})}(\mathcal{U}_{O},\varrho_{A})\right|\geq\exp\left(\frac{d\min\\{(1-2\tilde{\varepsilon})^{2},(4\gamma^{2}\tilde{\varepsilon}^{2}-1)^{2}\\}}{16}\right),$
(60)

where the inequality follows Lemma 12 with denoting
$\tilde{\varepsilon}=2\sqrt{2d(d+1)}\varepsilon$. This completes the proof.

∎

###  C.6 Proof of Lemma 10—bounding the mutual information $I({X};\hat{X})$

The upper bound of the mutual information $I(X;\hat{X})$ is derived from two
aspects. First, the mutual information between $X$ and $\hat{X}$ is upper
bounded by the mutual information of the output states
$\\{(U_{X}\otimes\mathbb{I}_{\mathcal{R}})\ket{\psi_{j}}\\}_{j=1}^{N}$ and
measurement outputs $\\{\bm{o}_{j}\\}_{j=1}^{N}$, according to the data
processing inequality. This is because increasing the number of measurements
allows for more information to be extracted from the output states, thereby
increasing the mutual information $I(X;\hat{X})$. Second, as the mutual
information $I(X;\hat{X})$ cannot grow infinitely with the number of
measurements, it is also upper bounded by the mutual information between the
index $X$ and the training output states
$\\{(U_{X}\otimes\mathbb{I}_{\mathcal{R}})\ket{\psi_{j}}\\}_{j=1}^{N}$, which
can be interpreted as the maximum amount of information that the output states
can obtain about the target unitary. These observations are formulated as the
following lemmas, namely, Lemma 13 and Lemma 14, which are used to derive the
results of Lemma 10.

######  Lemma 13.

For a given observable $O$ and the output state
$\rho_{X}=(U_{X}\otimes\mathbb{I}_{\mathcal{R}})\rho(U_{X}^{\dagger}\otimes\mathbb{I}_{\mathcal{R}})$
with $X$ uniformly distributed in the index set of the local
$2\varepsilon$-packing $\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}$,
assume that the $m$-measurement output $\bm{o}=\sum_{k=1}^{m}\bm{o}_{k}/m$
conditional on $X=x$ follows the normal distribution
$\mathbb{N}(u_{x},(\sigma_{x})^{2})$ where $u_{x}$ and $\sigma^{2}$ refers to
the mean and variance following Assumption 1. Then the mutual information
between $X$ and $\bm{o}$ given the training state $\rho$ yields

$I(X;\bm{o})\leq\frac{1}{|\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}|^{2}}\sum_{x,x^{\prime}\in\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}}\frac{(u_{x}-u_{x^{\prime}})^{2}}{2\sigma^{2}}.$
(61)

###### Proof of Lemma 13.

Denote $\Theta$ as the value space of $\bm{o}$. Let $p_{X}$ and
$\mathbb{P}_{\bm{o}|\rho_{x}}=\mathbb{P}(\cdot|\rho_{x}):=p(\cdot|X=x,\rho)$
be the distribution of $X$ and the distribution of $\bm{o}$ conditional on
$X=x$ for fixed input state $\rho$, respectively. For simplicity, in the
following, we denote $I(\rho_{X};\bm{o})=I(X;\bm{o}|\rho)$ and
$p(\rho_{X},\bm{o})=p(X,\bm{o}|\rho)$ as the mutual information and joint
distribution between $X$ and $\bm{o}$ given $\rho$. Then $\bm{o}$ is drawn
from the mixture distribution,

$\bar{\mathbb{P}}_{\bm{o}}:=\sum_{x\in\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}}p_{X}(x)\mathbb{P}_{\bm{o}|\rho_{x}}=\frac{1}{|\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}|}\sum_{x\in\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}}\mathbb{P}_{\bm{o}|\rho_{x}},$
(62)

where the second equality follows that $X$ is uniform in
$\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}$. Denoting
$p(\rho_{x},\bm{o})$ and $p(\bm{o}|\rho_{x})$ as the joint probability
distribution function of $\bm{o}$ and $X=x$, and the conditional probability
distribution function of $\bm{o}$ on $X=x$, respectively. With the definition
of the mixture distribution and mutual information, we have

$\displaystyle I(\rho_{X};\bm{o})$
$\displaystyle=D_{\operatorname{KL}}(\mathbb{P}_{\rho_{X},\bm{o}}\|\mathbb{P}_{\rho_{X}}\mathbb{P}_{\bm{o}})$
$\displaystyle=\sum_{x\in\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}}\int_{\Theta}p(\rho_{x},\bm{o})\log\frac{p(\rho_{x},\bm{o})}{p_{X}(x)\bar{p}(\bm{o})}\mathrm{d}\bm{o}$
$\displaystyle=\sum_{x\in\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}}p_{X}(x)\int_{\Theta}p(\bm{o}|\rho_{x})\log\frac{p(\bm{o}|\rho_{x})}{\bar{p}(\bm{o})}\mathrm{d}\bm{o}$
$\displaystyle=\frac{1}{|\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}|}\sum_{x\in\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}}D_{\operatorname{KL}}(\mathbb{P}_{x}\|\bar{\mathbb{P}}_{\bm{o}})$
$\displaystyle\leq\frac{1}{|\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}|^{2}}\sum_{x,x^{\prime}\in\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}}D_{\operatorname{KL}}(\mathbb{P}_{x}\|\mathbb{P}_{x^{\prime}})$
$\displaystyle=\frac{1}{|\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}|^{2}}\sum_{x,x^{\prime}\in\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}}D_{\operatorname{KL}}(\mathbb{N}(u_{x},\sigma^{2})\|\mathbb{N}(u_{x^{\prime}},\sigma^{2}))$
$\displaystyle=\frac{1}{|\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}|^{2}}\sum_{x,x^{\prime}\in\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}}\frac{(u_{x}-u_{x^{\prime}})^{2}}{2\sigma^{2}},$
(63)

where the first equality and the second equality employ the definition of
mutual information that $I(X;Y)=D_{\operatorname{KL}}(p_{XY}||p_{X}p_{Y})$
with $D_{\operatorname{KL}}$ referring to the KL-divergence and
$p_{XY},p_{X},p_{Y}$ referring to the joint probability distribution of $X$
and $Y$, the probability distribution of $X$ and $Y$ respectively, the third
equality exploits the property of conditional probability that
$p(\rho_{x},\bm{o})=p(\bm{o}|\rho_{x})p_{X}(x)$, the fourth equality follows
that $X$ is uniform in $\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}$ and
hence $p_{X}(x)=1/|\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}|$ for all
$x\in\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}$, the first inequality
employs the Jensen’s inequality with the convexity of the function $-\log$,
the fifth equality follows that $o_{j}=\sum_{k=1}^{m}o_{k}/m$ following the
binomial distribution $\mathbb{B}(m,u_{x})$ is approximated by the normal
distribution $\mathbb{N}(u_{x},\sigma^{2})$ with the variance is assumed to be
identical over difference choice of $x$, the final equality is obtained by
algebraic computation of the KL-divergence between two Gaussian distributions
with the identical variance. ∎

We next drive an upper bound of the mutual information $I(X;\hat{X})$
independent with the number of measurements $m$. Particularly, since a large
number of measurements aims to precisely estimate the expectation value of the
projective measurement $O$ on the training output states
$(U_{X}\otimes\mathbb{I}_{d})\ket{\psi_{j}}$, i.e.,
$u_{j}^{(X)}=\operatorname{Tr}((U_{X}^{\dagger}OU_{X}\otimes\mathbb{I}_{d})\ket{\psi_{j}}\bra{\psi_{j}})$,
we can directly focus on the mutual information of $X$ and the training output
states $\\{(U_{X}\otimes\mathbb{I}_{d})\ket{\psi_{j}}\\}_{j=1}^{N}$ by
regarding the states $(U_{X}\otimes\mathbb{I}_{d})\ket{\psi_{j}}$ as random
variables. We encapsulate the analyzed results related to this case into the
following lemma.

######  Lemma 14.

For any Haar random unitary $U_{X}$ uniformly sampled from the local
$2\varepsilon$-packing
$\\{U_{x}\\}_{x\in\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}}$ and the
entangled states set
$\\{\ket{\psi_{j}}=\sum_{k=1}^{r}\sqrt{c_{jk}}\ket{\xi_{jk}}\ket{\zeta_{jk}}\\}_{j=1}^{N}$,
let $\bm{o}_{j}=\sum_{k=1}^{m}\bm{o}_{jk}/m$ be the $m$ measured results of
the corresponding output states
$\ket{\psi_{j}^{(X)}}=(U_{X}\otimes\mathbb{I}_{d})\ket{\psi_{j}}$ under the
projective measurement $O$. Then the mutual information between $X$ and the
measurement outputs $\bm{o}_{1},\cdots,\bm{o}_{N}$ for the infinite number of
measurements $m\rightarrow\infty$ yields

$\lim\limits_{m\to\infty}I(X;\bm{o}_{1},\cdots,\bm{o}_{N})\leq
I(X;\ket{\psi_{1}^{(X)}},\cdots,\ket{\psi_{N}^{(X)}})\leq
Nr\log\left(d\right).$ (64)

###### Proof of Lemma 14.

We first note that when the number of measurements $m$ is infinite, the
measured result $\bm{o}_{j}$ is exactly the expectation value of the output
states $\ket{\psi_{j}^{(X)}}$ under the projective measurement $O$, i.e.,
$\lim_{m\to\infty}\bm{o}_{j}=u_{j}^{(X)}:=\operatorname{Tr}((O\otimes\mathbb{I}_{d})\ket{\psi_{j}^{(X)}}\bra{\psi_{j}^{(X)}})$.
In this regard, we have

$\displaystyle\lim\limits_{m\to\infty}I(X;\bm{o}_{1},\cdots,\bm{o}_{N})=$
$\displaystyle
I\left(X;\lim\limits_{m\to\infty}\bm{o}_{1},\cdots,\lim\limits_{m\to\infty}\bm{o}_{N}\right)$
$\displaystyle=$ $\displaystyle
I\left(X;u_{1}^{(X)},\cdots,u_{N}^{(X)}\right)$ $\displaystyle\leq$
$\displaystyle
I\left(X;\ket{\psi_{1}^{(X)}},\cdots,\ket{\psi_{N}^{(X)}}\right)$
$\displaystyle\leq$ $\displaystyle
I(X;\ket{\xi_{11}^{(X)}},\cdots,\ket{\xi_{1r}^{(X)}},\cdots,\ket{\xi_{N1}^{(X)}},\cdots,\ket{\xi_{Nr}^{(X)}})$
$\displaystyle=$ $\displaystyle
I\left(X;\otimes_{j=1}^{N}\otimes_{k=1}^{r}\ket{\xi_{jk}^{(X)}}\right)$
$\displaystyle\leq$ $\displaystyle
S\left(\frac{1}{\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}}\sum_{x\in\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}}\otimes_{j=1}^{N}\otimes_{k=1}^{r}\ket{\xi_{jk}^{(x)}}\bra{\xi_{jk}^{(x)}}\right)$
$\displaystyle\leq$ $\displaystyle Nrn\log(2)$ (65)

where the first equality employs the dominated convergence theorem applied to
the integrated function in the mutual information, which converges point-wise
and is bounded by $\log(|\mathcal{X}_{2\varepsilon}^{(2\gamma\varepsilon)}|)$,
such that the interchange of the order of limitation and integration in the
calculation is allowed, the first inequality employs the data processing
inequality given in the Property 6 for the Markov chain
$X\to\ket{\psi_{1}^{(X)}},\cdots,\ket{\psi_{N}^{(X)}}\to
u_{1}^{(X)},\cdots,u_{N}^{(X)}$, the second inequality follows the data
processing inequality with the observation that the randomness of the states
$\ket{\psi_{j}^{(X)}}$ about $X$ comes from the states
$\\{\ket{\xi_{jk}^{(X)}}\\}_{k=1}^{r}$ and hence there exists an
$X$-independent functional
$g:\\{\ket{\xi_{jk}^{(X)}}\\}_{j,k=1}^{N,r}\to\\{\ket{\psi_{j}^{(X)}}\\}_{1}^{N}$
leading to a Markov chain
$X\to\\{\ket{\xi_{jk}^{(X)}}\\}_{j,k=1}^{r}\to\\{\ket{\psi_{j}^{(X)}}\\}_{1}^{N}$,
the second inequality employs the Holevo’s theorem araki1970entropy ;
bengtsson2017geometry ; holevo1973bounds ; horodecki2009quantum , and the last
inequality uses the fact that the entropy of mixed states living in an
$(N\cdot r\cdot n)$-qubit system is at most $Nrn\log 2$. This completes the
proof. ∎

We note that the mutual information $I(X;\ket{\psi_{j}^{(X)}})$ is defined to
quantify the accessible information of the target index from the limited
number of training states. Lemma 14 implies that the mutual information
between the target index $X$ and the measurement outputs of projective
measurement $O$ on the $m$ copies of the state $\ket{\psi_{j}^{(X)}}$ is upper
bounded by the mutual information between $X$ and the single copy of