# Power of Quantum Generative Learning

Yuxuan Du  JD Explore Academy, Beijing 101111, China  Zhuozhuo Tu  School of
Computer Science, The University of Sydney, Darlington, NSW 2008, Australia
Bujiao Wu  Center on Frontiers of Computing Studies, Peking University,
Beijing 100871, China  School of Computer Science, Peking University, Beijing
100871, China  Xiao Yuan  Center on Frontiers of Computing Studies, Peking
University, Beijing 100871, China  School of Computer Science, Peking
University, Beijing 100871, China  Dacheng Tao  JD Explore Academy, Beijing
101111, China

###### Abstract

The intrinsic probabilistic nature of quantum mechanics invokes endeavors of
designing quantum generative learning models (QGLMs). Despite the empirical
achievements, the foundations and the potential advantages of QGLMs remain
largely obscure. To narrow this knowledge gap, here we explore the
generalization property of QGLMs, the capability to extend the model from
learned to unknown data. We consider two prototypical QGLMs, quantum circuit
Born machines and quantum generative adversarial networks, and explicitly give
their generalization bounds. The result identifies superiorities of QGLMs over
classical methods when quantum devices can directly access the target
distribution and quantum kernels are employed. We further employ these
generalization bounds to exhibit potential advantages in quantum state
preparation and Hamiltonian learning. Numerical results of QGLMs in loading
Gaussian distribution and estimating ground states of parameterized
Hamiltonians accord with the theoretical analysis. Our work opens the avenue
for quantitatively understanding the power of quantum generative learning
models.

##  I Introduction

Learning is a generative activity that constructs its own interpretations of
information and draws inferences on them wittrock1989generative . This
comprehensive philosophy sculpts a substantial subject in artificial
intelligence, which is designing powerful generative learning models (GLMs)
lecun2015deep ; schmidhuber2015deep  to capture the distribution $\mathbb{Q}$
describing the real-world data (see Fig. 1(a)). Concisely, a fundamental
concept behind GLMs is estimating $\mathbb{Q}$ by a tunable probability
distribution $\mathbb{P}_{\operatorname{\bm{\theta}}}$. In the past decades, a
plethora of GLMs, e.g., the Helmholtz machine dayan1995helmholtz , variational
auto-encoders Kingma2013VAE , and generative adversarial networks (GANs)
goodfellow2014generative ; zhao2017energy , have been proposed. Attributed to
the efficacy and flexibility of handling
$\mathbb{P}_{\operatorname{\bm{\theta}}}$, these GLMs have been broadly
applied to myriad scientific domains and gained remarkable success, including
image synthesis and editing YiLLR19 ; karras2019style ; park2019semantic ,
medical imaging armanious2020medgan , molecule optimization maziarka2020mol ;
mendez2020novo , and quantum computing ahmed2021quantum ;
carrasquilla2019reconstructing ; smith2021efficient ; rocchetto2018learning ;
melko2019restricted ; carleo2018constructing . Despite the wide success, their
limitations have recently been recognized from different perspectives, such as
expensive runtime and inferior performance towards complex datasets
Du2019implicit ; dosovitskiy2016generating ; arora2018do ; che2016mode ;
mescheder2018training ; gui2020review .

Envisioned by the intrinsic probabilistic nature of quantum mechanics and the
superior power of quantum computers feynman2017quantum ; biamonte2017quantum ;
harrow2017quantum , quantum generative learning models (QGLMs) are widely
believed to enhance the ability of GLMs. Concrete evidence has been provided
by Refs. gao2018quantum ; lloyd2018quantum , showing that fault-tolerant based
QGLMs could surpass GLMs with stronger model expressivity and runtime
speedups. Since fault-tolerant quantum computing is still in absence,
attention has recently shifted to design QGLMs that can be efficiently carried
out on noisy intermediate-scale quantum (NISQ) machines preskill2018quantum ;
arute2019quantum ; wu2021strong  with advantages on specific tasks
huang2021quantum ; huang2021power ; Wang2021towards ; du2021exploring . For
this purpose, a leading strategy is constructing QGLMs through variational
quantum algorithms (VQAs) cerezo2021variational ; bharti2021noisy . Depending
on whether the probability distribution
$\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}$ is explicitly
formulated or not 111Implicit probabilistic models do not specify the
distribution of the data itself, but rather define a stochastic process that,
after training, aims to draw samples from the underlying data distribution.
Refer to SM A for details, these QGLMs can be mainly divided into explicit
QGLMs and implicit QGLMs. Primary protocols of these two classes are quantum
circuit Born machines (QCBMs) benedetti2019generative ; liu2018differentiable
; coyle2021quantum ; du2018expressive  and quantum generative adversarial
networks (QGANs) zoufal2019quantum ; zeng2019learning ; huang2021experimental
; huang2021quantum2 ; romero2021variational ; gili2022evaluating ;
nakaji2021quantum ; braccia2022quantum ; anand2021noise ; du2022Effcient ;
huang2021quantum2 . Experimental studies have demonstrated the feasibility of
QGLMs for different learning tasks, e.g., image generation zhu2019training ;
huang2021experimental , state approximation huang2021quantum ; hu2019quantum ,
and drug design li2021quantum ; Jin2022Quantum .

A crucial vein in quantum machine learning biamonte2017quantum  is
comprehending potential advantages of quantum learners from the perspective of
generalization, which quantifies the capability to extend the model from
learned to unknown data arora2017generalization ; allen2019learning ;
du2021learnability ; zhao2018bias . In sharp contrast to quantum
discriminative learning abbas2020power ; banchi2021generalization ;
caro2021generalization ; du2021efficient ; huang2021information ;
Junyu2022dynamic ; qian2021dilemma , prior literature related to the
generalization of QGLMs is scarce and negative sweke2021quantum ;
hinsche2021learnability . Concretely, Ref. hinsche2021learnability  pointed
out the hardness for both QCBM and GLMs to efficiently learn the output
distributions of local quantum circuits under the statistical query access. In
this regard, two key questions are naturally invoked: how to quantify the
generalization of different QGLMs in a generic way? And is there any potential
advantage of QGLMs in solving nontrivial learning problems?

Figure 1: The paradigm of quantum generative learning models. (a) The data
explored in generative learning includes both classical and quantum scenarios.
(b) The approaches of QGLMs to access target data distribution
$\operatorname{\mathbb{Q}}$. When $\operatorname{\mathbb{Q}}$ is classical,
QGLMs operate its samples on the classical side or encode its samples into
quantum circuits. When $\operatorname{\mathbb{Q}}$ is quantum, QGLMs may
directly access it without sampling. (c) The paradigm of QCBMs with MMD loss.
The left and right panels depict the setup of classical and quantum kernels,
respectively. (d) The scheme of QGANs with MMD loss for the continuous
distribution $\operatorname{\mathbb{Q}}$. (e) QAOA, hardware-efficient, and
tensor-network based Ansätze are covered by
$\hat{U}(\operatorname{\bm{\theta}})$ in Eq. (2). (f) The metrics exploited in
QGLMs to measure the discrepancy between the generated and target
distributions. (g) When $\operatorname{\mathbb{Q}}$ and $k(\cdot,\cdot)$ are
both quantum, QGLMs may attain generalization advantages over classical GLMs.

To shrink the above knowledge gap, here we establish the generalization theory
of QGLMs with the maximum mean discrepancy (MMD) loss Gretton2012AKernel  and
utilize these results to affirm potential merits of QGLMs in practical
applications. The attention on MMD loss is because it is an efficient measure
to evaluate the difference between
$\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}$ and
$\operatorname{\mathbb{Q}}$ without the curse of dimensionality issue. Our
first result is unveiling the power of QCBMs and QGANs through the lens of the
statistical learning theory vapnik1999nature . Specifically, when
$\operatorname{\mathbb{Q}}$ is discrete, we prove that the generalization
error of QCBMs scales with $\tilde{O}(\sqrt{1/n+1/m})$, where $n$ and $m$
refer to the number of examples sampled from
$\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}$ and
$\operatorname{\mathbb{Q}}$. In addition, when $\operatorname{\mathbb{Q}}$ can
be efficiently prepared by quantum circuits (see Fig. 1(b)), quantum kernels
enable QCBMs to attain a strictly lower generalization error than classical
kernels. When $\operatorname{\mathbb{Q}}$ is continuous, we prove that the
generalization error of QGAN is upper bounded by
$\tilde{O}(\sqrt{1/n+1/m}+Nd^{k}\sqrt{N_{gt}N_{ge}}/n)$, where $d$, $k$,
$N_{ge}$, and $N_{gt}$ refer to the dimension of a qudit, the type of quantum
gates, the number of encoding gates, and the number of trainable parameters,
respectively. This bound explicitly reveals how the encoding strategy and the
adopted Ansatz affect the generalization. Taken together, sufficient
expressivity and large examples allows
$\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}\approx\operatorname{\mathbb{Q}}$
for QGLMs. In light of this observation, we exhibit the potential advantage of
QCBMs and QGANs in quantum state preparation and parameterized Hamiltonian
learning.

The remainder of this study is organized as follows. In Secs. II & III, we
theoretically explore the power of QCBM and QGAN through the lens of
statistical learning theory, respectively. Then, in Sec. IV, we elaborate how
QGLMs can advance quantum state preparation and Hamiltonian learning.
Subsequently, we conduct numerical simulations to validate our claims about
QCBMs and QGANs in Sec. V. We conclude this study in Sec. VI.

##  II Generalization of QCBM

We first study the generalization property of QCBM. As shown in Fig. 1(a),
QCBM applies an $N$-qudit Ansatz $\hat{U}(\bm{\theta})$ to a fixed input state
$\rho_{0}=(\ket{0}\bra{0})^{\otimes N}$ to form the parameterized distribution
$\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}\in\operatorname{\mathbb{P}}_{\bm{\Theta}}$,
where $\operatorname{\bm{\theta}}$ denotes trainable parameters living in the
parameter space $\bm{\Theta}$. The probability of sampling $i\in[d^{N}]$ over
the discrete distribution
$\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}$ yields

$\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}(i)=\operatorname{Tr}(\Pi_{i}\hat{U}(\bm{\theta})\rho_{0}\hat{U}(\bm{\theta})^{\dagger}),$
(1)

where $\Pi_{i}=\ket{i}\bra{i}$ refers to the projector of the computational
basis $i$. Given $n$ reference examples $\\{\bm{x}^{(j)}\\}_{j=1}^{n}$ sampled
from $\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}$, its empirical
distribution is defined as
$\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}^{n}(i)=\sum_{j=1}^{n}\delta_{\bm{x}^{(j)}}(i)/n$
with $\delta_{(\cdot)}(\cdot)$ being the indicator. Throughout the whole
study, the Ansatz employed in QCBMs takes the generic form

$\hat{U}(\bm{\theta})=\prod_{l=1}^{N_{g}}\hat{U}_{l}(\bm{\theta}),$ (2)

where $\hat{U}_{l}(\bm{\theta})\in\mathcal{U}(d^{k})$ refers to the $l$-th
quantum gate operated with at most $k$-qudits with $k\leq N$, and
$\mathcal{U}(d^{k})$ denotes the unitary group in dimension $d^{k}$ ($d=2$ for
qubits). Note that for simplicity, the definition of $N$-qudit Ansatz
$\hat{U}(\bm{\theta})$ in Eq. (2) omits some identity operators. The complete
description for the $l$-th layer is
$\mathbb{I}_{d^{N-k}}\otimes\hat{U}_{l}(\bm{\theta})$. The form of
$\hat{U}(\operatorname{\bm{\theta}})$ covers almost all Ansätze in VQAs and
some constructions are given in Fig. 1(e).

The training of QCBMs is guided by the maximum mean discrepancy (MMD) loss
Gretton2012AKernel . Suppose $\operatorname{\mathbb{Q}}$ and
$\operatorname{\mathbb{P}}_{\bm{\theta}}$ live on the same space. The MMD loss
measures the difference between
$\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}$ and
$\operatorname{\mathbb{Q}}$ with

$\operatorname{MMD}^{2}(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}||\operatorname{\mathbb{Q}})=\operatorname{\mathbb{E}}(k(\bm{x},\bm{x}^{\prime}))+\operatorname{\mathbb{E}}(k(\bm{y},\bm{y}^{\prime}))-2\operatorname{\mathbb{E}}(k(\bm{x},\bm{y})),$

where the expectations are taken over the randomness of examples and
$k(\cdot,\cdot)$ denotes a predefined kernel. QCBMs aim to find an estimator
minimizing MMD loss,

$\hat{\operatorname{\bm{\theta}}}=\arg\min_{\operatorname{\bm{\theta}}\in\bm{\Theta}}\operatorname{MMD}^{2}(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}||\operatorname{\mathbb{Q}}).$
(3)

If the distribution $\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}$
and $\operatorname{\mathbb{Q}}$ cannot be accessed directly, the estimator is
located by minimizing the empirical MMD loss with finite samples
Gretton2012AKernel , i.e.,

$\hat{\operatorname{\bm{\theta}}}^{(n,m)}=\arg\min_{\operatorname{\bm{\theta}}\in\bm{\Theta}}\operatorname{MMD}_{U}^{2}(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}^{n}||\operatorname{\mathbb{Q}}^{m}),$
(4)

where $\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}^{n}$ and
$\operatorname{\mathbb{Q}}^{m}$ separately refers to the empirical
distribution of $\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}$ and
$\operatorname{\mathbb{Q}}$, and

$\displaystyle\operatorname{MMD}^{2}_{U}(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}^{n}||\operatorname{\mathbb{Q}}^{m}):=\frac{1}{n(n-1)}\sum_{i\neq
i^{\prime}}^{n}k(\bm{x}^{(i)},\bm{x}^{(i^{\prime})})$
$\displaystyle+\frac{1}{m(m-1)}\sum_{j\neq
j^{\prime}}^{m}k(\bm{y}^{(j)},\bm{y}^{(j^{\prime})})-\frac{2}{nm}\sum_{i,j}k(\bm{x}^{(i)},\bm{y}^{(j)}).$

More explanations of MMD loss are provided in SM B.

The choice of the kernel $k(\cdot,\cdot)$ in MMD loss is flexible. When it is
specified to be the quantum kernel (i.e., the specified kernel can be
efficiently computed by quantum algorithms, where representative examples are
linear kernel and polynomial kernels schuld2019quantum ) and
$\operatorname{\mathbb{Q}}$ can be directly accessed by QGLMs (e.g.,
$\operatorname{\mathbb{Q}}$ can be efficiently prepared by a quantum circuit),
the MMD loss can be efficiently calculated.

######  Lemma 1.

Suppose that the distribution $\operatorname{\mathbb{Q}}$ can be directly
accessed by QCBMs. When the quantum kernel is adopted, the MMD loss in Eq. (3)
can be estimated within an error $\epsilon$ in $O({1}/{\epsilon}^{2})$ runtime
complexity.

###### Proof of Lemma 1.

Here we separately elaborate on the calculation of MMD loss when the target
distribution $\operatorname{\mathbb{Q}}$ can be efficiently prepared by a
diagonalized mixed state
$\sigma=\sum_{\bm{y}}\mathbb{Q}(\bm{y})\ket{\bm{y}}\bra{\bm{y}}$ or a pure
quantum state $\ket{\Psi}=\sum_{\bm{y}}\sqrt{\mathbb{Q}(\bm{y})}\ket{\bm{y}}$.

Diagonalized mixed states. In this setting, the quantum kernel corresponds to
the linear kernel, i.e.,

$k(\bm{a},\bm{a}^{\prime})=\langle\bm{a},\bm{a}^{\prime}\rangle.$

Recall the definition of the MMD loss is
$\operatorname{MMD}^{2}(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}||\operatorname{\mathbb{Q}})=\operatorname{\mathbb{E}}(k(\bm{x},\bm{x}^{\prime}))-2\operatorname{\mathbb{E}}(k(\bm{x},\bm{y}))+\operatorname{\mathbb{E}}(k(\bm{y},\bm{y}^{\prime}))$.
The first term equals to

$\operatorname{\mathbb{E}}\left(k(\bm{x},\bm{x}^{\prime})\right)=\operatorname{\mathbb{E}}_{\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}},\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}}\left(\delta_{\bm{x},\bm{x}^{\prime}}\right)=\sum_{\bm{x}}\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}^{2}(\bm{x}).$

Similarly, the second term equals to

$\operatorname{\mathbb{E}}\left(k(\bm{x},\bm{y})\right)=\sum_{\bm{x}}\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}(\bm{x})\operatorname{\mathbb{Q}}(\bm{x}).$

And the third term equals to

$\operatorname{\mathbb{E}}\left(k(\bm{y},\bm{y}^{\prime})\right)=\sum_{\bm{y}}\operatorname{\mathbb{Q}}^{2}(\bm{y}).$

The above three terms can be effectively and analytically evaluated by quantum
Swap test when the input state of QCBM in Eq. (1) is a full rank mixed state,
e.g., $\rho_{0}=\mathbb{I}_{2^{N}}/2^{N}$. Denote the output state of QCBM as
$\rho=U(\operatorname{\bm{\theta}})\rho_{0}U(\operatorname{\bm{\theta}})^{\dagger}$.
This state is also diagonalized and its diagonalized entry records
$\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}$, i.e.,

$\rho=\sum_{\bm{x}}\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}(\bm{x})\ket{\bm{x}}\bra{\bm{x}}.$

According to buhrman2001quantum ; kobayashi2003quantum , given two mixed
states $\varrho_{1}$ and $\varrho_{2}$, the output of Swap test is
$1/2+\operatorname{Tr}(\varrho_{1}\varrho_{2})/2$ with an additive error
$\epsilon$ in $O(1/\epsilon^{2})$ runtime. As such, when
$\varrho_{1}=\varrho_{2}=\rho$, the first term
$\operatorname{\mathbb{E}}\left(k(\bm{x},\bm{x}^{\prime})\right)$ can be
calculated by Swap test, because
$\operatorname{Tr}(\rho\rho)=\sum_{\bm{x}}\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}^{2}(\bm{x})$.
Likewise, through setting $\varrho_{1}=\rho$, and $\varrho_{2}=\sigma$
($\varrho_{1}=\varrho_{2}=\sigma$), the second (third) term can be efficiently
evaluated by Swap test with an additive error $\epsilon$. In other words, by
leveraging Swap test, we can estimate MMD loss with an additive error
$\epsilon$ in $O(1/\epsilon^{2})$ runtime cost.

Pure states. The quantum kernel in this scenario corresponds to a nonlinear
kernel, i.e.,

$k(\bm{a},\bm{a}^{\prime})=\langle\frac{\bm{a}}{\sqrt{\operatorname{\mathbb{P}}(\bm{a})}},\frac{\bm{a}^{\prime}}{\sqrt{\operatorname{\mathbb{P}}(\bm{a}^{\prime})}}\rangle,$

where $\operatorname{\mathbb{P}}(\bm{a})$ stands for the probability of
sampling $\bm{a}$ and $\sum_{\bm{a}}\operatorname{\mathbb{P}}(\bm{a})=1$. With
this regard, the explicit form of MMD loss yields

$\displaystyle\operatorname{MMD}(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}||\operatorname{\mathbb{Q}})$
$\displaystyle\ =$
$\displaystyle\operatorname{\mathbb{E}}(k(\bm{x},\bm{x}^{\prime}))-2\operatorname{\mathbb{E}}(k(\bm{x},\bm{y}))+\operatorname{\mathbb{E}}(k(\bm{y},\bm{y}^{\prime}))$
$\displaystyle=$
$\displaystyle\sum_{\bm{x}}\sum_{\bm{x}^{\prime}}\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}\left\langle\frac{\bm{x}}{\sqrt{\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}(\bm{x})}},\frac{\bm{x}^{\prime}}{\sqrt{\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}(\bm{x}^{\prime})}}\right\rangle$
$\displaystyle-2\sum_{\bm{x}}\sum_{\bm{y}}\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}\operatorname{\mathbb{Q}}\left\langle\frac{\bm{x}}{\sqrt{\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}(\bm{x})}},\frac{\bm{y}}{\sqrt{\operatorname{\mathbb{Q}}(\bm{y})}}\right\rangle$
$\displaystyle+\sum_{\bm{y}}\sum_{\bm{y}^{\prime}}\operatorname{\mathbb{Q}}\operatorname{\mathbb{Q}}\left\langle\frac{\bm{y}}{\sqrt{\operatorname{\mathbb{Q}}(\bm{y})}},\frac{\bm{y}^{\prime}}{\sqrt{\operatorname{\mathbb{Q}}(\bm{y}^{\prime})}}\right\rangle$
$\displaystyle=$
$\displaystyle\sum_{\bm{x}}\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}(\bm{x})+\sum_{\bm{y}}\operatorname{\mathbb{Q}}(\bm{y})-2\sum_{\bm{x}}\sqrt{\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}(\bm{x})\operatorname{\mathbb{Q}}(\bm{x})}$
$\displaystyle=$ $\displaystyle
2-2\sum_{\bm{x}}\sqrt{\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}(\bm{x})\operatorname{\mathbb{Q}}(\bm{x})}.$

The above results indicate that the evaluation of $\operatorname{MMD}$ loss
amounts to calculating
$\sum_{\bm{x}}\sqrt{\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}(\bm{x})\operatorname{\mathbb{Q}}(\bm{x})}$.
Denote the generated state of QCBM as
$\ket{\Phi(\operatorname{\bm{\theta}})}=U(\operatorname{\bm{\theta}})\ket{0}^{\otimes
n}=e^{i\phi}\sum_{\bm{x}}\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}(\bm{x})\ket{\bm{x}}$,
where $\rho_{0}=(\ket{0}\bra{0})^{\otimes n}$. When the target distribution
$\operatorname{\mathbb{Q}}$ refers to a pure quantum state
$\ket{\Psi}=\sum_{\bm{y}}\sqrt{\operatorname{\mathbb{Q}}(\bm{y})}\ket{\bm{y}}$,
the term
$\sum_{\bm{x}}\sqrt{\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}(\bm{x})\operatorname{\mathbb{Q}}(\bm{x})}$
can be evaluated by Swap test buhrman2001quantum , i.e.,

$|\braket{\Phi(\operatorname{\bm{\theta}})}{\Psi}|^{2}=\left(\sum_{i=1}^{2^{N}}\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}(\bm{x})\operatorname{\mathbb{Q}}(\bm{x})\right)^{2}.$
(5)

According to buhrman2001quantum , taking account of the sample error, this
term can be estimated within an additive error $\epsilon$ in
$O(1/\epsilon^{2})$ runtime complexity. ∎

It hints that when both $k(\cdot,\cdot)$ and $\operatorname{\mathbb{Q}}$ are
quantum,
$\operatorname{MMD}^{2}(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}||\operatorname{\mathbb{Q}})$
can be efficiently calculated in which the runtime cost is independent of the
dimension of data space. In contrast, for GLMs and QCBMs with classical
kernels, the runtime cost in computing the MMD loss polynomially scales with
$n$ and $m$. Such runtime discrepancy warrants the advantage of QCBMs
explained in the subsequent context.

We now analyze the generalization ability of QCBMs. To begin with, let us
extend the definition of generalization error from the classical learning
theory dziugaite2015training  to the regime of quantum generative learning.

######  Definition 1 (Generalization error of QGLMs).

When either the kernel $k(\cdot,\cdot)$ or the target
$\operatorname{\mathbb{Q}}$ is classical, the generalization error of QGLMs is

$\mathfrak{R}^{C}=\operatorname{MMD}^{2}(\operatorname{\mathbb{P}}_{\hat{\operatorname{\bm{\theta}}}^{(n,m)}}||\operatorname{\mathbb{Q}})-\inf_{\operatorname{\bm{\theta}}\in\bm{\Theta}}\operatorname{MMD}^{2}(\operatorname{\mathbb{P}}_{\bm{\theta}}||\operatorname{\mathbb{Q}}).$
(6)

When the kernel $k(\cdot,\cdot)$ is quantum and $\operatorname{\mathbb{Q}}$
can be efficiently accessed by quantum machines, the generalization error of
QGLMs is

$\mathfrak{R}^{Q}=\operatorname{MMD}^{2}(\operatorname{\mathbb{P}}_{\hat{\operatorname{\bm{\theta}}}}||\operatorname{\mathbb{Q}})-\inf_{\operatorname{\bm{\theta}}\in\bm{\Theta}}\operatorname{MMD}^{2}(\operatorname{\mathbb{P}}_{\bm{\theta}}||\operatorname{\mathbb{Q}}).$
(7)

Intuitively, both $\mathfrak{R}^{C}$ and $\mathfrak{R}^{Q}$ evaluate the
divergence of the estimated and the optimal MMD loss, where a lower
$\mathfrak{R}^{C}$ or $\mathfrak{R}^{Q}$ suggests a better generalization
ability. The following theorem establishes the generalization theory of QCBMs.

######  Theorem 1.

Assume
$\max_{\operatorname{\bm{\theta}}\in\bm{\Theta}}\operatorname{MMD}^{2}(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}||\operatorname{\mathbb{Q}})\leq
C_{1}$ with $C_{1}$ being a constant. Define
$C_{2}=\sup_{\bm{x}}k(\bm{x},\bm{x})$. Following settings in Lemma 1, with
probability at least $1-\delta$, the generalization error of QCBMs yields

$\mathfrak{R}^{Q}\leq\mathfrak{R}^{C}\leq
C_{1}\sqrt{\frac{8}{n}+\frac{8}{m}}\sqrt{C_{2}}(2+\sqrt{\log\frac{1}{\delta}}).$
(8)

###### Proof of Theorem 1.

To prove Theorem 1, we first derive the upper bound of the generalization
error $\mathfrak{R}^{C}$ under the generic setting. Then, we analyze
$\mathfrak{R}^{Q}$ under the specific setting where the quantum kernel is
employed and the target distribution $\operatorname{\mathbb{Q}}$ can be
directly accessed by quantum machines. The analysis of $\mathfrak{R}^{C}$
adopts the following lemma.

######  Lemma 2 (Adapted from Theorem 1, briol2019statistical ).

Suppose that the kernel $k(\cdot,\cdot)$ is bounded. Following the notations
in Theorem 1, when the number of examples sampled from
$\operatorname{\mathbb{P}}_{\hat{\operatorname{\bm{\theta}}}^{(n,m)}}$ and
$\operatorname{\mathbb{Q}}$ is $n$ and $m$, with probability $1-\delta$,
$\operatorname{MMD}(\operatorname{\mathbb{P}}_{\hat{\operatorname{\bm{\theta}}}^{(n,m)}}||\operatorname{\mathbb{Q}})\leq\inf_{\operatorname{\bm{\theta}}\in\bm{\Theta}}\operatorname{MMD}(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}||\operatorname{\mathbb{Q}})+2\sqrt{\frac{2}{n}+\frac{2}{m}}\sqrt{\sup_{\bm{x}\in\mathcal{X}}k(\bm{x},\bm{x})}(2+\sqrt{\frac{2}{\delta}})$.

The calculation of $\mathfrak{R}^{C}$. Recall the definition of
$\hat{\operatorname{\bm{\theta}}}^{(n,m)}$ in Eq. (4). Let us first rewrite
the generalization error as

$\displaystyle\mathfrak{R}^{C}=$
$\displaystyle\operatorname{MMD}^{2}(\operatorname{\mathbb{P}}_{\hat{\operatorname{\bm{\theta}}}^{(n,m)}}||\operatorname{\mathbb{Q}})-\inf_{\operatorname{\bm{\theta}}\in\bm{\Theta}}\operatorname{MMD}^{2}(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}||\operatorname{\mathbb{Q}})$
$\displaystyle=$
$\displaystyle\left(\operatorname{MMD}(\operatorname{\mathbb{P}}_{\hat{\operatorname{\bm{\theta}}}^{(n,m)}}||\operatorname{\mathbb{Q}})-\inf_{\operatorname{\bm{\theta}}\in\bm{\Theta}}\operatorname{MMD}(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}||\operatorname{\mathbb{Q}})\right)$
$\displaystyle\times\left(\operatorname{MMD}(\operatorname{\mathbb{P}}_{\hat{\operatorname{\bm{\theta}}}^{(n,m)}}||\operatorname{\mathbb{Q}})+\inf_{\operatorname{\bm{\theta}}\in\bm{\Theta}}\operatorname{MMD}(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}||\operatorname{\mathbb{Q}})\right)$
$\displaystyle\leq$ $\displaystyle
2C_{1}\left|\operatorname{MMD}(\operatorname{\mathbb{P}}_{\hat{\operatorname{\bm{\theta}}}^{(n,m)}}||\operatorname{\mathbb{Q}})-\inf_{\operatorname{\bm{\theta}}\in\bm{\Theta}}\operatorname{MMD}(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}||\operatorname{\mathbb{Q}})\right|,$

where the second equality uses
$\inf_{\operatorname{\bm{\theta}}\in\bm{\Theta}}\operatorname{MMD}^{2}(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}||\operatorname{\mathbb{Q}})=(\inf_{\operatorname{\bm{\theta}}\in\bm{\Theta}}\operatorname{MMD}(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}||\operatorname{\mathbb{Q}}))^{2}$
and the inequality employs the
$\operatorname{MMD}(\operatorname{\mathbb{P}}_{\hat{\operatorname{\bm{\theta}}}^{(n,m)}}||\operatorname{\mathbb{Q}})+\inf_{\operatorname{\bm{\theta}}\in\bm{\Theta}}\operatorname{MMD}(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}||\operatorname{\mathbb{Q}})\leq
2\operatorname{MMD}(\operatorname{\mathbb{P}}_{\hat{\operatorname{\bm{\theta}}}^{(n,m)}}||\operatorname{\mathbb{Q}})\leq
2C_{1}$.

In conjunction with the above equation with the results of Lemma 2, we obtain
that with probability at least $1-\delta$, the upper bound of the
generalization error of QGCM yields

$\mathfrak{R}^{C}\leq
4C_{1}\left(\frac{2}{n}+\sqrt{\frac{2}{m}}\right)\sqrt{\sup_{x\in\mathcal{X}}k(\bm{x},\bm{x})}\left(2+\sqrt{\log\frac{2}{\delta}}\right).$
(9)

The calculation of $\mathfrak{R}^{Q}$. Recall the definition of
$\hat{\operatorname{\bm{\theta}}}$ in Eq. (3). When QCBM adopts the quantum
kernel and the target distribution $\operatorname{\mathbb{Q}}$ can be directly
accessed by quantum machines, the minimum argument of the loss function yields
$\hat{\operatorname{\bm{\theta}}}=\arg\min_{\operatorname{\bm{\theta}}\in\bm{\Theta}}\operatorname{MMD}^{2}(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}||\operatorname{\mathbb{Q}})$.
Following the definition of the generalization error, we obtain

$\displaystyle\mathfrak{R}^{Q}=$
$\displaystyle\operatorname{MMD}^{2}(\operatorname{\mathbb{P}}_{\hat{\operatorname{\bm{\theta}}}}||\operatorname{\mathbb{Q}})-\inf_{\operatorname{\bm{\theta}}\in\bm{\Theta}}\operatorname{MMD}^{2}(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}||\operatorname{\mathbb{Q}})$
(10)
$\displaystyle\leq\operatorname{MMD}^{2}(\operatorname{\mathbb{P}}_{\hat{\operatorname{\bm{\theta}}}^{(n,m)}}||\operatorname{\mathbb{Q}})-\inf_{\operatorname{\bm{\theta}}\in\bm{\Theta}}\operatorname{MMD}^{2}(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}||\operatorname{\mathbb{Q}})$
$\displaystyle=\mathfrak{R}^{C},$

where the inequality is supported by the definition of
$\hat{\operatorname{\bm{\theta}}}$, i.e,
$\operatorname{MMD}^{2}(\operatorname{\mathbb{P}}_{\hat{\operatorname{\bm{\theta}}}}||\operatorname{\mathbb{Q}})=\min_{\operatorname{\bm{\theta}}\in\bm{\Theta}}\operatorname{MMD}^{2}(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}||\operatorname{\mathbb{Q}})\leq\operatorname{MMD}^{2}(\operatorname{\mathbb{P}}_{\hat{\operatorname{\bm{\theta}}}^{(n,m)}}||\operatorname{\mathbb{Q}})$.

Combining the results of $\mathfrak{R}^{C}$ and $\mathfrak{R}^{Q}$ in Eqs. (9)
and (10), we obtain that with probability at least $1-\delta$,

$\mathfrak{R}^{Q}\leq\mathfrak{R}^{C}\leq
4C_{1}\left(\frac{2}{n}+\sqrt{\frac{2}{m}}\right)\sqrt{\sup_{x\in\mathcal{X}}k(\bm{x},\bm{x})}\left(2+\sqrt{\log\frac{2}{\delta}}\right).$

∎

It indicates that when $\operatorname{\mathbb{Q}}$ is quantum, quantum kernels
promise a strictly lower generalization error than classical kernels.
Moreover, the decisive factor to improve generalization of QCBMs is to
simultaneously increase $n$ and $m$. Note that this phenomenon results into a
tradeoff between the generalization and the runtime efficiency for QCBM with
classical kernels. That is, increasing $n$ and $m$ enables the reduced
generalization error but increases the runtime cost to compute
$\operatorname{MMD}_{U}^{2}(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}^{n}||\operatorname{\mathbb{Q}}^{m})$,
which echoes with the claim in hinsche2021learnability . Conversely, QCBM with
quantum kernels can simultaneously obtain both the good generalization and
runtime efficacy, supported by Lemma 1. We remark that this statement does not
contradict with the result in hinsche2021learnability , since our setting does
not require the statistical query access. Instead, our results show that a
careful design of learning strategies and model constructions can enhance the
power of QCBMs to advance GLMs, especially when $\operatorname{\mathbb{Q}}$
refers to the tasks in quantum many body physics and quantum information
processing huang2021quantum .

Remark. In SM C, we partially address another long standing problem of quantum
probabilistic models, i.e., whether QCBMs are superior to classical GLMs.
Briefly, for certain $\operatorname{\mathbb{Q}}$, QCBMs can attain a lower
$\inf_{\operatorname{\bm{\theta}}\in\bm{\Theta}}\operatorname{MMD}^{2}(\operatorname{\mathbb{P}}_{\bm{\theta}}||\operatorname{\mathbb{Q}})$
over restricted Boltzmann machine hinton2012practical , which may lead to a
better learnability.

##  III Generalization of QGAN

We next analyze the generalization of QGANs for continuous
$\operatorname{\mathbb{Q}}$. As shown in Fig. 1(b), QGAN adopts an $N$-qudit
Ansatz $\hat{U}(\operatorname{\bm{\theta}})$ in Eq. (2) to build a generator
$G_{\bm{\theta}}(\cdot)$, which maps $\bm{z}$ sampled from a prior
distribution $\operatorname{\mathbb{P}}_{\mathcal{Z}}$ to a generated example
$\bm{x}\sim\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}$, i.e.,
$\bm{x}:=G_{\bm{\theta}}(\bm{z})\in\mathbb{R}^{d^{N}}$. The $j$-th entry of
$\bm{x}$ is

$\bm{x}_{j}=\operatorname{Tr}(\Pi_{j}\hat{U}(\bm{\theta})\rho_{\bm{z}}\hat{U}(\bm{\theta})^{\dagger}),~{}\forall
j\in[d^{N}],$ (11)

where $\rho_{\bm{z}}$ refers to the encoded quantum state of $\bm{z}$. Given
$n$ reference examples $\\{\bm{x}^{(i)}\\}_{i=1}^{n}$ produced by
$G_{\bm{\theta}}(\cdot)$, its empirical distribution is
$\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}^{n}(d\bm{x})=\sum_{i=1}^{n}\delta_{\bm{x}^{(i)}}(d\bm{x})/n$.
Similarly, we define $\operatorname{\mathbb{Q}}^{m}$ as the empirical
distribution of $\operatorname{\mathbb{Q}}$ with $m$ true examples. In the
training process, QGAN updates $\operatorname{\bm{\theta}}$ to minimize the
empirical MMD loss in Eq. (4), i.e., the optimal solution satisfies
$\operatorname{\bm{\theta}}^{*}=\arg\min\operatorname{MMD}_{U}^{2}(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}^{n}||\operatorname{\mathbb{Q}}^{m})$.
Note that QGANs can be applied to estimate both discrete and continuous
distributions. When $\operatorname{\mathbb{Q}}$ is discrete, the mechanism of
QGANs is equivalent to QCBMs (refer to SM A & B for more elaborations about
QGANs). Due to this reason, here we only focus on applying QGANs to estimate
the continuous distribution $\operatorname{\mathbb{Q}}$.

When QGANs in Eq. (11) are designed to estimate the continuous distribution
$\operatorname{\mathbb{Q}}$, their generalization can only be measured by
$\mathfrak{R}^{C}$ in Definition 1. In this scenario, it is of paramount
importance of unveiling how the generalization of QGANs depends on uploading
methods and the structure information Ansatz. The following theorem makes a
concrete step toward this goal.

######  Theorem 2.

Assume the kernel $k(\cdot,\cdot)$ is $C_{3}$-Lipschitz. Suppose that the
employed quantum circuit $\hat{U}(\bm{z})$ to prepare $\rho_{\bm{z}}$
containing in total $N_{ge}$ parameterized gates and each gate acting on at
most $k$ qudits. Following notations in Eqs. (4) and (6), with probability at
least $1-\delta$, the generalization error of QGANs, $\mathfrak{R}^{C}$ in Eq.
(11) is upper bounded by

$8\sqrt{\frac{8C_{2}^{2}(n+m)}{nm}\ln\frac{1}{\delta}}+\frac{48}{n-1}+\frac{144d^{k}\sqrt{N_{gt}+N_{ge}}}{n-1}C_{4},$
(12)

where $C_{2}=\sup_{\bm{x}}k(\bm{x},\bm{x})$,
$C_{4}=N\ln(441dC_{3}^{2}nN_{ge}N_{gt})+1$.

###### Proof sketch.

Here we only deliver the central idea and postpone the whole proof to SM D.

For clearness, we denote $\hat{\operatorname{\bm{\theta}}}^{(n,m)}$ as
$\hat{\operatorname{\bm{\theta}}}$. Define
$\mathcal{E}(\operatorname{\bm{\theta}})=\operatorname{MMD}_{U}^{2}(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}^{n}||\operatorname{\mathbb{Q}}^{m})$
and
$\mathcal{T}(\operatorname{\bm{\theta}})=\operatorname{MMD}^{2}(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}||\operatorname{\mathbb{Q}})$.
Then the generalization error is upper bounded by

$\displaystyle\mathfrak{R}^{C}=$
$\displaystyle\mathcal{E}(\hat{\operatorname{\bm{\theta}}})-\mathcal{E}(\hat{\operatorname{\bm{\theta}}})+\mathcal{T}(\hat{\operatorname{\bm{\theta}}})-\mathcal{T}(\operatorname{\bm{\theta}}^{*})$
$\displaystyle\leq$
$\displaystyle|\mathcal{T}(\hat{\operatorname{\bm{\theta}}})-\mathcal{E}(\hat{\operatorname{\bm{\theta}}})|+|\mathcal{T}(\operatorname{\bm{\theta}}^{*})-\mathcal{E}(\operatorname{\bm{\theta}}^{*})|,$
(13)

where the first inequality employs the definition of
$\hat{\operatorname{\bm{\theta}}}$ with
$\mathcal{E}(\operatorname{\bm{\theta}}^{*})\geq\mathcal{E}(\hat{\operatorname{\bm{\theta}}})$
and the second inequality uses the property of absolute value function. In
this regard, we derive the probability for
$\sup_{\operatorname{\bm{\theta}}\in\Theta}|\mathcal{T}(\operatorname{\bm{\theta}})-\mathcal{E}(\operatorname{\bm{\theta}})|<\epsilon$,
which in turn can achieve the upper bound of $\mathfrak{R}^{C}$.

According to the explicit form of the MMD loss and Jensen inequality,
$\sup_{\operatorname{\bm{\theta}}\in\bm{\Theta}}|\mathcal{E}(\operatorname{\bm{\theta}})-\mathcal{T}(\operatorname{\bm{\theta}})|$
satisfies

$\displaystyle\sup_{\operatorname{\bm{\theta}}\in\bm{\Theta}}\left|\operatorname{MMD}_{U}^{2}(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}^{n}||\operatorname{\mathbb{Q}}^{m})-\operatorname{MMD}^{2}(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}||\operatorname{\mathbb{Q}})\right|$
$\displaystyle\leq$
$\displaystyle\underbrace{\sup_{\operatorname{\bm{\theta}}\in\bm{\Theta}}\Big{|}\operatorname{\mathbb{E}}_{\bm{y},\bm{y}^{\prime}}(k(\bm{y},\bm{y}^{\prime}))-\frac{\sum_{j\neq
j^{\prime}}k(\bm{y}^{(j)},\bm{y}^{(j^{\prime})})}{m(m-1)}\Big{|}}_{T1}$
$\displaystyle+$
$\displaystyle\underbrace{\sup_{\operatorname{\bm{\theta}}\in\bm{\Theta}}\Big{|}\operatorname{\mathbb{E}}_{\bm{z},\bm{z}^{\prime}}(k(G_{\operatorname{\bm{\theta}}}(\bm{z}),G_{\operatorname{\bm{\theta}}}(\bm{z}^{\prime})))-\frac{\sum_{i\neq
i^{\prime}}k(G_{\operatorname{\bm{\theta}}}(\bm{z}^{(i)}),G_{\operatorname{\bm{\theta}}}(\bm{z}^{(i^{\prime})}))}{n(n-1)}\Big{|}}_{T2}$
$\displaystyle+$ $\displaystyle
2\underbrace{\sup_{\operatorname{\bm{\theta}}\in\bm{\Theta}}\Big{|}\operatorname{\mathbb{E}}_{z,y}(k(G_{\operatorname{\bm{\theta}}}(\bm{z}),\bm{y}))-\frac{\sum_{i\in[n],j\in[m]}k(G_{\operatorname{\bm{\theta}}}(\bm{z}^{(i)}),\bm{y}^{(j)})}{mn}\Big{|}}_{T3}.$

In other words, to upper bound $\mathfrak{R}^{C}$, we should separately derive
the upper bounds of the terms $T1$, $T2$, and $T3$. Specifically, supported by
concentration inequality mendelson2003few , we obtain with probability at
least $1-3\delta_{T3}$,

$\mathfrak{R}^{C}\leq 2(\epsilon_{1}+2\epsilon_{2}+4\epsilon),$ (14)

where $\epsilon=\sqrt{\frac{8C^{2}(n+m)}{nm\log 1/\delta_{T3}}}$,
$\epsilon_{1}=\operatorname{\mathbb{E}}(T2)$, and
$\epsilon_{2}=\operatorname{\mathbb{E}}(T3)$.

The above inequality indicates that the generalization error of QGAN depends
on $\epsilon_{1}$ and $\epsilon_{2}$. Namely, by leveraging the covering
number—a tool developed in statistical learning theory, we prove
$\epsilon_{1}\leq\frac{8}{n-1}+\frac{24\sqrt{d^{2k}(N_{ge}+N_{gt})}}{n-1}\left(1+N\ln(441dC_{3}^{2}(n-1)N_{ge}N_{gt})\right)$
and
$\epsilon_{2}\leq\frac{8}{n}+\frac{24\sqrt{d^{2k}(N_{ge}+N_{gt})}}{n}\left(1+N\ln(441dC_{3}^{2}nN_{ge}N_{gt})\right)$.
Taken together, with probability $1-3\delta_{T3}$, the generalization error of
QGANs is upper bounded by
$8\sqrt{\frac{8C_{2}^{2}(n+m)}{nm}\ln\frac{1}{\delta}}+\frac{48}{n-1}+\frac{144d^{k}\sqrt{N_{gt}+N_{ge}}}{n-1}C_{4}$.

∎

The results of Theorem 2 convey four-fold implications. First, according to
the first term in the right hand-side of Eq. (12), to achieve a tight upper
bound of $\mathfrak{R}^{C}$, the ratio between the number of examples sampled
from $\operatorname{\mathbb{Q}}$ and $\operatorname{\mathbb{P}}$ should
satisfy $m/n=1$. In this case, $\mathfrak{R}^{C}$ linearly decreases and
finally converges to zero with the increased $n$ or $m$. Second,
$\mathfrak{R}^{C}$ linearly depends on the kernel term $C_{2}$, exponentially
depends on $k$ in Eq. (2), and sublinearly depends on the number of trainable
quantum gates $N_{gt}$. These observations underpin the importance of
controlling the expressivity of the adopted Ansatz and selecting proper
kernels to ensure both the good learning performance and generalization of
QGANs. Third, the way of preparing $\rho_{\bm{z}}$ is a determinant factor in
generalization of QGANs, which implies the prior distribution
$\operatorname{\mathbb{P}}_{\mathcal{Z}}$ and the number of encoding gates
$N_{ge}$ should be carefully designed. Last, the explicit dependence on the
architecture of Ansatz connects the generalization of QGANs with their
trainability, i.e., a large $N_{gt}$ or $k$ may induce barren plateaus in
training QGLMs mcclean2018barren ; kieferova2021quantum  and results in an
inferior learning performance. Meanwhile, it also leads to a degraded
generalization error bound.

Remark. Most kernels such as RBF, linear, and Matérn kernels satisfy the
Lipchitz condition Lederer2019 . Meanwhile, Theorem 2 can be efficiently
extended to noisy settings by using the contraction properties of noisy
channels explained in Ref. du2021efficient .

The derived bound in Theorem 2 is succinct and can be directly employed to
quantify the generalization of QGANs with the specified Ansatz. The following
corollary quantifies $\mathfrak{R}^{C}$ of QGANs with two typical Ansätze in
VQAs, i.e., hardware-efficient Ansatz and quantum approximate optimization
Ansatz.

######  Corollay 1.

Following notations in Theorem 2, when QGAN is realized by the hardware-
efficient Ansatz and quantum approximate optimization Ansatz with $L$ layers,
$\mathfrak{R}^{C}$ is upper bounded by

$\tilde{\mathcal{O}}(C_{2}\sqrt{\frac{n+m}{(nm)}}+\frac{1}{n}+\frac{\sqrt{N(L_{E}+3L)}(N+1)}{n-1}),$

and

$\tilde{\mathcal{O}}(C_{2}\sqrt{\frac{(n+m)}{(nm)}}+\frac{1}{n-1}+\frac{2^{N}\sqrt{(N+1)(L+L_{E})}(N+1)}{n-1}).$

###### Proof of Corollary 1.

Here we separately analyze the generalization ability of QGANs with two
typical classes of Ansätze, i.e., the hardware-efficient Ansätze and the
quantum approximation optimization Ansätze.

Hardware-efficient Ansätze. An $N$-qubits hardware-efficient Ansatz is
composed of $L$ layers, i.e.,
$U(\bm{\theta})=\prod_{l=1}^{L}U(\bm{\theta}^{l})$ with $L\sim poly(N)$, where
$U(\bm{\theta}^{l})$ is composed of parameterized single-qubit gates and fixed
two-qubit gates. In general, the topology of $U(\bm{\theta}^{l})$ for any
$l\in[L]$ is the same and each qubit interacts with at least one parameterized
single-qubit gate and two qubits gates. Mathematically, we have
$U(\bm{\theta}^{l})=(\otimes_{i=1}^{N}U_{s})U_{eng}$ with
$U_{s}=R_{Z}(\beta)R_{Y}(\gamma)R_{Z}(\nu)$ being realized by three rotational
qubit gates and $\gamma,\beta,\nu\in[0,2\pi)$. The number of two-qubit gates
in each layer is set as $N$ and the connectively of two-qubit gates aims to
adapt to the topology restriction of quantum hardware. The entangled layer
$U_{eng}$ contains two-qubit gates, i.e., CNOT gates, whose connectivity
adapts the topology of the quantum hardware.

An example of $4$-qubit QGAN with hardware-efficient Ansatz is illustrated in
the upper panel of Fig. 2. Under this setting, when both the encoding unitary
and the trainable unitary adopt the hardware-efficient Ansatz, we have $k=2$,
$d=2$, $N_{ge}=L_{E}N$, $N_{gt}=L(3N)$, and $N_{g}=L(3N+N)=4L$. Based on the
above settings, we achieve the generalization error of ab $N$-qubit QGAN with
the hardware-efficient Ansätze, supported by Theorem 2, i.e., with probability
at least $1-\delta$,

$\displaystyle\mathfrak{R}^{C}\leq$ $\displaystyle
8\sqrt{\frac{8C_{2}^{2}(n+m)}{nm}\ln\frac{1}{\delta}}+\frac{48}{n-1}$
$\displaystyle+\frac{576\sqrt{N(L_{E}+3L)}}{n-1}(N\ln(1323dC_{3}^{2}nN^{2}L_{E}L)+1),$

where $C_{2}=\sup_{\bm{x}}k(\bm{x},\bm{x})$.

Figure 2: Illustration of QGANs with different Ansätze. The upper panel
presents that both the encoding method and the trainable unitary of QGANs
employ the hardware-efficient Ansätze. The lower panel presents a class of
QGANs such that the encoding method uses the hardware-efficient Ansätze and
the trainable unitary is implemented by the quantum approximate optimization
Ansätze.

Quantum approximate optimization Ansätze. The lower panel of Fig. 2 plots the
quantum approximate optimization Ansätze. The mathematical expression of this
Ansatz takes the form $U(\bm{\theta})=\prod_{l=1}^{L}U(\bm{\theta}^{l})$,
where the $l$-th layer
$U(\bm{\theta}^{l})=U_{B}(\bm{\theta}^{l})U_{C}(\bm{\theta}^{l})$ is
implemented by the driven Hamiltonian
$U_{B}(\bm{\theta}^{l})=\otimes_{i=1}^{N}R_{X}(\bm{\theta}^{l}_{i})$ and the
target Hamiltonian
$U_{C}(\bm{\theta}^{l})=\exp(-i\operatorname{\bm{\theta}}^{l}_{l+1}H_{C})$
with $H_{C}$ being a specified Hamiltonian. Under this setting, when the
encoding unitary is constructed by the hardware-efficient Ansatz and the
trainable unitary is realized by the quantum approximate optimization Ansatze,
we have $k=N$, $d=2$, $N_{ge}=L_{E}N$, and $N_{gt}=L(N+1)$. Based on the above
settings, we achieve the generalization error of an $N$-qubit QGAN with the
quantum approximate optimization Ansätze, supported by Theorem 2, i.e., with
probability at least $1-\delta$,

$\displaystyle\mathfrak{R}^{C}\leq$ $\displaystyle
8\sqrt{\frac{8C_{2}^{2}(n+m)}{nm}\ln\frac{1}{\delta}}+\frac{48}{n-1}$
$\displaystyle+\frac{144\times 2^{N}\sqrt{(N+1)(L+L_{E})}}{n-1}$
$\displaystyle\times(N\ln(441dC_{3}^{2}nLL_{E}N(N+1))+1),$

where $C_{2}=\sup_{\bm{x}}k(\bm{x},\bm{x})$. ∎

##  IV Applications of QGLMs with merits

A crucial message conveyed by Theorems 1 and 2 is that when
$\operatorname{\mathbb{Q}}\in\operatorname{\mathbb{P}}_{\bm{\Theta}}$, the
distance between the learned
$\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}$ and
$\operatorname{\mathbb{Q}}$ is continuously decreased by increasing $n$ and
$m$. This evidence contributes to theoretically study the merits of QGLMs in
many practical problems such as quantum state preparation and parameterized
Hamiltonian learning.

###  IV.1 Quantum state preparation

Quantum state preparation is a crucial subroutine in quantum computing and
quantum sensing, since its efficiency determines the achievable runtime
speedups of quantum machine learning and Hamiltonian simulation algorithms,
and improves the precision of the device. Nevertheless, theoretical results
indicate that exactly loading the generic discrete distribution with $d^{N}$
dimensions to an $N$-qudit state requests $O(d^{N})$ gates plesch2011quantum ;
zhang2022quantum , which prevents any merits. Moreover, there is no
deterministic method of encoding continuous distribution into the multi-qudit
system. QGLMs open the door to efficiently encode both discrete and continuous
distributions into quantum circuits with certain estimation error
zoufal2019quantum . Theorems 1 and 2 establish the theoretical foundation
about such an error. Specifically, for
$\operatorname{\mathbb{Q}}\in\operatorname{\mathbb{P}}_{\Theta}$, large
examples promise a low estimation error and the learned QGLM can be easily
realized and reused. For
$\operatorname{\mathbb{Q}}\notin\operatorname{\mathbb{P}}_{\Theta}$, the
estimation error could be considerable, even though $n$ and $m$ are infinite.
In this view, the power of QGLMs in quantum state preparation highly depends
on their expressivity.

###  IV.2 Parameterized Hamiltonian Learning

QGLMs may advance GLMs in parameterized Hamiltonian learning (PHL). Define an
$N$-qubit parameterized Hamiltonian as $H(\bm{a})$ and the corresponding
ground state as $\ket{\phi(\bm{a})}$, where $\bm{a}$ is the interaction
parameter sampled from a prior distribution $\mathbb{D}$. PHL aims to use $m$
training samples $\\{\bm{a}^{(i)},\ket{\phi(\bm{a}^{(i)})}\\}_{i=1}^{m}$ to
approximate the distribution of the ground states for $H(\bm{a})$ with
$\bm{a}\sim\mathbb{D}$, i.e.,
$\ket{\phi(\bm{a})}\sim\operatorname{\mathbb{Q}}$. If the estimation error is
low, then the trained model can prepare the ground state of
$H(\bm{a}^{\prime})$ for an unseen parameter $\bm{a}^{\prime}\sim\mathbb{D}$.
This property can be used to explore many crucial behaviors in condensed-
matter systems. Concisely, there exists an $N$-qubit Hamiltonian $H(\bm{a})$
and a distribution $\mathbb{D}$ such that the formed ground state distribution
$\operatorname{\mathbb{Q}}$ can be efficiently estimated by QGLMs with
$O(poly(N))$ trainable parameters but is computational hardness for GLMs with
$O(poly(N))$ trainable parameters.

Figure 3: Simulation results of QCBM. (a) The implementation of QCBMs when
$N=6$. The label ‘$L_{1}-1$’ refers to repeating the architecture highlighted
by the brown color $L_{1}-1$ times. The gate
$U(\operatorname{\bm{\theta}}_{i}^{l})$ refers to the $\operatorname{R_{Y}}$
gate applied on the $i$-th qubit in the $l$-th layer of Ansatz
$\hat{U}(\operatorname{\bm{\theta}})$. (b) The visualization of a two-qubit
GHZ state. (c) The upper and lower panels separately show the simulation
results of QCBMs in the task of estimating the discrete Gaussian distribution
when $N=8$ and $N=12$. The labels ‘$\operatorname{\mathbb{Q}}$’,
$\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}^{Q}$,
‘$\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}^{G},n$’, stand for
the target distribution, the output of QCBM with the quantum kernel, and the
output of QCBM with the RBF kernel and $n$ samples, respectively. The inner
plots evaluate the statistical performance of QCBM through KL divergence,
where the x-axis labels the number of examples $n$. (d) The four box-plots
separately show the simulation results of QCBM in the task of approximating
$N$-qubit GHZ state with $N=4,6,8,10$. The y-axis refers to the fidelity. The
x-axis refers to the applied kernels in QCBM, where the label ‘$Q$’ represents
the quantum kernel and the rest four labels refers to the RBF kernel with $n$
samples.

The separated power between QGLMs and GLMs relies on the following lemma.

######  Lemma 3.

Suppose that $\operatorname{\mathbb{Q}}$ refers to the distribution of the
ground states for parameterized Hamiltonians $H(\bm{a})$ with
$\bm{a}\sim\mathbb{D}$. Under the quantum threshold assumption, there exists a
distribution $\operatorname{\mathbb{Q}}$ that can be efficiently represented
by QGLMs but is computationally hard for GLMs.

###### Proof sketch.

The proof is provided in SM E. Conceptually, the proof is established on the
results of quantum random circuits, which is widely believed to be classically
computationally hard and in turn can be used to demonstrate quantum advantages
on NISQ devices boixo2018characterizing ; zhu2021quantum . Namely, Ref.
aaronson2017complexity  proposed a Heavy Output Generation (HOG) problem to
separate the power between classical and quantum computers. That is, under the
quantum threshold assumption, there do not exist classical samples that can
spoof the $k$ samples output by a random quantum circuit with success
probability at least $0.99$ aaronson2017complexity , while quantum computers
can solve the HOG problem with high success probability.

Based on this observation, we connect $\ket{\phi(\bm{a})}$ with the output
state of random quantum circuits. To this end, we prove that there exists a
ground state $\ket{\phi(\bm{a})}$ of a Hamiltonian $H(\bm{a})$, which can be
efficiently prepared by quantum computers but is computationally hard for
classical algorithms. ∎

It indicates that in PHL, the expressivity of QGLMs outperforms GLMs with
$\operatorname{\mathbb{Q}}\in\operatorname{\mathbb{P}}_{\bm{\Theta}}^{Q}$ and
$\operatorname{\mathbb{Q}}\notin\operatorname{\mathbb{P}}_{\bm{\Theta}}^{C}$.
When the number of trainable parameters of QGLMs scales with $O(poly(N))$,
there may exist a kernel leading to
$\inf_{\bm{\theta}\in\bm{\Theta}}\operatorname{MMD}^{2}(\operatorname{\mathbb{P}}_{\bm{\theta}}^{Q}||\operatorname{\mathbb{Q}})\rightarrow
0$. Considering that $\operatorname{\mathbb{P}}_{\bm{\theta}}^{Q}$ and
$\operatorname{\mathbb{Q}}$ are intractable, the training of QGANs amounts to
minimizing
$\operatorname{MMD}_{U}^{2}(\operatorname{\mathbb{P}}_{\bm{\theta}}^{Q}||\operatorname{\mathbb{Q}})$.
Theorems 1 and 2 imply that when the empirical loss tends to zero and $n$ and
$m$ are sufficient large, the generalization error vanishes and thus the
estimated distribution recovers the target distribution with
$\operatorname{\mathbb{P}}_{\bm{\theta}^{(n,m)}}^{Q}\approx\operatorname{\mathbb{P}}_{\bm{\theta}}^{Q}\approx\operatorname{\mathbb{Q}}$.
Conversely, the result
$\operatorname{\mathbb{Q}}\notin\operatorname{\mathbb{P}}_{\bm{\Theta}}^{C}$
for GLMs means that even though the empirical loss and the generalization
error are zero, the estimated distribution
$\operatorname{\mathbb{P}}_{\bm{\theta}^{(n,m)}}^{C}$ fails to recover
$\operatorname{\mathbb{Q}}$.

##  V Numerical simulations

In this section, we apply QCBMs and QGANs to accomplish the distribution
preparation and quantum state approximation tasks. More implementation details
and simulation results are deferred to SM F.

###  V.1 Gaussian distribution preparation by QCBM

The first task is applying QCBMs to prepare the discrete Gaussian distribution
$\mathsf{N}(N,\mu,\sigma)$, where $N$ specifies the range of events with
$\bm{x}\in[2^{N}]$, and $\mu$ and $\sigma$ refer to the mean and variance,
respectively. An intuition of $\mathsf{N}(N,\mu,\sigma)$ is shown in Fig.
3(c), labeled by $\operatorname{\mathbb{Q}}$. The hyper-parameter settings are
as follows. For all simulations, we fix $\mu=1$ and $\sigma=8$. The qubit
count is set as $N=12$. The hardware-efficient Ansatze is employed to
construct QCBM with $L_{1}=8$ for $N=8$ ($L_{1}=12$ for $N=12$). An intuition
is in illustrated in Fig. 3(a). The quantum kernel and RBF kernel are adopted
to compute the MMD loss. For RBF kernel, the number of samples is set as
$n=100$, $1000$, and $\infty$. The maximum number of iterations is $T=50$. For
each setting, we repeat the training $5$ times to collect the statistical
results.

Figure 4: Simulation results of QGANs. (a) The implementation of QGANs when
the number of qubits is $N=3$. $U(\bm{z})$ refers to the encoding circuit to
load the example $\bm{z}$. The meaning of ‘$L_{1}-1$’ is identical to the one
explained in Fig. 1. The gate $U(\operatorname{\bm{\theta}}_{i}^{l})$ refers
to the $\operatorname{R_{Y}}\operatorname{R_{Z}}$ gates applied on the $i$-th
qubit in the $l$-th layer of $\hat{U}(\operatorname{\bm{\theta}})$. (b) The
outer plot shows the training loss of QGANs with varied settings of $m$. The
x-axis refers to the number of iterations. The inner plot shows the
generalization property of trained QGANs by evaluating MMD loss. (c) The
visualization of the exploited 3D Gaussian distribution. The label
‘$X_{a}$-$X_{b}$’ means projects the 3D Gaussian into the $X_{a}$-$X_{b}$
plane with $a,b$ belonging to x, y, z-axis. (d) The generated data sampled
from the trained QGAN with varied settings of $m$. From upper to lower panel,
$m$ equals to $2$, $10$, and $200$, respectively.

The simulation results of QCBMs are illustrated in Fig. 3(c). The two outer
plots exhibit the approximated distributions under different settings. In
particular, for both $N=8,12$, the approximated distribution generated by QCBM
with the quantum kernel well approximates $\operatorname{\mathbb{Q}}$. In the
measure of KL divergence, the similarity of these two distributions is $0.18$
and $1.6$ for $N=8,12$, respectively. In contrast, when the adopted kernels
are classical and the number of measurements is finite, QCBMs encounter the
inferior performance. Namely, by increasing $n$ and $m$ from $50$ to $1000$,
the KL divergence between the approximated distribution and the target
distribution only decreases from $1.28$ to $0.59$ in the case of $N=8$.
Moreover, under the same setting, the KL divergence does not manifestly
decrease when $N=12$, which requires a larger $n$ and $m$ to attain a good
approximation as suggested by Theorem 1. This argument is warranted by the
numerical results with the setting $n=m\rightarrow\infty$, where the achieved
KL divergence is comparable with QCBM with the quantum kernel. Nevertheless,
the runtime complexity of QCBMs with the classical kernel polynomially scales
with $n$ and $m$. According to Lemma 1, under this scenario, QCBMs with the
quantum kernel embraces the runtime advantages.

###  V.2 GHZ state approximation by QCBM

We apply QCBMs to accomplish the task of preparing GHZ states, a.k.a., “cat
states” nielsen2010quantum . An intuition is depicted in Fig. 3(b). The choice
of GHZ states is motivated by their importance in quantum information. The
formal expression of an $N$-qubit GHZ state is
$\ket{\operatorname{\text{GHZ}}}=(\ket{0}^{\otimes N}+\ket{1}^{\otimes
N})/\sqrt{2}$. The hyper-parameter settings are as follows. The number of
qubits is set as $N=6,8,10$ and the corresponding depth is $L_{1}=4,6,8,10$.
The quantum kernel and RBF kernel are adopted to compute the MMD loss. For RBF
kernel, the number of samples is set as $n=100$, $1000$, and $\infty$. The
maximum number of iterations is $T=50$. For each setting, we repeat the
training $5$ times to get a better understanding of the robustness of the
results. The other settings are identical to those used in the task of
preparing Gaussian distributions.

The simulation results, as illustrated in Fig. 3(d), indicate that QCBMs with
quantum kernels outperforms RBF kernels when $n$ and $m$ are finite. This
observation becomes apparent with an increased $N$. For all settings of $N$,
the averaged fidelity between the generated states of QCBMs with the quantum
kernel and the target $\ket{\operatorname{\text{GHZ}}}$ is above $0.99$,
whereas the obtained averaged fidelity for QCBMs with the RBF kernel is $0.46$
for $N=10$ and $n=m=100$. Meanwhile, as with the prior task, RBF kernel attain
a competitive performance with the quantum kernel unless
$n=m\rightarrow\infty$, while the price to pay is an unaffordable
computational overhead.

###  V.3 3D-correlated Gaussian preparation by QGAN

The last tasks is using QGANs to prepare 3D correlated Gaussian distributions
with varied settings. The target distribution $\operatorname{\mathbb{Q}}$ is a
3D correlated Gaussian distribution centered at $\mu=(0,0,0)$ with covariance
matrix $\sigma=\big{(}\begin{smallmatrix}0.5&1&0.25\\\ 0.1&0.5&0.1\\\
0.25&0.1&0.5\end{smallmatrix}\big{)}$. The sampled examples from
$\operatorname{\mathbb{Q}}$ are visualized in Fig. 4(a). Here we use a variant
of the style-QGAN proposed by bravo2021style  to accomplish the task. Two key
modifications in our protocol are constructing the quantum generator and
replacing the trainable discriminator by MMD loss. Different from the original
proposal applying the re-uploading method, the modified quantum generator
first uploads the prior example $\bm{z}$ using $U(\bm{z})$ followed by the
Ansatz $U(\operatorname{\bm{\theta}})$. Such a modification facilitates the
analysis of the generalization behavior of QGANs as claimed in Theorem 2. The
hyper-parameter settings are as follows. The number of reference samples $n$
ranges from $2$ to $200$ and we keep $n=m$. The layer depth of
$G_{\operatorname{\bm{\theta}}}(\cdot)$ is set as $L\in\\{2,4,6,8\\}$. Each
setting is repeated with $5$ times to collect the statistical results.

The simulation results are exhibited in Figs. 4(b)-(c). For illustration, we
depicts the generated distribution of the trained QGANs in Fig. 4(b). With
increasing $m$, the learned distribution is close to the real distribution.
The outer plot in Fig. 4(c) shows that for all settings of $m$, the empirical
$\operatorname{MMD}$ loss, i.e.,
$\operatorname{MMD}_{U}(\operatorname{\mathbb{P}}_{\hat{\operatorname{\bm{\theta}}}^{(n,m)}}^{n}||\operatorname{\mathbb{Q}}^{m})$,
converges after $60$ iterations, where the averaged loss is $0.0114$,
$0.0077$, and $0.0054$ for $m=2,10,200$, respectively. The inner plot measures
the expected $\operatorname{MMD}$ loss, i.e., the trained QGANs are employed
to generate new $10000$ examples and then evaluate $\operatorname{MMD}_{U}$ to
estimate $\operatorname{MMD}$. The averaged expected $\operatorname{MMD}$ loss
for $m=2,10,200$ is $0.1178$, $0.0122$, and $0.0041$ respectively. These
observations echo with Theorem 2, where a large $m$ allows a better
generalization ability.

##  VI Discussions

We provide a succinct and direct way to compare generalization of QGLMs with
different Ansätze, which deepens our understanding about the capabilities of
QGLMs and benefit the design of advanced QGLMs. For QCBMs, Theorem 1 unveils
that quantum kernels can greatly benefit their generalization and reduce
computational overhead over classical kernels when the target distribution is
quantum. Theorem 2 hints that the generalization error of QGANs has the
explicit dependence on the qudits count, the structure information of the
employed Ansätze, the adopted encoding method, and the choice of prior
distribution. These results suggest that a possible way to enhance the
learning performance of QGLMs is devising novel Ansätze via quantum circuit
architecture design techniques amaro2022filtering ; bilkis2021semi ;
du2020quantum ; linghu2022quantum ; kuo2021quantum ; zhang2020differentiable .
Although the attained theoretical results do not exhibit the generic
exponential advantages of QGLMs, we clearly show that their potentials in
quantum state preparation and parameterized Hamiltonian learning.

The developed techniques in this study are general and provide a novel
approach to theoretically investigate the power of QGLMs. For instance, a
promising direction is uncovering the generalization of other QGLMs.
Furthermore, it is intriguing to explore the generalization of QGLMs with
other loss functions briol2019statistical ; chakrabarti2019quantum . Another
important future direction will be identifying how to use QGLMs to gain
substantial quantum advantages for practical applications, e.g., quantum many
body physics, quantum sensing, and quantum information processing. Last, the
entangled relation between expressivity and generalization in QGLMs queries a
deeper understanding from each side.

## References

  * (1) Merlin C Wittrock.  Generative processes of comprehension.  Educational psychologist, 24(4):345–376, 1989.
  * (2) Yann LeCun, Yoshua Bengio, and Geoffrey Hinton.  Deep learning.  nature, 521(7553):436, 2015.
  * (3) Jürgen Schmidhuber.  Deep learning in neural networks: An overview.  Neural Networks, 61:85–117, 2015.
  * (4) Peter Dayan, Geoffrey E Hinton, Radford M Neal, and Richard S Zemel.  The helmholtz machine.  Neural computation, 7(5):889–904, 1995.
  * (5) Diederik P. Kingma and Max Welling.  Auto-encoding variational bayes.  In Yoshua Bengio and Yann LeCun, editors, 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014.
  * (6) Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial nets.  In Advances in neural information processing systems, pages 2672–2680, 2014.
  * (7) Junbo Zhao, Michael Mathieu, and Yann LeCun.  Energy-based generative adversarial networks.  In 5th International Conference on Learning Representations, ICLR 2017, 2017.
  * (8) Ran Yi, Yong-Jin Liu, Yu-Kun Lai, and Paul L Rosin.  APDrawingGAN: Generating artistic portrait drawings from face photos with hierarchical gans.  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR ’19), pages 10743–10752, 2019.
  * (9) Tero Karras, Samuli Laine, and Timo Aila.  A style-based generator architecture for generative adversarial networks.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4401–4410, 2019.
  * (10) Taesung Park, Ming-Yu Liu, Ting-Chun Wang, and Jun-Yan Zhu.  Semantic image synthesis with spatially-adaptive normalization.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2337–2346, 2019.
  * (11) Karim Armanious, Chenming Jiang, Marc Fischer, Thomas Küstner, Tobias Hepp, Konstantin Nikolaou, Sergios Gatidis, and Bin Yang.  Medgan: Medical image translation using gans.  Computerized Medical Imaging and Graphics, 79:101684, 2020.
  * (12) Łukasz Maziarka, Agnieszka Pocha, Jan Kaczmarczyk, Krzysztof Rataj, Tomasz Danel, and Michał Warchoł.  Mol-cyclegan: a generative model for molecular optimization.  Journal of Cheminformatics, 12(1):1–18, 2020.
  * (13) Oscar Méndez-Lucio, Benoit Baillif, Djork-Arné Clevert, David Rouquié, and Joerg Wichard.  De novo generation of hit-like molecules from gene expression signatures using artificial intelligence.  Nature communications, 11(1):1–10, 2020.
  * (14) Shahnawaz Ahmed, Carlos Sánchez Muñoz, Franco Nori, and Anton Frisk Kockum.  Quantum state tomography with conditional generative adversarial networks.  Physical Review Letters, 127(14):140502, 2021.
  * (15) Juan Carrasquilla, Giacomo Torlai, Roger G Melko, and Leandro Aolita.  Reconstructing quantum states with generative models.  Nature Machine Intelligence, 1(3):155–161, 2019.
  * (16) Alistair WR Smith, Johnnie Gray, and MS Kim.  Efficient quantum state sample tomography with basis-dependent neural networks.  PRX Quantum, 2(2):020348, 2021.
  * (17) Andrea Rocchetto, Edward Grant, Sergii Strelchuk, Giuseppe Carleo, and Simone Severini.  Learning hard quantum distributions with variational autoencoders.  npj Quantum Information, 4(1):1–7, 2018.
  * (18) Roger G Melko, Giuseppe Carleo, Juan Carrasquilla, and J Ignacio Cirac.  Restricted boltzmann machines in quantum physics.  Nature Physics, 15(9):887–892, 2019.
  * (19) Giuseppe Carleo, Yusuke Nomura, and Masatoshi Imada.  Constructing exact representations of quantum many-body systems with deep neural networks.  Nature communications, 9(1):1–11, 2018.
  * (20) Yilun Du and Igor Mordatch.  Implicit generation and modeling with energy based models.  In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
  * (21) Alexey Dosovitskiy and Thomas Brox.  Generating images with perceptual similarity metrics based on deep networks.  Advances in neural information processing systems, 29:658–666, 2016\.
  * (22) Sanjeev Arora, Andrej Risteski, and Yi Zhang.  Do GANs learn the distribution? some theory and empirics.  In International Conference on Learning Representations, 2018.
  * (23) Tong Che, Yanran Li, Athul Paul Jacob, Yoshua Bengio, and Wenjie Li.  Mode regularized generative adversarial networks.  arXiv preprint arXiv:1612.02136, 2016.
  * (24) Lars Mescheder, Andreas Geiger, and Sebastian Nowozin.  Which training methods for gans do actually converge?  In International conference on machine learning, pages 3481–3490. PMLR, 2018.
  * (25) Jie Gui, Zhenan Sun, Yonggang Wen, Dacheng Tao, and Jieping Ye.  A review on generative adversarial networks: Algorithms, theory, and applications.  IEEE Transactions on Knowledge and Data Engineering, 2021.
  * (26) Richard P Feynman.  Quantum mechanical computers.  Between Quantum and Cosmos, pages 523–548, 2017.
  * (27) Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd.  Quantum machine learning.  Nature, 549(7671):195, 2017.
  * (28) Aram W Harrow and Ashley Montanaro.  Quantum computational supremacy.  Nature, 549(7671):203, 2017.
  * (29) Xun Gao, Z-Y Zhang, and L-M Duan.  A quantum machine learning algorithm based on generative models.  Science advances, 4(12):eaat9004, 2018.
  * (30) Seth Lloyd and Christian Weedbrook.  Quantum generative adversarial learning.  Physical review letters, 121(4):040502, 2018.
  * (31) John Preskill.  Quantum computing in the nisq era and beyond.  Quantum, 2:79, 2018.
  * (32) Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al.  Quantum supremacy using a programmable superconducting processor.  Nature, 574(7779):505–510, 2019.
  * (33) Yulin Wu, Wan-Su Bao, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, et al.  Strong quantum computational advantage using a superconducting quantum processor.  Physical review letters, 127(18):180501, 2021.
  * (34) 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.  arXiv preprint arXiv:2112.00778, 2021.
  * (35) 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.
  * (36) Xinbiao Wang, Yuxuan Du, Yong Luo, and Dacheng Tao.  Towards understanding the power of quantum kernels in the NISQ era.  Quantum, 5:531, August 2021.
  * (37) Yuxuan Du and Dacheng Tao.  On exploring practical potentials of quantum auto-encoder with advantages.  arXiv preprint arXiv:2106.15432, 2021.
  * (38) Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, et al.  Variational quantum algorithms.  Nature Reviews Physics, 3(9):625–644, 2021.
  * (39) Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, Tobias Haug, Sumner Alperin-Lea, Abhinav Anand, Matthias Degroote, Hermanni Heimonen, Jakob S Kottmann, Tim Menke, et al.  Noisy intermediate-scale quantum algorithms.  Reviews of Modern Physics, 94(1):015004, 2022.
  * (40) Implicit probabilistic models do not specify the distribution of the data itself, but rather define a stochastic process that, after training, aims to draw samples from the underlying data distribution. Refer to SM A for details.
  * (41) Marcello Benedetti, Delfina Garcia-Pintos, Oscar Perdomo, Vicente Leyton-Ortega, Yunseong Nam, and Alejandro Perdomo-Ortiz.  A generative modeling approach for benchmarking and training shallow quantum circuits.  npj Quantum Information, 5(1):1–9, 2019.
  * (42) Jin-Guo Liu and Lei Wang.  Differentiable learning of quantum circuit born machines.  Physical Review A, 98(6):062324, 2018.
  * (43) Brian Coyle, Maxwell Henderson, Justin Chan Jin Le, Niraj Kumar, Marco Paini, and Elham Kashefi.  Quantum versus classical generative modelling in finance.  Quantum Science and Technology, 6(2):024013, 2021.
  * (44) Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu, and Dacheng Tao.  Expressive power of parametrized quantum circuits.  Phys. Rev. Research, 2:033125, Jul 2020.
  * (45) Christa Zoufal, Aurélien Lucchi, and Stefan Woerner.  Quantum generative adversarial networks for learning and loading random distributions.  npj Quantum Information, 5(1):1–9, 2019.
  * (46) Jinfeng Zeng, Yufeng Wu, Jin-Guo Liu, Lei Wang, and Jiangping Hu.  Learning and inference on generative adversarial quantum circuits.  Physical Review A, 99(5):052306, 2019.
  * (47) He-Liang Huang, Yuxuan Du, Ming Gong, Youwei Zhao, Yulin Wu, Chaoyue Wang, Shaowei Li, Futian Liang, Jin Lin, Yu Xu, et al.  Experimental quantum generative adversarial networks for image generation.  Physical Review Applied, 16(2):024051, 2021.
  * (48) Yiming Huang, Hang Lei, Xiaoyu Li, and Guowu Yang.  Quantum maximum mean discrepancy gan.  Neurocomputing, 454:88–100, 2021.
  * (49) Jonathan Romero and Alán Aspuru-Guzik.  Variational quantum generators: Generative adversarial quantum machine learning for continuous distributions.  Advanced Quantum Technologies, 4(1):2000003, 2021.
  * (50) Kaitlin Gili, Marta Mauri, and Alejandro Perdomo-Ortiz.  Evaluating generalization in classical and quantum generative models.  arXiv preprint arXiv:2201.08770, 2022.
  * (51) Kouhei Nakaji and Naoki Yamamoto.  Quantum semi-supervised generative adversarial network for enhanced data classification.  Scientific reports, 11(1):1–10, 2021.
  * (52) Paolo Braccia, Leonardo Banchi, and Filippo Caruso.  Quantum noise sensing by generating fake noise.  Physical Review Applied, 17(2):024002, 2022.
  * (53) Abhinav Anand, Jonathan Romero, Matthias Degroote, and Alán Aspuru-Guzik.  Noise robustness and experimental demonstration of a quantum generative adversarial network for continuous distributions.  Advanced Quantum Technologies, 4(5):2000069, 2021.
  * (54) Xu-Fei Yin, Yuxuan Du, Yue-Yang Fei, Rui Zhang, Li-Zheng Liu, Yingqiu Mao, Tongliang Liu, Min-Hsiu Hsieh, Li Li, Nai-Le Liu, Dacheng Tao, Yu-Ao Chen, and Jian-Wei Pan.  Efficient Bipartite Entanglement Detection Scheme with a Quantum Adversarial Solver.  Phys. Rev. Lett. 128, 110501 (2022), 2022.  arXiv:2203.07749v1.
  * (55) Daiwei Zhu, Norbert M Linke, Marcello Benedetti, Kevin A Landsman, Nhung H Nguyen, C Huerta Alderete, Alejandro Perdomo-Ortiz, Nathan Korda, A Garfoot, Charles Brecque, et al.  Training of quantum circuits on a hybrid quantum computer.  Science advances, 5(10):eaaw9918, 2019.
  * (56) Ling Hu, Shu-Hao Wu, Weizhou Cai, Yuwei Ma, Xianghao Mu, Yuan Xu, Haiyan Wang, Yipu Song, Dong-Ling Deng, Chang-Ling Zou, et al.  Quantum generative adversarial learning in a superconducting quantum circuit.  Science advances, 5(1):eaav2761, 2019.
  * (57) Junde Li, Rasit O Topaloglu, and Swaroop Ghosh.  Quantum generative models for small molecule drug discovery.  IEEE Transactions on Quantum Engineering, 2:1–8, 2021.
  * (58) Yu-Xin Jin, Jun-Jie Hu, Qi Li, Zhi-Cheng Luo, Fang-Yan Zhang, Hao Tang, Kun Qian, and Xian-Min Jin.  Quantum Deep Learning for Mutant COVID-19 Strain Prediction, 2022.  arXiv:2203.03556v1.
  * (59) Sanjeev Arora, Rong Ge, Yingyu Liang, Tengyu Ma, and Yi Zhang.  Generalization and equilibrium in generative adversarial nets (gans).  arXiv preprint arXiv:1703.00573, 2017.
  * (60) Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang.  Learning and generalization in overparameterized neural networks, going beyond two layers.  In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pages 6158–6169, 2019.
  * (61) Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu, Shan You, and Dacheng Tao.  Learnability of quantum neural networks.  PRX Quantum, 2(4):040337, 2021.
  * (62) Shengjia Zhao, Hongyu Ren, Arianna Yuan, Jiaming Song, Noah Goodman, and Stefano Ermon.  Bias and generalization in deep generative models: An empirical study.  Advances in Neural Information Processing Systems, 31, 2018.
  * (63) 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.
  * (64) Leonardo Banchi, Jason Pereira, and Stefano Pirandola.  Generalization in quantum machine learning: A quantum information standpoint.  PRX Quantum, 2(4):040321, 2021.
  * (65) 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.
  * (66) 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.
  * (67) Hsin-Yuan Huang, Richard Kueng, and John Preskill.  Information-theoretic bounds on quantum advantage in machine learning.  Physical Review Letters, 126(19):190505, 2021.
  * (68) Junyu Liu, Khadijeh Najafi, Kunal Sharma, Francesco Tacchino, Liang Jiang, and Antonio Mezzacapo.  An analytic theory for the dynamics of wide quantum neural networks, 2022.  arXiv:2203.16711v1.
  * (69) Yang Qian, Xinbiao Wang, Yuxuan Du, Xingyao Wu, and Dacheng Tao.  The dilemma of quantum neural networks.  arXiv preprint arXiv:2106.04975, 2021.
  * (70) Ryan Sweke, Jean-Pierre Seifert, Dominik Hangleiter, and Jens Eisert.  On the quantum versus classical learnability of discrete distributions.  Quantum, 5:417, 2021.
  * (71) Marcel Hinsche, Marios Ioannou, Alexander Nietner, Jonas Haferkamp, Yihui Quek, Dominik Hangleiter, Jean-Pierre Seifert, Jens Eisert, and Ryan Sweke.  Learnability of the output distributions of local quantum circuits.  arXiv preprint arXiv:2110.05517, 2021.
  * (72) Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander Smola.  A kernel two-sample test.  J. Mach. Learn. Res., 13(null):723–773, mar 2012.
  * (73) Vladimir Vapnik.  The nature of statistical learning theory.  Springer science & business media, 1999.
  * (74) Maria Schuld and Nathan Killoran.  Quantum machine learning in feature hilbert spaces.  Physical review letters, 122(4):040504, 2019.
  * (75) Harry Buhrman, Richard Cleve, John Watrous, and Ronald De Wolf.  Quantum fingerprinting.  Physical Review Letters, 87(16):167902, 2001.
  * (76) Hirotada Kobayashi, Keiji Matsumoto, and Tomoyuki Yamakami.  Quantum merlin-arthur proof systems: Are multiple merlins more helpful to arthur?  In International Symposium on Algorithms and Computation, pages 189–198. Springer, 2003.
  * (77) GK Dziugaite, DM Roy, and Z Ghahramani.  Training generative neural networks via maximum mean discrepancy optimization.  In Uncertainty in Artificial Intelligence-Proceedings of the 31st Conference, UAI 2015, pages 258–267, 2015.
  * (78) Francois-Xavier Briol, Alessandro Barp, Andrew B Duncan, and Mark Girolami.  Statistical inference for generative models with maximum mean discrepancy.  arXiv preprint arXiv:1906.05944, 2019.
  * (79) Geoffrey E Hinton.  A practical guide to training restricted boltzmann machines.  In Neural networks: Tricks of the trade, pages 599–619. Springer, 2012.
  * (80) Shahar Mendelson.  A few notes on statistical learning theory.  In Advanced lectures on machine learning, pages 1–40. Springer, 2003.
  * (81) 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.
  * (82) Maria Kieferova, Ortiz Marrero Carlos, and Nathan Wiebe.  Quantum generative training using r$\backslash$’enyi divergences.  arXiv preprint arXiv:2106.09567, 2021.
  * (83) Armin Lederer, Jonas Umlauft, and Sandra Hirche.  Uniform Error Bounds for Gaussian Process Regression with Application to Safe Control.  Curran Associates Inc., Red Hook, NY, USA, 2019.
  * (84) Martin Plesch and Časlav Brukner.  Quantum-state preparation with universal gate decompositions.  Physical Review A, 83(3):032302, 2011.
  * (85) Xiao-Ming Zhang, Tongyang Li, and Xiao Yuan.  Quantum state preparation with optimal circuit depth: Implementations and applications.  arXiv preprint arXiv:2201.11495, 2022.
  * (86) Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J Bremner, John M Martinis, and Hartmut Neven.  Characterizing quantum supremacy in near-term devices.  Nature Physics, 14(6):595, 2018.
  * (87) Qingling Zhu, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, Ming Gong, Cheng Guo, Chu Guo, Shaojun Guo, Lianchen Han, Linyin Hong, He-Liang Huang, Yong-Heng Huo, Liping Li, Na Li, Shaowei Li, Yuan Li, Futian Liang, Chun Lin, Jin Lin, Haoran Qian, Dan Qiao, Hao Rong, Hong Su, Lihua Sun, Liangyuan Wang, Shiyu Wang, Dachao Wu, Yulin Wu, Yu Xu, Kai Yan, Weifeng Yang, Yang Yang, Yangsen Ye, Jianghan Yin, Chong Ying, Jiale Yu, Chen Zha, Cha Zhang, Haibin Zhang, Kaili Zhang, Yiming Zhang, Han Zhao, Youwei Zhao, Liang Zhou, Chao-Yang Lu, Cheng-Zhi Peng, Xiaobo Zhu, and Jian-Wei Pan.  Quantum computational advantage via 60-qubit 24-cycle random circuit sampling, 2021.
  * (88) Scott Aaronson and Lijie Chen.  Complexity-theoretic foundations of quantum supremacy experiments.  In 32nd Computational Complexity Conference, page 1, 2017.
  * (89) Michael A Nielsen and Isaac L Chuang.  Quantum computation and quantum information.  Cambridge University Press, 2010.
  * (90) Carlos Bravo-Prieto, Julien Baglio, Marco Cè, Anthony Francis, Dorota M Grabowska, and Stefano Carrazza.  Style-based quantum generative adversarial networks for monte carlo events.  arXiv preprint arXiv:2110.06933, 2021.
  * (91) David Amaro, Carlo Modica, Matthias Rosenkranz, Mattia Fiorentini, Marcello Benedetti, and Michael Lubasch.  Filtering variational quantum algorithms for combinatorial optimization.  Quantum Science and Technology, 7(1):015021, 2022.
  * (92) M Bilkis, M Cerezo, Guillaume Verdon, Patrick J Coles, and Lukasz Cincio.  A semi-agnostic ansatz with variable structure for quantum machine learning.  arXiv preprint arXiv:2103.06712, 2021.
  * (93) Yuxuan Du, Tao Huang, Shan You, Min-Hsiu Hsieh, and Dacheng Tao.  Quantum circuit architecture search: error mitigation and trainability enhancement for variational quantum solvers.  arXiv preprint arXiv:2010.10217, 2020.
  * (94) Kehuan Linghu, Yang Qian, Ruixia Wang, Meng-Jun Hu, Zhiyuan Li, Xuegang Li, Huikai Xu, Jingning Zhang, Teng Ma, Peng Zhao, et al.  Quantum circuit architecture search on a superconducting processor.  arXiv preprint arXiv:2201.00934, 2022.
  * (95) En-Jui Kuo, Yao-Lung L Fang, and Samuel Yen-Chi Chen.  Quantum architecture search via deep reinforcement learning.  arXiv preprint arXiv:2104.07715, 2021.
  * (96) Shi-Xin Zhang, Chang-Yu Hsieh, Shengyu Zhang, and Hong Yao.  Differentiable quantum architecture search.  arXiv preprint arXiv:2010.08561, 2020.
  * (97) Shouvanik Chakrabarti, Huang Yiming, Tongyang Li, Soheil Feizi, and Xiaodi Wu.  Quantum wasserstein generative adversarial networks.  Advances in Neural Information Processing Systems, 32, 2019.
  * (98) Martin Arjovsky, Soumith Chintala, and Léon Bottou.  Wasserstein generative adversarial networks.  In International Conference on Machine Learning, pages 214–223, 2017.
  * (99) Mehdi Mirza and Simon Osindero.  Conditional generative adversarial nets.  arXiv preprint arXiv:1411.1784, 2014.
  * (100) Han Zhang, Tao Xu, Hongsheng Li, Shaoting Zhang, Xiaogang Wang, Xiaolei Huang, and Dimitris N Metaxas.  Stackgan: Text to photo-realistic image synthesis with stacked generative adversarial networks.  In Proceedings of the IEEE International Conference on Computer Vision, pages 5907–5915, 2017.
  * (101) Alireza Makhzani, Jonathon Shlens, Navdeep Jaitly, Ian Goodfellow, and Brendan Frey.  Adversarial autoencoders.  arXiv preprint arXiv:1511.05644, 2015.
  * (102) Ian Goodfellow, Yoshua Bengio, and Aaron Courville.  Deep learning.  MIT press, 2016.
  * (103) Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe.  Convex optimization.  Cambridge university press, 2004.
  * (104) Marcello Benedetti, Edward Grant, Leonard Wossnig, and Simone Severini.  Adversarial quantum circuit learning for pure state approximation.  New Journal of Physics, 21(4):043023, 2019.
  * (105) Maria Schuld, Ville Bergholm, Christian Gogolin, Josh Izaac, and Nathan Killoran.  Evaluating analytic gradients on quantum hardware.  Physical Review A, 99(3):032331, 2019.
  * (106) Jacob Biamonte.  Universal variational quantum computation.  Physical Review A, 103(3):L030401, 2021.
  * (107) Nicolas Le Roux and Yoshua Bengio.  Representational power of restricted boltzmann machines and deep belief networks.  Neural computation, 20(6):1631–1649, 2008.
  * (108) Xun Gao and Lu-Ming Duan.  Efficient representation of quantum many-body states with deep neural networks.  Nature communications, 8(1):662, 2017.
  * (109) Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar.  Foundations of Machine Learning.  Adaptive Computation and Machine Learning. MIT Press, Cambridge, MA, 2 edition, 2018.
  * (110) Richard M Dudley.  The sizes of compact subsets of hilbert space and continuity of gaussian processes.  Journal of Functional Analysis, 1(3):290–330, 1967.
  * (111) Thomas Barthel and Jianfeng Lu.  Fundamental limitations for measurements in quantum many-body systems.  Phys. Rev. Lett., 121:080406, Aug 2018.
  * (112) Julia Kempe, Alexei Kitaev, and Oded Regev.  The complexity of the local hamiltonian problem.  Siam journal on computing, 35(5):1070–1097, 2006.

Supplementary Material: “Power of Quantum Generative Learning”

##  SM A Schematic of QGANs in the discrete and continuous settings

For the purpose of elucidating, in this section, we first introduce the basic
theory of GANs and QGANs, especially for QGANs with MMD loss, and then
demonstrate the equivalence of QCBMs and QGANs in the discrete setting when
the loss function is specified to be MMD.

Basic theory of (classical) GANs and QGANs when $\operatorname{\mathbb{Q}}$ is
continuous. The fundamental mechanism of GAN goodfellow2014generative  and its
variations arjovsky2017wasserstein ; mirza2014conditional ; zhang2017stackgan
; makhzani2015adversarial  is as follows. GAN sets up a two-players game: the
generator $G$ creates data that pretends to come from the real data
distribution $\operatorname{\mathbb{Q}}$ to fool the discriminator $D$, while
$D$ tries to distinguish the fake generated data from the real training data.
Mathematically, $G$ and $D$ corresponds to two a differentiable functions. In
particular, the input of $G$ is a latent variable $\bm{z}$ and its output is
$\bm{x}$, i.e., $G:G(\bm{z},\bm{\theta})\rightarrow\bm{x}$ with $\bm{\theta}$
being trainable parameters for $G$. The role of the latent variable $\bm{z}$
is ensuring GAN to be a structured probabilistic model goodfellow2016deep .
The input of $D$ can either be the generated data $\bm{x}$ or the real data
$\bm{y}\sim\operatorname{\mathbb{Q}}$ and its output corresponds to the binary
classification result (real or fake), respectively. The mathematical
expression of $D$ yields $D:D(\bm{x},\bm{y},\bm{\gamma})\rightarrow(0,1)$ with
$\bm{\gamma}$ being trainable parameters for $D$. If the distribution learned
by $G$ equals to the real data distribution, i.e.,
$\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}=\operatorname{\mathbb{Q}}$,
then $D$ can never discriminate between the generated data and the real data
and this unique solution is called Nash equilibrium goodfellow2014generative .

To reach the Nash equilibrium, the training process of GANs corresponds to the
minimax optimization. Namely, the discriminator $D$ updates $\bm{\gamma}$ to
maximize the classification accuracy, while the generator $G$ updates
$\operatorname{\bm{\theta}}$ to minimize the classification accuracy. With
this regard, the optimization of GAN follows

$\min_{\bm{\theta}}\max_{\bm{\gamma}}\mathcal{L}(D_{\bm{\gamma}}(G_{\bm{\theta}}(\bm{z})),D_{\bm{\gamma}}(\bm{x})):=\mathbb{E}_{\bm{x}\sim\operatorname{\mathbb{Q}}}[D_{\bm{\gamma}}(\bm{x})]+\mathbb{E}_{\bm{z}\sim\mathbb{P}_{\mathcal{Z}}}[(1-D_{\bm{\gamma}}(G_{\bm{\theta}}(\bm{z}))],$
(15)

where $\operatorname{\mathbb{Q}}$ is the distribution of training dataset, and
$\mathbb{P}_{\mathcal{Z}}$ is the probability distribution of the latent
variable $\bm{z}$. In general, $G_{\bm{\theta}}$ and $D_{\bm{\gamma}}$ are
constructed by deep neural networks, and their parameters are updated
iteratively using gradient descent methods boyd2004convex .

The key difference between GANs and QGANs is the way of implementing
$G_{\operatorname{\bm{\theta}}}$ and $D_{\bm{\gamma}}$. Particularly, in
QGANs, either $G$, $D$, or both can be realized by variational quantum
circuits instead of deep neural networks. The training strategy of QGANs is
similar to classical GANs. In this study, we focus on QGANs with MMD loss,
which can be treated as the quantum extension of MMD-GAN dziugaite2015training
. Unlike conventional GANs and QGANs, MMD-GAN and QGAN replace a trainable
discriminator with MMD. In this way, the family of discriminators is
substituted with a family $\mathcal{H}$ of test functions, closed under
negation, where the optimization of $D$ can be completed with the analytical
form. Therefore, the goal of QGANs is finding an estimator minimizing an
unbiased MMD loss, i.e.,

$\operatorname{MMD}^{2}_{U}(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}||\operatorname{\mathbb{Q}}):=\frac{1}{n(n-1)}\sum_{i\neq
i^{\prime}}^{n}k(\bm{x}^{(i)},\bm{x}^{(i^{\prime})})+\frac{1}{m(m-1)}\sum_{j\neq
j^{\prime}}^{m}k(\bm{y}^{(j)},\bm{y}^{(j^{\prime})})-\frac{2}{nm}\sum_{i,j}k(\bm{x}^{(i)},\bm{y}^{(j)}),$
(16)

where $\bm{x}^{(i)}\sim\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}$
and $\bm{y}^{(j)}\sim\operatorname{\mathbb{Q}}$.

Equivalence between QCBMs and QGANs when $\operatorname{\mathbb{Q}}$ is
discrete. In accordance with the explanations in Refs.
benedetti2019adversarial ; zoufal2019quantum , when QGAN is applied to
estimate a discrete distribution $\operatorname{\mathbb{Q}}$ (e.g., quantum
state approximation), the quantum generator aims to directly capture the
distribution of the data itself. This violates the criteria of implicit
generative models, where a stochastic process is employed to draw samples from
the underlying data distribution after training. More specifically, when
$\operatorname{\mathbb{Q}}$ is discrete, the output of the quantum circuit for
both QCBM and QGAN takes the form
$\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}(i)=\operatorname{Tr}(\Pi_{i}\hat{U}(\bm{\theta})\rho_{0}\hat{U}(\bm{\theta})^{\dagger})$
in Eq. (1). The concept ‘adversarial’ originates from the way of optimizing
$\operatorname{\bm{\theta}}$. Instead of using a deterministic distance
measure (e.g., KL divergence) as in QCBMs, QGANs utilize a discriminator
$D_{\bm{\gamma}}$, implemented by either trainable parameterized quantum
circuit or a neural network, to maximally separate
$\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}(i)$ from
$\operatorname{\mathbb{Q}}$. The behavior of simultaneously update
$\operatorname{\bm{\theta}}$ (to minimize the loss) and $\bm{\gamma}$ (to
maximize the loss) is termed as quantum generative adversarial learning. With
this regard, when we replace the trainable $D_{\bm{\gamma}}$ by the
deterministic measure MMD, QGAN takes an equivalent mathematical form with
QCBM.

##  SM B Optimization of QGANs with MMD loss

For self-consistency, in this section, we introduce the elementary backgrounds
of the optimization of QGLMs with MMD loss. See Ref. Gretton2012AKernel  for
elaborations. A central concept used in MMD loss is kernels.

######  Definition 2 (Definition 2, schuld2019quantum ).

Let $\mathcal{X}$ be a nonempty set, called the input set. A function
$k:\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{C}$ is called kernel if the
Gram matrix $\mathcal{K}$ with entries
$\mathcal{K}_{m,m^{\prime}}=k(\bm{x}^{m},\bm{x}^{m^{\prime}})$ is positive
semi-definite.

MMD loss. Let $k:\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}$ be a Borel
measurable kernel on $\mathcal{X}$, and consider the reproducing kernel
Hilbert space $\mathcal{H}_{k}$ associated with k (see Berlinet and Thomas-
Agnan [2004]), equipped with inner product
$\langle\cdot,\cdot\rangle_{\mathcal{H}_{k}}$. Let
$\mathcal{P}_{k}(\mathcal{X})$ be the set of Borel probability measures $\mu$
such that $\int_{\mathcal{X}}\sqrt{k(\bm{x},\bm{x})}\mu(d\bm{x})<\infty$. The
kernel mean embedding $\Pi_{k}(\mu)=\int k(\cdot,y)\mu(dy)$, interpreted as a
Bochner integral, defines a continuous embedding from
$\mathcal{P}_{k}(\mathcal{X})$ into $\mathcal{H}_{k}$. The mean embedding
pulls-back the metric on $\mathcal{H}_{k}$ generated by the inner product to
define a pseudo- metric on $\mathcal{P}_{k}(\mathcal{X})$ called the maximum
mean discrepancy MMD:
$\mathcal{P}_{k}(\mathcal{X})\times\mathcal{P}_{k}(\mathcal{X})\rightarrow\mathbb{R}_{+}$,
i.e.,

$\operatorname{MMD}(\operatorname{\mathbb{P}}_{1}||\operatorname{\mathbb{P}}_{2})=\|\Pi_{k}(\operatorname{\mathbb{P}}_{1})-\Pi_{k}(\operatorname{\mathbb{P}}_{2})\|_{\mathcal{H}_{k}}.$
(17)

The MMD loss has a particularly simple expression that can be derived through
an application of the reproducing property ($f(x)=\langle
f,k(\cdot,\bm{x})\rangle_{\mathcal{H}_{k}}$), i.e.,

$\displaystyle\operatorname{MMD}^{2}(\operatorname{\mathbb{P}}_{1}||\operatorname{\mathbb{P}}_{2}):=\left\|\int_{\mathcal{X}}k(\cdot,\bm{x})\operatorname{\mathbb{P}}_{1}(d\bm{x})-\int_{\mathcal{X}}k(\cdot,\bm{x})\operatorname{\mathbb{P}}_{2}(d\bm{x})\right\|_{\mathcal{H}_{k}}^{2}$
$\displaystyle=$
$\displaystyle\int_{\mathcal{X}}\int_{\mathcal{X}}k(\bm{x},\bm{y})\operatorname{\mathbb{P}}_{1}(d\bm{x})\operatorname{\mathbb{P}}_{1}(dy)-2\int_{\mathcal{X}}\int_{\mathcal{X}}k(\bm{x},\bm{y})\operatorname{\mathbb{P}}_{1}(d\bm{x})\operatorname{\mathbb{P}}_{2}(dy)+\int_{\mathcal{X}}\int_{\mathcal{X}}k(\bm{x},\bm{y})\operatorname{\mathbb{P}}_{2}(d\bm{x})\operatorname{\mathbb{P}}_{2}(dy)$
$\displaystyle=$
$\displaystyle\operatorname{\mathbb{E}}_{\bm{x},\bm{y}\sim\operatorname{\mathbb{P}}_{1}}(k(\bm{x},\bm{y}))-2\operatorname{\mathbb{E}}_{x\sim\operatorname{\mathbb{P}}_{1},y\sim\operatorname{\mathbb{P}}_{2}}(k(\bm{x},\bm{y}))+\operatorname{\mathbb{E}}_{\bm{x},\bm{y}\sim\operatorname{\mathbb{P}}_{2}}(k(\bm{x},\bm{y})),$
(18)

which provides a closed form expression up to calculation of expectations.

Optimization of QCBMs with MMD loss. The goal of QCBMs is finding an estimator
minimizing the loss function
$\operatorname{MMD}^{2}(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}||\operatorname{\mathbb{Q}})$
in Eq. (B), where $\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}$ is
defined in Eq. (1). The optimization is completed by the gradient based
descent optimizer. The updating rule satisfies
$\operatorname{\bm{\theta}}^{(t+1)}=\operatorname{\bm{\theta}}^{(t)}-\eta\nabla_{\operatorname{\bm{\theta}}}\operatorname{MMD}^{2}(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}||\operatorname{\mathbb{Q}})$
and $\eta$ is the learning rate. Concretely, the partial derivative of the
$j$-th entry satisfies

$\displaystyle\frac{\partial\operatorname{MMD}^{2}(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}||\operatorname{\mathbb{Q}})}{\partial\operatorname{\bm{\theta}}_{j}}$
$\displaystyle=$
$\displaystyle\frac{\partial\operatorname{\mathbb{E}}_{\bm{x},\bm{y}\sim\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}}(k(\bm{x},\bm{y}))-2\operatorname{\mathbb{E}}_{x\sim\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}},y\sim\operatorname{\mathbb{Q}}}(k(\bm{x},\bm{y}))+\operatorname{\mathbb{E}}_{\bm{x},\bm{y}\sim\operatorname{\mathbb{Q}}}(k(\bm{x},\bm{y}))}{\partial\operatorname{\bm{\theta}}_{j}}$
$\displaystyle=$
$\displaystyle\sum_{\bm{x},\bm{y}}k(\bm{x},\bm{y})\left(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}(\bm{y})\frac{\partial\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}(\bm{x})}{\partial\operatorname{\bm{\theta}}_{j}}+\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}(\bm{x})\frac{\partial\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}(\bm{y})}{\partial\operatorname{\bm{\theta}}_{j}}\right)-2\sum_{\bm{x},\bm{y}}k(\bm{x},\bm{y})\frac{\partial\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}(\bm{x})}{\partial\operatorname{\bm{\theta}}_{j}}\operatorname{\mathbb{Q}}(\bm{y})$
$\displaystyle=$
$\displaystyle\sum_{\bm{x},\bm{y}}k(\bm{x},\bm{y})\left(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}(\bm{y})\left(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}+\frac{\pi}{2}\bm{e}_{j}}(\bm{x})-\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}-\frac{\pi}{2}\bm{e}_{j}}(\bm{x})\right)+\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}(\bm{x})\left(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}+\frac{\pi}{2}\bm{e}_{j}}(\bm{y})-\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}-\frac{\pi}{2}\bm{e}_{j}}(\bm{y})\right)\right)$
$\displaystyle-2\sum_{\bm{x},\bm{y}}k(\bm{x},\bm{y})\left(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}+\frac{\pi}{2}\bm{e}_{j}}(\bm{x})-\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}-\frac{\pi}{2}\bm{e}_{j}}(\bm{x})\right)\operatorname{\mathbb{Q}}(\bm{y})$
$\displaystyle=$
$\displaystyle\operatorname{\mathbb{E}}_{\bm{x}\sim\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}+\frac{\pi}{2}\bm{e}_{j}},\bm{y}\sim\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}}(k(\bm{x},\bm{y}))-\operatorname{\mathbb{E}}_{\bm{x}\sim\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}-\frac{\pi}{2}\bm{e}_{j}},\bm{y}\sim\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}}(k(\bm{x},\bm{y}))+\operatorname{\mathbb{E}}_{\bm{x}\sim\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}},\bm{y}\sim\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}+\frac{\pi}{2}\bm{e}_{j}}}(k(\bm{x},\bm{y}))-\operatorname{\mathbb{E}}_{\bm{x}\sim\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}},\bm{y}\sim\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}-\frac{\pi}{2}\bm{e}_{j}}}(k(\bm{x},\bm{y}))$
(19)
$\displaystyle-2\operatorname{\mathbb{E}}_{\bm{x}\sim\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}+\frac{\pi}{2}\bm{e}_{j}},\bm{y}\sim\operatorname{\mathbb{Q}}}(k(\bm{x},\bm{y}))+2\operatorname{\mathbb{E}}_{\bm{x}\sim\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}-\frac{\pi}{2}\bm{e}_{j}},\bm{y}\sim\operatorname{\mathbb{Q}}}(k(\bm{x},\bm{y})),$

where the last second equality employs the parameter shift rule
schuld2019evaluating  to calculate the partial derivative
${\partial\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}(\bm{y})}/{\partial\operatorname{\bm{\theta}}_{j}}$
and
${\partial\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}(\bm{x})}/{\partial\operatorname{\bm{\theta}}_{j}}$.
According to Lemma 1, the six expectation terms in Eq. (B) can be analytically
and efficiently calculated when the $k(\cdot,\cdot)$ is quantum. In the case
of classical kernels, the six expectation terms in Eq. (B) are estimated by
the sample mean.

Optimization of QGANs with MMD loss. We next derive the gradients of QGANs
with respect to the $\ell$-th entry. Since the evaluation of expectation is
runtime expensive when $\operatorname{\mathbb{Q}}$ is continuous, QGANs employ
an unbiased estimator of the MMD loss in Eq. (16) to update
$\operatorname{\bm{\theta}}$. The updating rule at the $t$-th iteration is
$\operatorname{\bm{\theta}}^{(t+1)}=\operatorname{\bm{\theta}}^{(t)}-\eta\nabla_{\operatorname{\bm{\theta}}}\operatorname{MMD}^{2}_{U}(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}||\operatorname{\mathbb{Q}})$.
According to the chain rule, we have

$\displaystyle\frac{\partial\operatorname{MMD}_{U}^{2}(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}||\operatorname{\mathbb{Q}})}{\partial\operatorname{\bm{\theta}}_{\ell}}$
$\displaystyle=$ $\displaystyle\frac{\partial\frac{1}{n(n-1)}\sum_{i\neq
i^{\prime}}^{n}k(G_{\operatorname{\bm{\theta}}}(\bm{z}^{(i)}),G_{\operatorname{\bm{\theta}}}(\bm{z}^{(i^{\prime})}))-\frac{2}{nm}\sum_{i,j}k(G_{\operatorname{\bm{\theta}}}(\bm{z}^{(i)}),\bm{y}^{(j)})}{\partial\operatorname{\bm{\theta}}_{\ell}}$
$\displaystyle=$ $\displaystyle\frac{1}{n(n-1)}\sum_{i\neq
i^{\prime}}^{n}\frac{\partial
k(G_{\operatorname{\bm{\theta}}}(\bm{z}^{(i)}),G_{\operatorname{\bm{\theta}}}(\bm{z}^{(i^{\prime})}))}{\partial
G_{\operatorname{\bm{\theta}}}(\bm{z}^{(i)})}\frac{\partial
G_{\operatorname{\bm{\theta}}}(\bm{z}^{(i)})}{\partial\operatorname{\bm{\theta}}_{\ell}}+\frac{\partial
k(G_{\operatorname{\bm{\theta}}}(\bm{z}^{(i)}),G_{\operatorname{\bm{\theta}}}(\bm{z}^{(i^{\prime})}))}{\partial
G_{\operatorname{\bm{\theta}}}(\bm{z}^{(i^{\prime})})}\frac{\partial
G_{\operatorname{\bm{\theta}}}(\bm{z}^{(i^{\prime})})}{\partial\operatorname{\bm{\theta}}_{\ell}}-$
(21) $\displaystyle\frac{2}{nm}\sum_{i,j}\frac{\partial
k(G_{\operatorname{\bm{\theta}}}(\bm{z}^{(i)}),\bm{y}^{(j)})}{\partial
G_{\operatorname{\bm{\theta}}}(\bm{z}^{(i)})}\frac{\partial
G_{\operatorname{\bm{\theta}}}(\bm{z}^{(i)})}{\partial\operatorname{\bm{\theta}}_{\ell}}$

where the first equality uses $\partial\frac{1}{m(m-1)}\sum_{j\neq
j^{\prime}}^{m}k(\bm{y}^{(j)},\bm{y}^{(j^{\prime})})/\partial\operatorname{\bm{\theta}}_{\ell}=0$,
each derivative ${\partial
k(G_{\operatorname{\bm{\theta}}}(\bm{z}^{(i)}),G_{\operatorname{\bm{\theta}}}(\bm{z}^{(i^{\prime})}))}/{\partial
G_{\operatorname{\bm{\theta}}}(\bm{z}^{(i)})}$ can be easily computed for
standard kernels, and the derivative ${\partial
G_{\operatorname{\bm{\theta}}}(\bm{z}^{(i)})}/{\partial\operatorname{\bm{\theta}}_{\ell}}$
for $\forall i\in n,j\in[m]$ can be computed via the parameter shift rule.
Therefore, the gradients of QGANs with MMD loss can be achieved.

##  SM C The comparison between QCBMs and GLMs for estimating discrete
distributions

In this section, we emphasize a central question in QGLMs, i.e., when both
variational quantum circuits and neural networks are used to implement
$\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}$, which one can attain
a lower
$\inf_{\operatorname{\bm{\theta}}\in\bm{\Theta}}\operatorname{MMD}^{2}(\operatorname{\mathbb{P}}_{\bm{\theta}}||\operatorname{\mathbb{Q}})$.
The importance of this issue comes from Eq. (7), where the generalization
error bound becomes meaningful when
$\inf_{\operatorname{\bm{\theta}}\in\bm{\Theta}}\operatorname{MMD}^{2}(\operatorname{\mathbb{P}}_{\bm{\theta}}||\operatorname{\mathbb{Q}})$
is small. In this respect, it is necessary to understand whether QCBMs allow a
lower
$\inf_{\operatorname{\bm{\theta}}\in\bm{\Theta}}\operatorname{MMD}^{2}(\operatorname{\mathbb{P}}_{\bm{\theta}}||\operatorname{\mathbb{Q}})$
over (classical) GLMs.

In what follows, we analyze when QCBMs promise a lower
$\inf_{\operatorname{\bm{\theta}}\in\bm{\Theta}}\operatorname{MMD}^{2}(\operatorname{\mathbb{P}}_{\bm{\theta}}||\operatorname{\mathbb{Q}})$
over a typical GLM—restricted Boltzmann machine (RBM) hinton2012practical . To
be more specific, consider that both QCBMs and RBMs are universal
approximators with an exponential number of trainable parameters
biamonte2021universal ; le2008representational  with
$\inf_{\operatorname{\bm{\theta}}\in\bm{\Theta}}\operatorname{MMD}^{2}(\operatorname{\mathbb{P}}_{\bm{\theta}}||\operatorname{\mathbb{Q}})\rightarrow
0$, we focus on the more practical scenario in which the number of parameters
polynomially scales with the feature dimension, the qudit count, and the
number of visible neurons. Denote the space of the parameterized distributions
formed by QCBMs (or RBM) as
$\operatorname{\mathbb{P}}^{\text{QCBM}}_{\bm{\Theta}}$ (or
$\operatorname{\mathbb{P}}^{\text{RBM}}_{\bm{\Theta}}$). The superiority of
QCBMs can be identified by showing
$\inf_{\operatorname{\bm{\theta}}\in\bm{\Theta}}\operatorname{MMD}^{2}(\operatorname{\mathbb{P}}_{\bm{\theta}}^{\text{QCBM}}||\operatorname{\mathbb{Q}})\leq\inf_{\operatorname{\bm{\theta}}\in\bm{\Theta}}\operatorname{MMD}^{2}(\operatorname{\mathbb{P}}_{\bm{\theta}}^{\text{RBM}}||\operatorname{\mathbb{Q}})$.
This amounts to finding a distribution $\operatorname{\mathbb{Q}}$ satisfying

$\left(\operatorname{\mathbb{Q}}\in\operatorname{\mathbb{P}}^{\text{QCBM}}_{\bm{\Theta}}\right)\wedge\left(\operatorname{\mathbb{Q}}\notin\operatorname{\mathbb{P}}^{\text{RBM}}_{\bm{\Theta}}\right).$
(22)

According to the results in gao2017efficient1 , there is a large class of
quantum states meeting the above requirement. Representative examples include
projected entangled pair states and ground states of $k$-local Hamiltonians.

##  SM D Proof of Theorem 2 (generalization of QGANs)

The proof of Theorem 2 utilizes the following three lemmas. For clearness, we
defer the proof of Lemmas 5 and 6 to SM D.1 and D.2, respectively.

######  Lemma 4 (McDiarmids inequality, mendelson2003few ).

Let
$f:\mathcal{X}_{1}\times\mathcal{X}_{2}\times...\times\mathcal{X}_{N}\rightarrow\mathbb{R}$
and assume there exists $c_{1},...,c_{2}\geq 0$ such that, for all
$k\in\\{1,...,N\\}$, we have

$\sup_{\bm{x}_{1},...,\bm{x}_{k},\tilde{\bm{x}}_{k},...\bm{x}_{N}}|f(\bm{x}_{1},...,\bm{x}_{k},...,\bm{x}_{N})-f(\bm{x}_{1},...,\tilde{\bm{x}}_{k},...,\bm{x}_{N})|\leq
c_{k}.$ (23)

Then for all $\epsilon\geq 0$ and independent random variables
$\xi_{1},...\xi_{N}$ in $\mathcal{X}$,

$\Pr(|f(\xi_{1},...\xi_{N})-\operatorname{\mathbb{E}}(f(\xi_{1},...\xi_{N}))|\geq\epsilon)\leq\exp\left(\frac{-2\epsilon^{2}}{\sum_{n=1}^{N}c_{n}^{2}}\right).$
(24)

######  Lemma 5.

Following the notations in Theorem 2, define
$\mathcal{G}=\\{k(G_{\bm{\theta}}(\cdot),G_{\bm{\theta}}(\cdot))|\bm{\theta}\in\bm{\Theta}\\}$
and
$\mathcal{G}_{+}=\\{k(G_{\bm{\theta}}(\bm{z}),G_{\bm{\theta}}(\cdot))|\bm{\theta}\in\bm{\Theta},\bm{z}\in\mathcal{Z}\\}$.
Given the set $\mathcal{S}=\\{\bm{z}^{(i)}\\}_{i=1}^{n}$, we have

$\displaystyle\operatorname{\mathbb{E}}\large(\sup_{\operatorname{\bm{\theta}}\in\bm{\Theta}}\large|\operatorname{\mathbb{E}}_{\bm{z},\bm{z}^{\prime}}(k(G_{\operatorname{\bm{\theta}}}(\bm{z}),G_{\operatorname{\bm{\theta}}}(\bm{z}^{\prime})))-\frac{1}{n(n-1)}\sum_{i\neq
i^{\prime}}k(G_{\operatorname{\bm{\theta}}}(\bm{z}^{(i)}),G_{\operatorname{\bm{\theta}}}(\bm{z}^{(i^{\prime})}))\large|\large)$
$\displaystyle\leq$
$\displaystyle\frac{8}{n-1}+\frac{24\sqrt{d^{2k}(N_{ge}+N_{gt})}}{n-1}\left(1+N\ln(441dC_{3}^{2}(n-1)N_{ge}N_{gt})\right).$
(25)

######  Lemma 6.

Following the notations in Theorem 2, define
$\mathcal{W}=\\{k(G_{\bm{\theta}}(\cdot),\cdot)|\bm{\theta}\in\bm{\Theta}\\}$
and
$\mathcal{W}_{+}=\\{k(G_{\bm{\theta}}(\cdot),\bm{y})|\bm{\theta}\in\bm{\Theta},\bm{y}\in\mathcal{Y}\\}$.
Given the set $\mathcal{S}=\\{\bm{z}^{(i)}\\}_{i=1}^{n}$ and the set
$\\{\bm{y}^{(j)}\\}_{j=1}^{m}$, we have

$\displaystyle\operatorname{\mathbb{E}}\left(\sup_{\operatorname{\bm{\theta}}\in\bm{\Theta}}\Big{|}\operatorname{\mathbb{E}}_{\bm{z},\bm{y}}(k(G_{\operatorname{\bm{\theta}}}(\bm{z}),\bm{y}))-\frac{1}{mn}\sum_{i\in[n],j\in[m]}k(G_{\operatorname{\bm{\theta}}}(\bm{z}^{(i)}),\bm{y}^{(j)})\Big{|}\right)$
$\displaystyle\leq$
$\displaystyle\frac{8}{n}+\frac{24\sqrt{d^{2k}(N_{ge}+N_{gt})}}{n}\left(1+N\ln(441dC_{3}^{2}nN_{ge}N_{gt})\right).$
(26)

We are now ready to prove Theorem 2.

###### Proof of Theorem 2.

Let
$\mathcal{E}(\operatorname{\bm{\theta}})=\operatorname{MMD}_{U}^{2}(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}^{n}||\operatorname{\mathbb{Q}}^{m})$
and
$\mathcal{T}(\operatorname{\bm{\theta}})=\operatorname{MMD}^{2}(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}||\operatorname{\mathbb{Q}})$.
Note that the generalization error equals to

$\mathfrak{R}^{C}=\mathcal{T}(\hat{\operatorname{\bm{\theta}}}^{(n,m)})-\mathcal{T}(\operatorname{\bm{\theta}}^{*}).$
(27)

In the remainder of the proof, when no confusion occurs, we abbreviate
$\hat{\operatorname{\bm{\theta}}}^{(n,m)}$ as
$\hat{\operatorname{\bm{\theta}}}$ for clearness. The above equation is upper
bounded by

$\mathfrak{R}^{C}=\mathcal{E}(\hat{\operatorname{\bm{\theta}}})-\mathcal{E}(\hat{\operatorname{\bm{\theta}}})+\mathcal{T}(\hat{\operatorname{\bm{\theta}}})-\mathcal{T}(\operatorname{\bm{\theta}}^{*})\leq\mathcal{E}(\operatorname{\bm{\theta}}^{*})-\mathcal{E}(\hat{\operatorname{\bm{\theta}}})+\mathcal{T}(\hat{\operatorname{\bm{\theta}}})-\mathcal{T}(\operatorname{\bm{\theta}}^{*})\leq|\mathcal{T}(\hat{\operatorname{\bm{\theta}}})-\mathcal{E}(\hat{\operatorname{\bm{\theta}}})|+|\mathcal{T}(\operatorname{\bm{\theta}}^{*})-\mathcal{E}(\operatorname{\bm{\theta}}^{*})|,$
(28)

where the first inequality employs the definition of
$\hat{\operatorname{\bm{\theta}}}$ with
$\mathcal{E}(\operatorname{\bm{\theta}}^{*})\geq\mathcal{E}(\hat{\operatorname{\bm{\theta}}})$
and the second inequality uses the property of absolute value function. In the
following, we derive the probability for
$\sup_{\operatorname{\bm{\theta}}\in\Theta}|\mathcal{T}(\operatorname{\bm{\theta}})-\mathcal{E}(\operatorname{\bm{\theta}})|<\epsilon$,
which in turn can achieve the upper bound of $\mathfrak{R}^{C}$.

According to the explicit form of the MMD loss,
$\sup_{\operatorname{\bm{\theta}}\in\bm{\Theta}}|\mathcal{E}(\operatorname{\bm{\theta}})-\mathcal{T}(\operatorname{\bm{\theta}})|$
satisfies

$\displaystyle\sup_{\operatorname{\bm{\theta}}\in\bm{\Theta}}\left|\operatorname{MMD}_{U}^{2}(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}^{n}||\operatorname{\mathbb{Q}}^{m})-\operatorname{MMD}^{2}(\operatorname{\mathbb{P}}_{\operatorname{\bm{\theta}}}||\operatorname{\mathbb{Q}})\right|$
$\displaystyle=$
$\displaystyle\sup_{\operatorname{\bm{\theta}}\in\bm{\Theta}}\Big{|}\operatorname{\mathbb{E}}_{\bm{z},\bm{z}^{\prime}}(k(G_{\operatorname{\bm{\theta}}}(\bm{z}),G_{\operatorname{\bm{\theta}}}(\bm{z}^{\prime})))-2\operatorname{\mathbb{E}}_{\bm{z},y}(k(G_{\operatorname{\bm{\theta}}}(\bm{z}),\bm{y}))+\operatorname{\mathbb{E}}_{\bm{y},\bm{y}^{\prime}}(k(\bm{y},\bm{y}^{\prime}))-\frac{1}{n(n-1)}\sum_{i\neq
i^{\prime}}k(G_{\operatorname{\bm{\theta}}}(\bm{z}^{(i)}),G_{\operatorname{\bm{\theta}}}(\bm{z}^{(i^{\prime})}))$
$\displaystyle+\frac{2}{mn}\sum_{i\in[n],j\in[m]}k(G_{\operatorname{\bm{\theta}}}(\bm{z}^{(i)}),\bm{y}^{(j)})-\frac{1}{m(m-1)}\sum_{j\neq
j^{\prime}}k(\bm{y}^{(j)},\bm{y}^{(j^{\prime})})\Big{|}$ $\displaystyle\leq$
$\displaystyle\underbrace{\sup_{\operatorname{\bm{\theta}}\in\bm{\Theta}}\Big{|}\operatorname{\mathbb{E}}_{\bm{y},\bm{y}^{\prime}}(k(\bm{y},\bm{y}^{\prime}))-\frac{1}{m(m-1)}\sum_{j\neq
j^{\prime}}k(\bm{y}^{(j)},\bm{y}^{(j^{\prime})})\Big{|}}_{T1}+\underbrace{\sup_{\operatorname{\bm{\theta}}\in\bm{\Theta}}\Big{|}\operatorname{\mathbb{E}}_{\bm{z},\bm{z}^{\prime}}(k(G_{\operatorname{\bm{\theta}}}(\bm{z}),G_{\operatorname{\bm{\theta}}}(\bm{z}^{\prime})))-\frac{1}{n(n-1)}\sum_{i\neq
i^{\prime}}k(G_{\operatorname{\bm{\theta}}}(\bm{z}^{(i)}),G_{\operatorname{\bm{\theta}}}(\bm{z}^{(i^{\prime})}))\Big{|}}_{T2}$
(29)
$\displaystyle+2\underbrace{\sup_{\operatorname{\bm{\theta}}\in\bm{\Theta}}\Big{|}\operatorname{\mathbb{E}}_{z,y}(k(G_{\operatorname{\bm{\theta}}}(\bm{z}),\bm{y}))-\frac{1}{mn}\sum_{i\in[n],j\in[m]}k(G_{\operatorname{\bm{\theta}}}(\bm{z}^{(i)}),\bm{y}^{(j)})\Big{|}}_{T3}$

where the inequality comes from the Jensen inequality.

We next separately derive the upper bounds of the terms $T1$, $T2$, and $T3$
in Eq. (D).

Upper bound of $T1$. The upper bound of $T1$ only depends on the examples
sampled from the target distribution $\operatorname{\mathbb{Q}}$, which is
independent of $\operatorname{\bm{\theta}}\in\bm{\Theta}$. With this regard,
T1 can be taken out of the supremum and we apply the concentration inequality
in Lemma 4 to derive the upper bound of
$|\operatorname{\mathbb{E}}_{\bm{y},\bm{y}^{\prime}}(k(\bm{y},\bm{y}^{\prime}))-\frac{1}{m(m-1)}\sum_{j\neq
j^{\prime}}k(\bm{y}^{(j)},\bm{y}^{(j^{\prime})})|$. Recall the precondition of
employing Lemma 4 is finding the upper bound on $f(\cdot)$. Let the function
$f(\cdot)$ be $\frac{1}{m(m-1)}\sum_{j\neq
j^{\prime}}k(\bm{y}^{(j)},\bm{y}^{(j^{\prime})})$. For each
$\ell\in\\{1,...,m\\}$, the desired upper bound yields

$\displaystyle\left|-\frac{1}{m(m-1)}(\sum_{j\neq
j^{\prime},j\neq\ell}k(\bm{y}^{(j)},\bm{y}^{(j^{\prime})})+\sum_{j^{\prime}\neq\ell}k(\bm{y}^{(\ell)},\bm{y}^{(j^{\prime})}))+\frac{1}{m(m-1)}(\sum_{j\neq
j^{\prime},j\neq\ell}k(\bm{y}^{(j)},\bm{y}^{(j^{\prime})})+\sum_{j^{\prime}\neq\ell}k(\tilde{\bm{y}}^{(\ell)},\bm{y}^{(j^{\prime})}))\right|$
$\displaystyle=$
$\displaystyle\left|\frac{1}{m(m-1)}\sum_{j^{\prime}\neq\ell}\left(k(\bm{y}^{(\ell)},\bm{y}^{(j^{\prime})}))-k(\tilde{\bm{y}}^{(\ell)},\bm{y}^{(j^{\prime})}))\right)\right|$
$\displaystyle\leq$ $\displaystyle\frac{2C_{2}}{m},$ (30)

where the inequality leverages the assumption that the kernel $k(\cdot,\cdot)$
is upper bounded by $C_{2}$.

Given this upper bound, we obtain

$\displaystyle\Pr(T1\geq\epsilon)$ $\displaystyle=$
$\displaystyle\Pr\left(\left|\operatorname{\mathbb{E}}_{\bm{y},\bm{y}^{\prime}}(k(\bm{y},\bm{y}^{\prime}))-\frac{1}{m(m-1)}\sum_{j\neq
j^{\prime}}k(\bm{y}^{(j)},\bm{y}^{(j^{\prime})})\right|\geq\epsilon\right)$
$\displaystyle\leq$
$\displaystyle\exp\left(-\frac{\epsilon^{2}}{8C_{2}^{2}}m\right)=\delta_{T1},$
(31)

where the inequality exploits the results in Lemma 4.

Upper bound of $T2$. We next use the concentration inequality to quantify the
upper bound of $T2$. The derivation is similar to that of $T1$. In particular,
supported by the results of Lemma 4, we have

$\Pr(|T2-\operatorname{\mathbb{E}}(T2)|\geq\epsilon)\leq\exp\left(-\frac{\epsilon^{2}}{8C_{2}^{2}}n\right)=\delta_{T2}.$
(32)

Suppose that $\operatorname{\mathbb{E}}(T2)\leq\epsilon_{1}$, an immediate
observation is that

$\Pr(T2\geq\epsilon_{1}+\epsilon)\leq\exp\left(-\frac{\epsilon^{2}}{8C_{2}^{2}}n\right)=\delta_{T2}.$
(33)

In other words, the derivation of the upper bound of T2 amounts to analyzing
the upper bound $\epsilon_{1}$.

Upper bound of $T3$. Following the same routine with the derivation of the
upper bound of T2, we obtain

$\Pr(|T3-\operatorname{\mathbb{E}}(T3)|\geq\epsilon)\leq\exp\left(-\frac{\epsilon^{2}}{8C_{2}^{2}}\frac{nm}{n+m}\right)=\delta_{T3}.$
(34)

Suppose that $\operatorname{\mathbb{E}}(T3)\leq\epsilon_{2}$. The above result
hints that

$\Pr(T3\geq\epsilon_{2}+\epsilon)\leq\exp\left(-\frac{\epsilon^{2}}{8C_{2}^{2}}\frac{nm}{n+m}\right)=\delta_{T3}.$
(35)

Summing up Eqs. (D), (33), and (35), the union bound gives

$\displaystyle\Pr\left(\sup_{\operatorname{\bm{\theta}}\in\bm{\Theta}}|\mathcal{E}(\operatorname{\bm{\theta}})-\mathcal{T}(\operatorname{\bm{\theta}})|\geq\epsilon_{1}+2\epsilon_{2}+4\epsilon\right)\leq\delta_{T1}+\delta_{T2}+\delta_{T3}$
$\displaystyle\Rightarrow$
$\displaystyle\Pr\left(\sup_{\operatorname{\bm{\theta}}\in\bm{\Theta}}|\mathcal{E}(\operatorname{\bm{\theta}})-\mathcal{T}(\operatorname{\bm{\theta}})|\geq\epsilon_{1}+2\epsilon_{2}+4\epsilon\right)\leq
3\delta_{T3}$ $\displaystyle\Rightarrow$
$\displaystyle\Pr\left(|\mathcal{E}(\hat{\operatorname{\bm{\theta}}})-\mathcal{T}(\hat{\operatorname{\bm{\theta}}})|\geq\epsilon_{1}+2\epsilon_{2}+4\epsilon\right)\leq
3\delta_{T3}.$ (36)

This yields that with probability at least $1-3\delta_{T3}$,

$2(\epsilon_{1}+2\epsilon_{2}+4\epsilon)\geq|\mathcal{E}(\hat{\operatorname{\bm{\theta}}})-\mathcal{T}(\hat{\operatorname{\bm{\theta}}})|+|\mathcal{E}(\operatorname{\bm{\theta}}^{*})-\mathcal{T}(\operatorname{\bm{\theta}}^{*})|\geq|\mathcal{E}(\hat{\operatorname{\bm{\theta}}})-\mathcal{T}(\hat{\operatorname{\bm{\theta}}})-\mathcal{E}(\operatorname{\bm{\theta}}^{*})+\mathcal{T}(\operatorname{\bm{\theta}}^{*})|\geq|\mathcal{T}(\hat{\operatorname{\bm{\theta}}})-\mathcal{T}(\operatorname{\bm{\theta}}^{*})|=\mathfrak{R}^{C}.$
(37)

According to the explicit forms of $\epsilon_{1}$ and $\epsilon_{2}$ achieved
in Lemmas 5 and 6, with probability $1-3\delta_{T3}$, the generalization error
of QGANs is upper bounded by

$\displaystyle\mathfrak{R}^{C}$ $\displaystyle\leq$ $\displaystyle
8\epsilon+2\left(\frac{8}{n-1}+\frac{24\sqrt{d^{2k}(N_{ge}+N_{gt})}}{n-1}\left(1+N\ln(1764C_{3}^{2}(n-1)N_{ge}N_{gt})\right)\right)$
$\displaystyle+4\left(\frac{8}{n}+\frac{24\sqrt{d^{2k}(N_{ge}+N_{gt})}}{n}\left(1+N\ln(1764C_{3}^{2}nN_{ge}N_{gt})\right)\right)$
$\displaystyle\leq$ $\displaystyle
8\sqrt{\frac{8C_{2}^{2}(n+m)}{nm}\ln(\frac{1}{3\delta_{T3}})}+6\left(\frac{8}{n-1}+\frac{24\sqrt{d^{2k}(N_{gt}+N_{ge})}}{n-1}\left(1+N\ln(441dC_{3}^{2}nN_{ge}N_{gt})\right)\right).$
(38)

where the last inequality uses the relation between $\delta_{T3}$ and
$\epsilon$ in Eq. (35) with
$\epsilon=\sqrt{8C_{2}^{2}(n+m)\ln(1/\delta_{T3})/(nm)}$, $1/n<1/(n-1)$, and
$n-1<n$.

∎

###  D.1 Proof of Lemma 5

Recall Lemma 5 aims to derive the upper bound of
$\operatorname{\mathbb{E}}(T2)$ in Eq. (D). In Ref. dziugaite2015training ,
the authors utilize a statistical measure named Rademacher complexity to
quantify these two terms. Different from the classical counterpart, here we
adopt an another statistical measure, i.e., covering number, to derive the
upper bound of $\operatorname{\mathbb{E}}(T2)$. This measure allows us to
identify how $\operatorname{\mathbb{E}}(T2)$ scales with the qudit count $N$
and the architecture of the employed Ansatz such as the trainable parameters
$N_{gt}$ and the types of the quantum gates. For self-consistency, we provide
the formal definition of covering number and Rademacher as follows.

######  Definition 3 (Covering number, MohriRostamizadehTalwalkar18 ).

The covering number $\mathcal{N}(\mathcal{U},\epsilon,\|\cdot\|)$ denotes the
least cardinality of any subset $\mathcal{V}\subset\mathcal{U}$ that covers
$\mathcal{U}$ at scale $\epsilon$ with a norm $\|\cdot\|$, i.e.,

$\sup_{A\in\mathcal{U}}\min_{B\in\mathcal{V}}\|A-B\|\leq\epsilon.$ (39)

######  Definition 4 (Rademacher, MohriRostamizadehTalwalkar18 ).

Let $\mu$ be a probability measure on $\mathcal{X}$, and let $\mathcal{F}$ be
a class of uniformly bounded functions on $\mathcal{X}$. Then the Rademacher
complexity of $\mathcal{F}$ is

$\mathfrak{R}_{n}(\mathcal{F})=\mathbb{E}_{\mu}\mathbb{E}_{\sigma_{1},...,\sigma_{n}}\left(\frac{1}{\sqrt{n}}\sup_{f\in\mathcal{F}}\left|\sum_{i=1}^{n}\sigma_{i}f(\bm{x}^{(i)})\right|\right),$
(40)

where $\bm{\sigma}=(\sigma_{1},...,\sigma_{n})$ is a sequence of independent
Rademacher variables taking values in $\\{-1,1\\}$ and each with probability
$1/2$, and $\bm{x}_{1},...,\bm{x}_{n}\in\mathcal{X}$ are independent,
$\mu$-distributed random variables.

Intuitively, the covering number concerns the minimum number of spherical
balls with radius $\varepsilon$ that occupies the whole space; the Rademacher
complexity measures the ability of functions from $\mathcal{F}$ to fit random
noise. The relation between Rademacher complexity and covering number is
established by the following Dudley entropy integral bound.

######  Lemma 7 (Adapted from dziugaite2015training ; dudley1967sizes ).

Let $\mathcal{F}=\\{f:\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}\\}$
and
$\mathcal{F}_{+}=\\{h=f(\bm{x},\cdot):f\in\mathcal{F},\bm{x}\in\mathcal{X}\\}$
and $\mathcal{F}_{+}\subset B(L_{\infty}(\mathcal{X}))$. Given the set
$\mathcal{S}=\\{\bm{x}^{(1)},...,\bm{x}^{(n)}\\}\in\mathcal{X}$, denote the
Rademacher complexity of $\mathcal{F}_{+}$ as
$\mathfrak{R}_{n}(\mathcal{F}_{+})$, it satisfies

$\mathfrak{R}_{n}(\mathcal{F}_{+})\leq\inf_{\alpha>0}\left(4\alpha+\frac{12}{\sqrt{n}}\int_{\alpha}^{1}\sqrt{\ln(\mathcal{N}((\mathcal{F}_{+})_{|\mathcal{S}},\epsilon,\|\cdot\|_{2})}d\epsilon\right),$
(41)

where
$(\mathcal{F}_{+})_{|\mathcal{S}}=\\{[f(\bm{x},\bm{x}^{(i)})]_{i=1:n}:f\in\mathcal{F},\bm{x}\in\mathcal{X}\\}$
denotes the set of vectors formed by the hypothesis with $\mathcal{S}$.

Ref. dziugaite2015training  hinges on the term $\mathbb{E}(T2)$ with the
Rademacher complexity, as stated in the following lemma.

######  Lemma 8 (Adapted from Lemma 1, dziugaite2015training ).

Following notations in Theorem 2 and Lemma 7, define
$\mathcal{G}=\\{k(G_{\bm{\theta}}(\cdot),G_{\bm{\theta}}(\cdot))|\bm{\theta}\in\bm{\Theta}\\}$
and
$\mathcal{G}_{+}=\\{k(G_{\bm{\theta}}(\bm{z}),G_{\bm{\theta}}(\cdot))|\bm{\theta}\in\bm{\Theta},\bm{z}\in\mathcal{Z}\\}$.
Given the set $\mathcal{S}=\\{\bm{z}^{(i)}\\}_{i=1}^{n}$, we have

$\operatorname{\mathbb{E}}(T2)\leq\frac{2}{\sqrt{n-1}}\mathfrak{R}_{n-1}(\mathcal{G}_{+}),$

where $\mathfrak{R}_{n-1}(\mathcal{G}_{+})$ refers to the Rademacher’s
complexity of $\mathcal{G}_{+}$.

In conjunction with the above two lemmas, the term $\mathbb{E}(T2)$ is upper
bounded by the covering number of $\mathcal{G}_{+}$. As such, the proof of
Lemma 5 utilizes the following three lemmas, which are used to formalize the
relation of covering number of two metric spaces, quantify the covering number
of variational quantum circuits, and evaluate the covering number of the space
living in $N$-qudit quantum states, respectively.

######  Lemma 9 (Lemma 5, Barthel2018fundamental ).

Let $(\mathcal{H}_{1},d_{1})$ and $(\mathcal{H}_{2},d_{2})$ be metric spaces
and $f:\mathcal{H}_{1}\rightarrow\mathcal{H}_{2}$ be bi-Lipschitz such that

$d_{2}(f(\bm{x}),f(\bm{y}))\leq
Kd_{1}(\bm{x},\bm{y}),~{}\forall\bm{x},\bm{y}\in\mathcal{H}_{1},$ (42)

and

$d_{2}(f(\bm{x}),f(\bm{y}))\geq
kd_{1}(\bm{x},\bm{y}),~{}\forall\bm{x},\bm{y}\in\mathcal{H}_{1}~{}\text{with}~{}d_{1}(\bm{x},\bm{y})\leq
r.$ (43)

Then their covering numbers obey

$\mathcal{N}(\mathcal{H}_{1},2\epsilon/k,d_{1})\leq\mathcal{N}(\mathcal{H}_{2},\epsilon,d_{2})\leq\mathcal{N}(\mathcal{H}_{1},\epsilon/K,d_{1}),$
(44)

where the left inequality requires $\epsilon\leq kr/2$.

######  Lemma 10 (Lemma 2, du2021efficient ).

Define the operator group as

$\mathcal{H}_{circ}:=\left\\{\hat{U}(\bm{\theta})\Pi_{j}\hat{U}(\bm{\theta})^{\dagger}|\bm{\theta}\in\Theta\right\\}.$
(45)

Suppose that the employed encoding Ansatz $\hat{U}(\bm{\theta})$ containing in
total $N_{g}$ gates, each gate $\hat{u}_{i}(\bm{\theta})$ acting on at most
$k$ qudits, and $N_{gt}\leq N_{g}$ gates in $\hat{U}(\bm{\theta})$ are
trainable. The $\epsilon$-covering number for the operator group
$\mathcal{H}_{circ}$ with respect to the operator-norm distance obeys

$\mathcal{N}(\mathcal{H}_{circ},\epsilon,\|\cdot\|)\leq\left(\frac{7N_{gt}\|\Pi_{j}\|}{\epsilon}\right)^{d^{2k}N_{gt}},$
(46)

where $\|\Pi_{j}\|$ denotes the operator norm of $\Pi_{j}$.

######  Lemma 11.

Define the input state group as
$\mathcal{B}:=\left\\{\rho_{\bm{z}}:=\hat{U}(\bm{z})^{\dagger}(\ket{\bm{0}}\bra{\bm{0}})\hat{U}(\bm{z})\Big{|}\bm{z}\in\mathcal{Z}\right\\}$.
Suppose that the employed quantum circuit $\hat{U}(\bm{z})$ containing in
total $N_{ge}$ parameterized gates to load $\bm{z}$ and each gate
$\hat{u}_{i}(\bm{z})$ acting on at most $k$ qudits. The $\epsilon$-covering
number for $\mathcal{B}$ with respect to the operator-norm distance obeys

$\mathcal{N}(\mathcal{B},\epsilon,\|\cdot\|)\leq\left(\frac{7N_{ge}}{\epsilon}\right)^{d^{2k}N_{ge}}.$
(47)

###### Proof of Lemma 11.

The proof is identical to that presented in Lemma 2 of Ref. du2021efficient .
∎

We are now ready to prove Lemma 5.

###### Proof of Lemma 5.

Recall the aim of Lemma 5 is to obtain the upper bound of
$\operatorname{\mathbb{E}}(T2)$. In conjunction with Lemmas 7 and 8, we obtain

$\operatorname{\mathbb{E}}(T2)\leq\operatorname{\mathbb{E}}\frac{2}{\sqrt{n-1}}\inf_{\alpha>0}\left(4\alpha+\frac{12}{\sqrt{n-1}}\int_{\alpha}^{1}\sqrt{\ln(\mathcal{N}((\mathcal{G}_{+})_{|\mathcal{S}},\epsilon,\|\cdot\|_{2})}d\epsilon\right),$
(48)

where
$\mathcal{G}_{+}=\\{k(G_{\bm{\theta}}(\bm{z}),G_{\bm{\theta}}(\cdot))|\bm{\theta}\in\bm{\Theta},\bm{z}\in\mathcal{Z}\\}$
and $\mathcal{S}$ denotes the set $\\{\bm{z}^{(1)},...,\bm{z}^{(n-1)}\\}$
sampled from the prior distribution $\operatorname{\mathbb{P}}_{\mathcal{Z}}$,
and
$(\mathcal{G}_{+})_{|\mathcal{S}}=\\{[k(G_{\bm{\theta}}(\bm{z}),G_{\bm{\theta}}(\bm{z}^{(i)})]_{i=1:n-1}:\operatorname{\bm{\theta}}\in\bm{\Theta},\bm{z}\in\mathcal{Z}\\}$
denotes the set of vectors formed by the hypothesis with $\mathcal{S}$. In
other words, the upper bound of $\operatorname{\mathbb{E}}(T2)$ is quantified
by the covering number
$\mathcal{N}((\mathcal{G}_{+})_{|\mathcal{S}},\epsilon,\|\cdot\|_{2})$.

We next follow the definition of covering number to quantify how
$\mathcal{N}((\mathcal{G}_{+})_{|\mathcal{S}},\epsilon,\|\cdot\|_{2})$ depends
on the structure information of the employed Ansatz and the input quantum
states. Denote $\mathcal{Q}_{\epsilon_{1}}$ as an $\epsilon_{1}$-covering of
the set
$\mathcal{Q}_{1}=\\{G_{\operatorname{\bm{\theta}}}(\bm{z})|\operatorname{\bm{\theta}}\in\bm{\Theta}\\}$
and $\mathcal{Q}_{\epsilon_{3}}$ as an $\epsilon_{3}$-covering of the set
$\mathcal{Q}=\\{G_{\operatorname{\bm{\theta}}}(\bm{z})|\bm{z}\in\bm{\mathcal{Z}}\\}$.
Then, the covering number
$\mathcal{N}((\mathcal{G}_{+})_{|\mathcal{S}},\epsilon,\|\cdot\|_{2})$ can be
upper bounded by
$\mathcal{N}((\mathcal{Q}_{1})_{|\mathcal{S}},\epsilon_{1},\|\cdot\|_{2})$ and
$\mathcal{N}((\mathcal{Q}_{3})_{|\mathcal{S}},\epsilon_{3},\|\cdot\|_{3})$.
Mathematically, according to the explicit expression of
$(\mathcal{G}_{+})_{|\mathcal{S}}$, we have for any $(\bm{\theta},\bm{z})$ and
$(\bm{\theta}^{\prime},\bm{z}^{\prime})$

$\displaystyle\Big{\|}[k(G_{\bm{\theta}}(\bm{z}),G_{\bm{\theta}}(\bm{z}^{(i)}))]_{i=1:n-1}-[k(G_{\bm{\theta}^{\prime}}(\bm{z}^{\prime}),G_{\bm{\theta}^{\prime}}(\bm{z}^{(i)}))]_{i=1:n-1}\Big{\|}_{2}$
$\displaystyle=$
$\displaystyle\Big{\|}[k(G_{\bm{\theta}}(\bm{z}),G_{\bm{\theta}}(\bm{z}^{(i)}))]_{i=1:n-1}-[k(G_{\bm{\theta}^{\prime}}(\bm{z}),G_{\bm{\theta}}(\bm{z}^{(i)}))]_{i=1:n-1}+[k(G_{\bm{\theta}^{\prime}}(\bm{z}),G_{\bm{\theta}}(\bm{z}^{(i)}))]_{i=1:n-1}$
$\displaystyle-[k(G_{\bm{\theta}^{\prime}}(\bm{z}),G_{\bm{\theta}^{\prime}}(\bm{z}^{(i)}))]_{i=1:n-1}+[k(G_{\bm{\theta}^{\prime}}(\bm{z}),G_{\bm{\theta}^{\prime}}(\bm{z}^{(i)}))]_{i=1:n-1}-[k(G_{\bm{\theta}^{\prime}}(\bm{z}^{\prime}),G_{\bm{\theta}^{\prime}}(\bm{z}^{(i)}))]_{i=1:n-1}\Big{\|}_{2}$
$\displaystyle\leq$
$\displaystyle\Big{\|}[k(G_{\bm{\theta}}(\bm{z}),G_{\bm{\theta}}(\bm{z}^{(i)}))]_{i=1:n-1}-[k(G_{\bm{\theta}^{\prime}}(\bm{z}),G_{\bm{\theta}}(\bm{z}^{(i)}))]_{i=1:n-1}\Big{\|}_{2}+\Big{\|}[k(G_{\bm{\theta}^{\prime}}(\bm{z}),G_{\bm{\theta}}(\bm{z}^{(i)}))]_{i=1:n-1}$
$\displaystyle-[k(G_{\bm{\theta}^{\prime}}(\bm{z}),G_{\bm{\theta}^{\prime}}(\bm{z}^{(i)}))]_{i=1:n-1}\Big{\|}_{2}+\Big{\|}[k(G_{\bm{\theta}^{\prime}}(\bm{z}),G_{\bm{\theta}^{\prime}}(\bm{z}^{(i)}))]_{i=1:n-1}-[k(G_{\bm{\theta}^{\prime}}(\bm{z}^{\prime}),G_{\bm{\theta}^{\prime}}(\bm{z}^{(i)}))]_{i=1:n-1}\Big{\|}_{2}$
$\displaystyle\leq$ $\displaystyle
C_{3}\left(\sqrt{n-1}\big{\|}G_{\bm{\theta}}(\bm{z})-G_{\bm{\theta}^{\prime}}(\bm{z})\big{\|}+\Big{\|}\big{[}\big{\|}G_{\bm{\theta}^{\prime}}(\bm{z}^{(i)})-G_{\bm{\theta}}(\bm{z}^{(i)})\big{\|}\big{]}_{i=1:n-1}\Big{\|}_{2}+\sqrt{n-1}\big{\|}G_{\bm{\theta}^{\prime}}(\bm{z})-G_{\bm{\theta}^{\prime}}(\bm{z}^{\prime})\big{\|}\right),$
(49)

where the first inequality uses the triangle inequality and the last
inequality exploits $C_{3}$-Lipschitz property of the kernel. Following the
definition of covering number, the above relationship indicates that if for
any $\operatorname{\bm{\theta}}$ there exists
$\operatorname{\bm{\theta}}^{\prime}$ such that
$\big{\|}G_{\bm{\theta}}(\bm{z})-G_{\bm{\theta}^{\prime}}(\bm{z})\big{\|}\leq\epsilon_{1}$
holds for every $\bm{z}$, and for any $\bm{z}$ there exists $\bm{z}^{\prime}$
such that
$\big{\|}G_{\bm{\theta}}(\bm{z})-G_{\bm{\theta}}(\bm{z}^{\prime})\big{\|}\leq\epsilon_{3}$
holds for every $\operatorname{\bm{\theta}}$, the composition of the covering
sets $\mathcal{Q}_{\epsilon_{1}}$ and $\mathcal{Q}_{\epsilon_{3}}$ forms the
covering set of $(\mathcal{G}_{+})_{|\mathcal{S}}$. That is, the covering
number of $(\mathcal{G}_{+})_{|\mathcal{S}}$ is upper bounded by

$\mathcal{N}((\mathcal{G}_{+})_{|\mathcal{S}},C_{3}\sqrt{n-1}(2\epsilon_{1}+\epsilon_{3}),\|\cdot\|_{2})\leq\mathcal{N}(\mathcal{Q}_{1},\epsilon_{1},\|\cdot\|_{2})\times\mathcal{N}(\mathcal{Q}_{3},\epsilon_{3},\|\cdot\|_{2}).$
(50)

In other words, to quantify the $\epsilon$-covering of
$(\mathcal{G}_{+})_{|\mathcal{S}}$, it is equivalent to deriving the upper
bound of
$\mathcal{N}(\mathcal{Q}_{1},\epsilon/(3C_{3}\sqrt{n-1}),\|\cdot\|_{2})$ and
$\mathcal{N}(\mathcal{Q}_{3},\epsilon/(3C_{3}\sqrt{n-1}),\|\cdot\|_{2})$,
respectively. We next separately derive these two quantities.

The upper bound of
$\mathcal{N}(\mathcal{Q}_{1},\epsilon/(3C_{3}\sqrt{n-1}),\|\cdot\|_{2})$. Let
$\mathcal{Q}_{4}$ be an $\frac{\epsilon}{3C_{3}d^{N}\sqrt{n-1}}$-cover of
$\mathcal{H}_{circ}$ in Eq. (45). Then, for any $\operatorname{\bm{\theta}}$,
there exists $\operatorname{\bm{\theta}}^{\prime}$ such that
$\|\hat{U}(\operatorname{\bm{\theta}})\Pi_{j}\hat{U}(\operatorname{\bm{\theta}})-\hat{U}(\operatorname{\bm{\theta}}^{\prime})\Pi_{j}\hat{U}(\operatorname{\bm{\theta}}^{\prime})\|\leq\frac{\epsilon}{3C_{3}d^{N}\sqrt{n-1}}$
for every $j$ with
$\hat{U}(\operatorname{\bm{\theta}}^{\prime})\Pi_{j}\hat{U}(\operatorname{\bm{\theta}}^{\prime})\in\mathcal{Q}_{4}$.
This leads that for any $\bm{z}$, we have

$\displaystyle\Big{\|}G_{\bm{\theta}}(\bm{z})-G_{\bm{\theta}^{\prime}}(\bm{z})\Big{\|}_{2}$
$\displaystyle=$
$\displaystyle\left\|[\operatorname{Tr}(\hat{U}(\operatorname{\bm{\theta}})\Pi_{j}\hat{U}(\operatorname{\bm{\theta}})^{\dagger}\rho_{\bm{z}})-\operatorname{Tr}(\hat{U}(\operatorname{\bm{\theta}}^{\prime})\Pi_{j}\hat{U}(\operatorname{\bm{\theta}}^{\prime})^{\dagger}\rho_{\bm{z}})]_{j=1:d^{N}}\right\|_{2}$
$\displaystyle\leq$
$\displaystyle\left\|[\LARGE\|\hat{U}(\operatorname{\bm{\theta}})\Pi_{j}\hat{U}(\operatorname{\bm{\theta}})^{\dagger}-\hat{U}(\operatorname{\bm{\theta}}^{\prime})\Pi_{j}\hat{U}(\operatorname{\bm{\theta}}^{\prime})^{\dagger}\LARGE\|]_{j=1:d^{N}}\right\|_{2}$
$\displaystyle\leq$ $\displaystyle
d^{N}\frac{\epsilon}{3C_{3}d^{N}\sqrt{n-1}}$ $\displaystyle=$
$\displaystyle\frac{\epsilon}{3C_{3}\sqrt{n-1}},$ (51)

where the first inequality comes from the Cauchy-Schwartz inequality and the
second inequality follows the definition of covering number.

The above observation means that the covering set of
$\mathcal{N}(\mathcal{Q}_{1},\epsilon/(3C_{3}\sqrt{n-1}),\|\cdot\|_{2})$ is
independent with $\bm{z}$ and its covering number is upper bound by
$\mathcal{N}(\mathcal{H}_{circ},\frac{\epsilon}{3C_{3}d^{N}\sqrt{n-1}},\|\cdot\|_{2})$.
Then, by leveraging the results in Lemma 10, we obtain