[5]Sebastian Schmitt

1]Kirchhoff-Institut für Physik, Universität Heidelberg, Im Neuenheimer Feld
227, Heidelberg, 69120, Germany

2]Zapata Computing Canada Inc., 25 Adelaide St E, Toronto, M5C3A1, Canada
3]Institute of Physics, Ecole Polytechnique Fédérale de Lausanne (EPFL),
Station 3, Lausanne, 1015, Switzerland 4]Alqor UG (haftungsbeschränkt),
Alexanderstr. 65, Frankfurt am Main, 60489, Germany 5]Honda Research Institute
Europe GmbH, Carl-Legien-Str. 30, Offenbach, 63073, Germany

# Data re-uploading with a single qudit

Noah L. Wach  Manuel S. Rudolph  Fred Jendrzejewski  sebastian.schmitt@honda-
ri.de [  [  [  [  [

###### Abstract

Quantum two-level systems, i.e. qubits, form the basis for most quantum
machine learning approaches that have been proposed throughout the years.
However, higher dimensional quantum systems constitute a promising alternative
and are increasingly explored in theory and practice. Here, we explore the
capabilities of multi-level quantum systems, so-called qudits, for their use
in a quantum machine learning context. We formulate classification and
regression problems with the data re-uploading approach and demonstrate that a
quantum circuit operating on a single qudit is able to successfully learn
highly non-linear decision boundaries of classification problems such as the
MNIST digit recognition problem. We demonstrate that the performance strongly
depends on the relation between the qudit states representing the labels and
the structure of labels in the training data set. Such a bias can lead to
substantial performance improvement over qubit-based circuits in cases where
the labels, the qudit states and the operators employed to encode the data are
well-aligned. Furthermore, we elucidate the influence of the choice of the
elementary operators and show that a squeezing operator is necessary to
achieve good performances. We also show that there exists a trade-off for
qudit systems between the number of circuit-generating operators in each
processing layer and the total number of layers needed to achieve a given
accuracy. Finally, we compare classification results from numerically exact
simulations and their equivalent implementation on actual IBM quantum
hardware. The findings of our work support the notion that qudit-based
algorithms exhibit attractive traits and constitute a promising route to
increasing the computational capabilities of quantum machine learning
approaches.

###### keywords:

Quantum machine learning, qudits, parameterized quantum circuits, data re-
uploading

##  1 Introduction

In recent years, the field of quantum machine learning has attracted much
attention. There, quantum circuits are employed as central processing units
for data-driven applications (Biamonte et al, 2017; Schuld and Petruccione,
2018; Dunjko and Briegel, 2018). While it is currently not clear whether or
not quantum processing can provide a benefit on practical machine learning
problems (Schuld and Killoran, 2022; Schuld, 2021), there has been some
evidence that quantum machine learning models can outperform classical models
in certain tasks (Liu et al, 2021; Sweke et al, 2021; Gyurik and Dunjko, 2022;
Gyurik et al, 2022). While most studies, theoretical (Bharti et al, 2022;
Montanaro, 2016) as well as experimental (Graham et al, 2022; Pino et al,
2021; Kjaergaard et al, 2020), focus on quantum systems consisting of two-
level quantum systems, i.e., quantum bits (qubits), quantum computing hardware
and algorithms can also be based on $d$-level systems, which are typically
called qudits (Wang et al, 2020; Ringbauer et al, 2022). Such qudit systems
were shown to have advantages in specific contexts (Cozzolino et al, 2019;
Sheridan and Scarani, 2010) and have already been applied to several tasks
(Bravyi et al, 2022; Deller et al, 2023; Weggemans et al, 2022). However, a
full evaluation on application-relevant tasks is still lacking.

Currently, it is not clear whether there is a fundamental advantage or
disadvantage of utilizing qudit systems over their qubit counterparts for
quantum machine learning or other application domains such as quantum
optimization. However, qudits provide a complementary route to increasing the
Hilbert space size in pursuit of better computation performance. This is an
alternative direction to qubit systems, where the route to larger Hilbert
spaces is to increase the number of qubits. Among other challenges, increasing
the number of qubits comes with increased difficulty of engineering high-
fidelity interactions between separate qubits, which are technologically
challenging and typically involve larger gate errors than single qubit
operations, see for example, Kjaergaard et al (2020), Fedorov et al (2022) or
Resch and Karpuzcu (2019). In that regard, expanding the local Hilbert space
dimension by utilization of qudit systems seems promising, since certain
interactions between spatially separated qubits could instead be implemented
by local qudit operations, and thus might prove to be more efficient (Fischer
et al, 2022; Ringbauer et al, 2022). We discuss several of such aspects of
qudit system at various parts in this work.

We explore the usage of qudit systems in the context of the data re-uploading
(Pérez-Salinas et al, 2020) quantum machine learning approach to build
regression and multi-class classification models. In this scheme, a single
qudit provides a natural way of encoding multiple classes by representing each
class label as an orthogonal basis state. We focus on the prominent data re-
uploading architecture, since it was shown in the original work that a single
qubit is already sufficient to implement a universal classifier. Due to the
comparably small resource requirement data re-uploading circuits were also
experimentally implemented on a trapped ion device (Dutta et al, 2022).
Additionally, the encoding characteristics of these models is well understood,
as it generates increasingly higher Fourier terms with more layers (Schuld et
al, 2021). Thus, it is natural to first evaluate and confirm these same
properties for a single qudit as well. Extending these circuits to multi-
qubit/multi-qudit circuits would allow for more sophisticated setups including
entanglement. However, in this work we refrain from doing this and instead
focus on the most simple, non-trivial case to investigate the fundamental
aspects of qubits and qudits related to basic operators and Hilbert spaces.

This paper is structured as follows: In Sec. 2, we introduce the mathematical
description of qudits. Sec. 3 illustrates the implementation of the data re-
uploading algorithm (Pérez-Salinas et al, 2020) with qudits and shows the
circuit structure as well as the chosen loss functions used during training.
Sec. 4 presents the training procedure which is done numerically and on IBMQ
hardware. To be able to run our model on qubit based quantum hardware, we
present a way to encode qudits with multiple qubits. In Sec. 5, we verify the
expressivity of our model by testing it on a simple regression problem. We
then go on and test our model on multi-class classification problems where we
show an intrinsic bias between the qudit state representation and the data
structure. Finally, we present numerical results of the model when being
trained on the MNIST handwritten digits data set (LeCun and Cortes, 2005). We
additionally investigate an equivalent qubit-based implementation on IBMQ
hardware and the effect of entangling operations on the performance of the
model.

##  2 Qudits

$d$ level quantum systems, typically called qudits, are a generalization of
qubits to $d>2$ and can serve as a basis for quantum information processing.
The Hilbert space is spanned by $d$ orthonormal basis vectors, denoted by
$|0\rangle,|1\rangle,...|d-1\rangle$ and arbitrary qudit states can be
represented by the supersposition
$|\psi\rangle=\sum_{k=0}^{d-1}c_{k}|k\rangle$ with the normalization condition
$\sum_{k=0}^{d-1}|c_{k}|^{2}=1$.

Inspired by cold atom systems (Kasper et al, 2022), we interpret a $d$-level
qudit as a spin with total angular momentum $\ell=\tfrac{d-1}{2}$, such that
the basis state $|k\rangle$ corresponds to the spin eigenstate with angular
momentum $m=\tfrac{2k-d+1}{2}$. A natural set of operations on qudits states,
which is also easily implementable in experiments, is given by the angular
momentum operators $\\{L_{x},L_{y},L_{z}\\}$. These generate rotations around
the corresponding axes and obey the canonical commutation relations of the
special unitary group $SU(2)$, $[L_{i},L_{j}]=i\epsilon_{ijk}L_{k}$. The
action of the angular momentum operators on the qudit basis state are given by

$\displaystyle L_{x}|k\rangle$
$\displaystyle=\tfrac{1}{2}\big{(}\gamma_{d,k+1}|k+1\rangle+\gamma_{d,k-1}|k-1\rangle\big{)}$
(1) $\displaystyle L_{y}|k\rangle$
$\displaystyle=\tfrac{1}{2i}\big{(}\gamma_{d,k+1}|k+1\rangle-\gamma_{d,k-1}|k-1\rangle\big{)}$
(2) $\displaystyle L_{z}|k\rangle$ $\displaystyle=\tfrac{2k-d+1}{2}|k\rangle$
(3)

where $k\in[0,d-1]$ and with $\gamma_{d,k}=\sqrt{(d-k-1)(k+1)}$.

There are various ways to define a universal gate set to realize arbitrary
actions in the qudit Hilbert space, see e.g. Wang et al (2020) and Luo et al
(2014). For a single qudit, as it is considered in this work, we choose the
two angular momentum operators $L_{x}$ and $L_{z}$ and the squeezing or one-
axis twisting operator $L_{z^{2}}=L_{z}^{2}$. For $d>2$ this additional gate
is needed to be able to generate any state by (possibly many) repeated finite
rotations as detailed in Kasper et al (2022) and Giorda et al (2003). The
reason for this is that the iterated commutators of these three operators
generate all $d^{2}-1$ Hermitian basis operators, which are necessary to
generate all unitary operations of the $SU(d)$ group.

Equivalent to qubits, the gates for qudit circuits are then generated by
exponentiation of the basic operators which implements the rotations

$\displaystyle R_{j}(\theta)=e^{-i\theta L_{j}},$ (4)

with $j\in\\{x,z,z^{2}\\}$ and where $\theta\in\mathbb{R}$ are free
parameters.

a b

c

Figure 1: a: Schematic representation of $d=7$ qudit states on a generalized
Bloch sphere. b: Schematic illustration of the action of the three operators
$R_{x}$ (left), $R_{z}$ (middle) and $R_{z^{2}}$ (right) on a qudits state. c:
Illustration of the data re-uploading circuit structure

In Fig. 1 we illustrate the qudit states (panel A) and the action of the
elementary operators by showing the Husimi-Q quasi-probability distribution
(Husimi, 1940) on a generalized Bloch sphere in panel B. The pure rotation
does not deform the probability distributions, but applying the squeezing
operation leads to a deformation of the state.

By choosing the operator set $\\{L_{x},L_{z},L_{z}^{2}\\}$ we impose a ladder
structure on the qudit target states. This primarily arises from the operator
$L_{x}$, which couples each state $|k\rangle$ to its adjacent states
$|k+1\rangle$ and $|k-1\rangle$, as it is illustrated in Eq. 1.

##  3  Data re-uploading with a single qudit

We utilize a single $d$-level qudit and implement the quantum machine learning
model as a data re-uploading quantum circuit (Pérez-Salinas et al, 2020; Jerbi
et al, 2023). The quantum circuit in its general form is build up from $L$
layers and encodes a quantum state, which depends on the input data
$\mathbf{x}$ as

$\displaystyle|\mathbf{x},\bm{\omega},\bm{\theta}\rangle$
$\displaystyle=\prod_{l=1}^{L}U(\mathbf{x},\bm{\omega}^{(l)},\bm{\theta}^{(l)})|0\rangle\,,$
(5)

where $|0\rangle$ is the initial state. The characteristic of the data re-
uploading architecture is that the unitary operation of each layer $l$
encompasses data dependent unitaries, which are parametrized by the scaling
parameters $\bm{\omega}^{(l)}$ and data independent operations with free
parameters $\bm{\theta}^{(l)}$.

We tested several layer structures and found that they all produce similar
results. In the following we report results for two architectures. The first
one is inspired by classical Euler rotations, where the unitaries of each
layer have the structure:

$\displaystyle
U(\mathbf{x},\bm{\omega}^{(l)},\bm{\theta}^{(l)})=W(\bm{\theta}^{(l)})S(\mathbf{x},\mathbf{\omega}^{(l)})\,.$
(6)

The data encoding block $S$ of each layer consists of alternating $x$ and $z$
rotations,

$\displaystyle
S(\mathbf{x},\bm{\omega}^{(l)})=R_{\alpha}(x_{D}\omega_{D}^{(l)})\cdots{R}_{z}(x_{2}\omega_{2}^{(l)}){R}_{x}(x_{1}\omega_{1}^{(l)})$
(7)

where the number of rotations is determined by the dimensionality $D$ of the
input data and consequently $\alpha=x$ ($\alpha=z$) in case $D$ is odd (even).
The alternating $x$ and $z$ rotations is chosen to ensure that these are non-
commuting. This is necessary to distinguish between the individual dimensions
of the data vector. If only $x$ (or $z$) rotations were chosen to encode the
data, the classifier would only be able to learn the sum of the input data.

The data-independent block in each layer is composed of a sequence of three
rotations followed by a squeezing gate $R_{z^{2}}$ as the last operation, i.e.

$\displaystyle
W(\bm{\theta}^{(l)})={R}_{z^{2}}(\theta^{(l)}_{4}){R}_{x}(\theta^{(l)}_{3}){R}_{z}(\theta^{(l)}_{2}){R}_{x}(\theta^{(l)}_{1})$
(8)

The first three operations give rise to Euler angles, starting from
$|0\rangle$, and thus the freedom to create overlap with an arbitrary qudit
state. The total number of adjustable parameters of a $L$-layer model is given
by $(4+D)L$. The action of this circuit structure is illustrated in Fig. 1 C.

The second architecture considered here is inspired by the simplified form
presented by Pérez-Salinas et al (2020) and has the structure:

$\displaystyle
U(\mathbf{x},\bm{\omega}^{(l)},\bm{\theta}^{(l)})=e^{-i\sum_{j}^{D}(\theta_{j}^{(l)}+\omega_{j}^{(l)}x_{j})L_{c(j)}-i\theta_{D+1}^{(l)}L_{z^{2}}}\,.$
(9)

Here the first term in the exponent is the sum over the three angular momentum
operators, i.e. the generators of the $SU(2)$, and the function $c(j)=(j\mod
3)$ selects one of them. The second term in the exponent is a generalization
of the original simplified architecture by including the squeezing operator in
each layer. The total number of adjustable parameters for an $L$-layer model
of this structure is given by $(2D+1)L$.

We like to point out that in this form both architectures implement the
aforementioned ladder structure, since the data encoding is done with the
angular momentum operators, that only couple each qudit basis state to its
adjacent states.

In our work we approach supervised classification and regression tasks by
using qudit-based quantum circuits. In a supervised learning setting, there
exists a set of $N$ training samples $(\mathbf{x}_{i},y_{i})$ with
$i=1,\dots,N$, which consist of pairs of input samples $\mathbf{x}$ with
corresponding output values $y$. The input samples are real-valued
$D$-dimensional vectors $\mathbf{x}\in\mathbb{R}^{D}$ while the output values
are either real numbers or a finite set of integers for regression and
classification tasks, respectively.

For classification problems the output values $y\in(0,1,\dots,d-1)$ indicate
to which of the $d$ classes the data sample x belongs. In the quantum
formulation, each class label is represented by a basis state of the $d$-level
qudit $|y\rangle$ with $y=0,\dots,d-1$. The model prediction, i.e., the
probability that a data sample $\mathbf{x}$ belongs to class $y$, can then
conveniently be calculated from the overlap of the label state and the qudit
wave function obtained from the quantum circuit with input $\mathbf{x}$,

$\displaystyle P(y|\mathbf{x},\bm{\omega},\bm{\theta})=|\langle
y|\psi(\mathbf{x},\bm{\omega},\bm{\theta})\rangle|^{2}\,.$ (10)

Training the quantum circuit is achieved by minimizing a loss function over
the given training data set
$\mathcal{D}=\\{(\textbf{x}_{i},y_{i})\\}_{i=1,\dots,N}$. The overlap of Eq.
(10) is the basis for formulating the mean squared error (MSE) loss function,

$\displaystyle\mathcal{L}_{\text{MSE}}(\bm{\omega},\bm{\theta})$
$\displaystyle=\frac{1}{N}\sum_{i=1}^{N}\big{(}\langle\bar{y}_{i}\rangle-
y_{i}\big{)}^{2}$ (11)

with the average predicted label of the quantum model

$\displaystyle\langle\bar{y}_{i}\rangle=\sum_{y=0}^{d-1}y\,P(y|\mathbf{x}_{i},\bm{\omega},\bm{\theta})\,.$
(12)

Another popular choice is the overlap loss as used in Pérez-Salinas et al
(2020),

$\displaystyle\mathcal{L}_{\text{overlap}}(\bm{\omega},\bm{\theta})=\sum_{i=1}^{N}\big{(}1-P(y_{i}|\mathbf{x}_{i},\bm{\omega},\bm{\theta})\big{)}.$
(13)

The learning procedure amounts to adjusting the parameters of the quantum
circuit $(\bm{\omega},\bm{\theta})$ in order to minimize the loss function,
which is done by running a classical optimization algorithm.

After the quantum circuit has been trained its accuracy is evaluated by
analyzing its predictions of the output variables on a test data set, i.e. a
set of data samples not used during the training procedure. For a
classification task the predicted output labels is given by the basis state
with the highest probability in the quantum state with the corresponding input
data sample, i.e.

$\displaystyle
y_{i}^{\mathrm{predicted}}=\mathrm{argmax}_{y}P(y|\mathbf{x}_{i},\bm{\omega}_{\mathrm{opt}},\bm{\theta}_{\mathrm{opt}})\,,$
(14)

where $(\bm{\omega}_{\mathrm{opt}},\bm{\theta}_{\mathrm{opt}})$ are the
optimized values of the circuit parameters. The accuracy of the trained model
can then be evaluated by calculating the fraction of correctly predicted
labels in the test data set,

$\displaystyle\text{Accuracy}=\frac{1}{N_{\mathrm{test}}}\sum_{i\in\mathcal{D}_{\text{test}}}\delta_{y_{i}^{\mathrm{predicted}},y_{i}}\,,$
(15)

where $\mathcal{D}_{\text{test}}$ denotes the test data set which contains
$N_{\mathrm{test}}$ data samples and $\delta_{a,b}$ is the Kronecker delta.

The MSE loss of Eq. (11) is also suitable to learn regression tasks. In that
case the output variables are finite-range continuous variables,
$y\in[0,d-1]$. The resulting qudit state of the trained quantum circuit is
then a superposition of basis states and the predicted output value for input
$\mathbf{x}_{i}$ is calculated as the expectation value of Eq. (12),

$\displaystyle\
\langle\bar{y}_{i}\rangle^{\mathrm{predicted}}=\sum_{y=0}^{d-1}y\,P(y|\mathbf{x}_{i},\bm{\omega}_{\mathrm{opt}},\bm{\theta}_{\mathrm{opt}})\,.$
(16)

For simulations running on actual quantum hardware, the probability
distribution of Eq. (10) is estimated by performing a finite number of
measurement shots and recording the measurement results as a histogram. This
approximative distribution is then used to calculate the predicted output
values of Eqs. (14) and (16).

##  4 Experimental setup

We perform the training of the quantum circuit utilizing exact numerical
simulations of the qudit states and quantum gates. The parameter values of
$\bm{\omega}$ and $\bm{\theta}$ are initialized randomly in the range
$[-\pi,\pi]$. As classical optimization algorithms for minimizing the loss
function we employ the ADAM optimizer (Kingma and Ba, 2014) paired with the
exact gradients calculated by the automatic differentiation package JAX
(Bradbury et al, 2018). Additionally, we also used L-BFGS-B and Powell
optimization approaches from the scipy library (Virtanen et al, 2020), where
we do not utilize automatic differentiation. Apart from differences in the run
time for the training, the results obtained with all approaches were always
comparable. If not stated otherwise, all models are trained on randomly
selected data sets with size $N=750$. The performance is evaluated on a
separate randomly selected test data set, which contains $\tfrac{N}{3}=250$
data samples. In order to obtain reliable statistics of the results, we run 60
different simulations for each setting, each time randomly varying the data
set and the model initialization. To visualize the decision boundaries of the
trained classifiers, we utilize the visualization library orqviz (Rudolph et
al, 2021).

In addition to the numerically exact simulation, in 5.6 we re-train and
evaluate the qudit quantum circuit on the IBM ibmq_lima hardware using the
qiskit (Treinish et al, 2023) framework. This allows us to estimate the impact
of gate errors and noise of actual NISQ hardware on the learning performance.
As the IBM hardware naturally operates on qubits, we employ a mapping of the
$d$-level qudit Hilbert space to $d-1$ qubits, which is inspired by cold atom
systems (Kasper et al, 2022; Santra et al, 2022). The qudit basis state
$|k\rangle$ is represented by the qubit Dicke-state $|D^{d-1}_{k}\rangle$,
i.e. $|k\rangle\to|D^{d-1}_{k}\rangle$ (Gasieniec et al, 2019). The $k^{th}$
Dicke state $|D^{d-1}_{k}\rangle$ of $d-1$ qubits is given by the equal
superposition of all states which have $k$ qubits in the state $|1\rangle$ and
$d-1-k$ in state $|0\rangle$, i.e.

$\displaystyle|D^{d-1}_{k}\rangle=\begin{pmatrix}d-1\\\
k\end{pmatrix}^{-\tfrac{1}{2}}\sum_{x\in\\{0,1\\}^{d-1},hw(x)=k}|x\rangle\,.$
(17)

where $hw(x)$ indicates the Hamming weight of string $x$, i.e. the number of
1’s in $x$. The angular momentum operators for the $d-1$ qubit states are
defined as the sum over the single-qubit operators,
$L^{\text{tot}}_{a}=\sum_{j=0}^{d-1}L_{a}^{j}$ with $a=\\{x,y,z\\}$, and they
act as described by Eqs. (1) on the Dicke states. In particular, the Dicke
state $|D^{d-1}_{k}\rangle$ and the qudit state $|k\rangle$ have the same
$z$-component of the angular momentum, i.e.
$L^{\text{tot}}_{z}|D^{d-1}_{k}\rangle=\tfrac{2k-d+1}{2}|D^{d-1}_{k}\rangle$.

In this representation the squeezing operation consists of all pairwise qubit
interactions,

$\displaystyle
L^{\text{tot}}_{z^{2}}=\big{(}L^{\text{tot}}_{z}\big{)}^{2}=\sum_{i,j}L_{z}^{i}L_{z}^{j}$
(18)

which is implemented as two-qubit $zz$-rotation gates on the hardware
(Treinish et al, 2023). From this form it is clear that the squeezing operator
has the capability to generate correlation and entanglement between the
individual qubits (Santra et al, 2022). On the qubit device, we start from the
optimized parameters found by the training with the exact simulation and re-
train the model on the actual hardware. There, we perform 512 measurement
shots for each qiskit circuit evaluation.

For comparison we also report the accumulated results on classification tasks
of a standard classical machine learning approach, namely the scikit-learn
(Pedregosa et al, 2018) implementation of the random forest (RF) classifier
with 100 estimators, a $k$-nearest neighbor classifier with $k=3$ ($k$nn) and
a support vector classifier (SVC). The performance of these approaches were
always comparable and we report the cumulative results of running each
algorithm 50 times on randomized data stets.

##  5 Results

Figure 2: Results of trained data re-uploading models with structure of Eqs.
(6)-(8) using a $d=3$ qutrit with one (left) and two (right) layers for the
regression task of learning the function in Eq. (19) (blue line). The purple
dots indicate the results of the numerically exact model simulation obtained
and the green dots the results from re-training and evaluation on the IBM
ibmq_lima hardware

###  5.1 Expressivity in one dimension

First, we examine the expressivity of the data re-uploading circuit with a
single qudit on a continuous one-dimensional regression problem analogous to
Schuld et al (2021). We train a model with one qutrit, i.e. a $d=3$ qudit, to
learn the simple function

$\displaystyle f(x)=\tfrac{1}{2}\big{(}\cos{(2x)}+\cos{(3.5x)}\big{)}$ (19)

with  $\ignorespaces x\in[-\pi,\pi]$ . As the model output we use the
expectation value of Eq. (12) but shift it to match the data range, i.e.
$f_{i}^{\mathrm{predicted}}=\langle\bar{y_{i}}\rangle-1$. For training the
quantum circuit we employ the MSE loss function of Eq. (11) and use a training
set of 100 linearly distributed samples.

We show the results of a $L=1$ layer model in the left panel of Fig. 2. It is
evident that this model is not able to learn the function properly. This
confirms the previous insight for qubit circuits (Schuld et al, 2021), that
data re-uploading models learn truncated Fourier series, and that a circuit
containing only one angle parametrized by the input can only encode one
Fourier component. In the right panel we show the results of a model with
$L=2$ layers. As expected, this model is now able to learn the function with
two Fourier coefficients exactly. The derivation is analogous to the qubit
case (Schuld et al, 2021), but is not shown in this work. Apart from the
results obtained by numerically exact simulations, we also include results
from the evaluation on the IBM ibmq_lima hardware (green dots in the plot).
These predicted values are generally noisy which result from the inherent
errors in the quantum circuit, as well as the shot noise from the finite
number of samples used to estimate the probability distribution of Eq. (10).

###  5.2 Two-dimensional classification tasks

Figure 3: Results of the seven-class horizontal stripe classification problem
with circuit structure of Eqs. (6)-(8). In the upper row the qudit states are
aligned with the class labels, while in the lower row the class labels are
randomly assigned to the qudit states as illustrated in the pictures on the
left. The first stripe pattern shows the ground truth and the training data
samples. The middle and right stripe patterns show the classification regions
obtained after training with three and six layers, respectively. The rightmost
plots show the statistics of classification accuracy, obtained from 50
independent training runs, as a function of layers in the quantum circuit with
(blue) and without (green) the squeezing operation in the $W$ blocks. Colored
boxes indicate 25% and 75% percentiles and horizontal whiskers the minimal and
maximal values. In the right panels, cML indicates the results of the
classical machine learning approaches

Inspired by the original benchmark of the data re-uploading algorithm (Pérez-
Salinas et al, 2020), we investigate the performance of the qudit circuit with
the structure of Eqs. (6)-(8) on various two-dimensional multi-class
classification problems. The data samples are located on a two-dimensional
square $\mathbf{x}=(x_{1},x_{2})\in[-1,1]^{2}$, where each sample is
associated with one out of $d$ classes. In the first problem setting, the
classes are arranged in parallel horizontal stripes. Fig. 3 shows the results
for seven classes, where we used a $d=7$ qudit to represent the classes in the
quantum circuit.

In the upper row of the figure, we show results from the case where we align
the qudit states with the labels in such a way, that the $z$-components of the
spin are in order with the class label. In that case, adjacent classes are
represented by qudit states with adjacent $z$-spin values. Under these
circumstances, the model has a strong inductive bias towards the data set
caused by the chosen ladder structure. This is illustrated in the leftmost
figure where we draw the qudit states on the generalized Bloch sphere. The
lowest qudit state $|0\rangle$ is associated with the class of the lowest
(blue) stripe, the second lowest qudit $|1\rangle$ with the second lowest
stripe, and so on. The corresponding results show that the data re-uploading
circuit can predict this data set almost perfectly with three or more layers,
$L\geq 3$ (blue graph in top right plot). Remarkably, the performance of the
data re-uploading circuit is even better than the classical machine learning
models shown on the far right of the right panel. However, the learned classes
and decision boundaries, as shown in the middle panels of the Figure, can
still differ from the ground truth. This is due to the small size of the
training data set, which necessarily leads to small random variations of the
learned decision boundaries, depending on the precise location of the training
data close to the decision boundaries.

The importance of the squeezing operation $R_{z^{2}}$ in the $W$ operator of
Eq. (8) is highlighted by observing the massively degraded performance of the
same circuits without this gate (green graph in the top right panel of Fig.
3). Without squeezing, the median accuracy saturates at around $0.7$ while
with squeezing the median accuracy reaches $0.95$ and higher. This performance
difference is attributed to the fact, that the squeezing operator is necessary
to allow for the representation of arbitrary unitary operations in the qudit
Hilbert space.

Figure 4: Learned classification regions of a single qudit classifier circuit
with $L=5$ layers trained on the first two (a), three (b) and five (c) classes
(i.e. digits) of the MNIST data set, which was compressed down to two
dimensions using PCA. Each background color indicates one region associated
with the same label. The training data samples are shown in the plots and
colored according to their true label. (d) Accuracy of the qudit classifier as
a function of the number of layers for various numbers of classes. RF denotes
the random forest classifier for comparison

The second row of Fig. 3 shows the performance when the class labels are
randomly assigned to the qudit states. This removes the inductive bias of the
model and makes the problem much harder to learn for the qudit quantum
circuit, since the ladder structure used for the data encoding does not align
to the data set. Consequently, the accuracy drops significantly and many more
layers are necessary to recover the performance level of the scenario with
aligned labels.

The plots of the accuracies also show the accumulated results of the three
classical machine learning classifiers RF, SVC and $k$nn for comparison. The
performance of the quantum circuits including squeezing with randomized
assignment of qudit states to labels is comparable to the classical
approaches. For aligned labels the quantum circuit even slightly outperform
the classical approaches.

We also considered several other two-dimensional multi-class classification
problems and trained data re-uploading models on several horizontal stripe
data sets with varying number of stripes (i.e. classes), as well as data sets
where the stripes are not horizontal but rotated by an angle. We also
investigated the models on data sets where the class regions are given by
concentric rings with approximately the same width and where the center of the
rings is somewhere in the plane. The results (not shown) on those models were
always qualitatively similar to the ones presented here. Squeezing is always
necessary to achieve good performance and when the label order is aligned with
the qudit states, the performance is consistently higher. The overall
performance was slightly reduced for the tilted stripes and the concentric
rings and the variance in the results was also slightly larger as compared to
the horizontal stripes cases presented here.

###  5.3 Classifying MNIST data

As the next application example, we train the model of Eqs. (6)-(8) on subsets
of a scikit-learn (Pedregosa et al, 2018) version of the MNIST handwritten
digits data set (LeCun and Cortes, 2005). This version includes down-sampled
images with $8$x$8$ pixels instead of the $28$x$28$ pixels of the original
MNIST data set. Since it is very computationally demanding to encode $8\times
8=64$ dimensional data samples into the quantum circuit, we reduce the input
dimension further using the principal component analysis (PCA) (Jolliffe and
Cadima, 2016).

In Fig. 4(a)-(c) we visualize the classification boundaries of a $L=5$ layer
circuit for two, three and five classes, where the input dimension is reduced
to $D=2$ using a PCA. The plots show that the data re-uploading classifier is
able to learn highly non-linear decision boundaries. It can also be seen that
the classifier tends to produce disconnected classification regions due to the
oscillatory nature of parametrized quantum circuits. The statistics of the
accuracy for various classes is shown in Fig. 4 (d) as a function of the
quantum circuit layers. It can be observed that the accuracy, as expected,
increases with more layers, and that increasing the number of classes in the
problem reduces the accuracy. For more classes, the reduction to two
dimensions using PCA leads to more spacial overlap between classes, which
makes the problems inherently noisy and limits the overall achievable
accuracy. The overlapping classes can be directly observed in panel (c).
Additionally, panel (d) shows the result from 50 runs of a random forest (RF)
classifier. The accuracy of the quantum-based classifier approaches the values
of the RF model with increasing number of layers. However, the variance in the
result is significantly larger for the data re-uploading circuit. One reason
for this is found in the increasingly more complex classical optimization
problem when increasing the number of parameters in the quantum circuit.

###  5.4 Qudit vs Qubit

The quantum circuits we employed up to this point used a single $d$-level
qudit to solve classification problems with $d$ classes, where each basis
state encodes one class label. While it may appear less natural, multi-class
classification problems can also be learned with a data re-uploading circuit
operating with a single qubit (Pérez-Salinas et al, 2020). In those
approaches, the different classes are represented by single-qubit quantum
states which are chosen to be maximally orthogonal. Unless a two-class
classification problems is considered, where the labels states are $|0\rangle$
and $|1\rangle$, these states cannot be fully orthogonal to each other. For a
$d=6$ class example, we choose the eigenstates of the three spin operators,
i.e.
$|y\rangle\in\\{|0\rangle,|1\rangle,\tfrac{1}{\sqrt{2}}(|0\rangle+|1\rangle),\tfrac{1}{\sqrt{2}}(|0\rangle-|1\rangle),\tfrac{1}{\sqrt{2}}(|0\rangle+i|1\rangle),\tfrac{1}{\sqrt{2}}(|0\rangle-i|1\rangle)\\}$,
as the maximally orthogonal label states. Note that in this situation, the
overlap of Eq. (10) as a function of the labels is no longer a proper
probability distribution since $\sum_{y}P(y)>1$.

The natural question which arises is whether there is any difference when
using qubit or qudit data re-uploading circuits for multi-class classification
problems. Therefore, we study and compare the performance of a single qubit as
well as a single qudit on several problems. For the single qubit approach, we
utilize the simplified data re-uploading structure of Eqs. (9). Here, the
squeezing operator can be removed from the circuit since it is proportional to
the identity, $L_{z^{2}}=\tfrac{\mathds{1}}{4}$, and therefore only applies a
global phase.

Figure 5:  Comparison of $d=6$ multi-class classification performance of qubit
and qudit data re-uploading circuits with the simplified structure of Eq. (9).
Left: tilted $D=2$ dimensional stripes data set with a rotation angle of
$27^{\circ}$. Qudit accuracies are shown for aligned and randomized label and
state assignment, as well as with aligned labels and qudit states, but with a
randomized $\tilde{L}_{x}$ in the encoding. Right: six randomly selected
digits of the MNIST data set which are reduced to $D=2$ input dimensions using
a PCA

Fig. 5 shows the results where the qubit and qudit models were trained on two
different classification problems with $d=6$ classes and $D=2$ input
dimensions. The left panel of Fig. 5 shows the classification accuracy as a
function of the circuit layers for the tilted stripes data set, where the
horizontal stripes from Fig. 3 are rotated by an angle of $27^{\circ}$. It can
be seen that the accuracy of the qubit and qudit circuits are comparable for
the case where the class labels were randomly assigned to the qudit basis
states. However, for labels aligned with the qudit states, the performance is
consistently higher for the qudit circuits. This result is similar to the one
obtained for the horizontal stripe data set reported in Fig. 3 and can be
explained by the ladder structure employed in the qudit circuits. This gives
rise to the inductive bias and leads to an performance improvement in case the
structure of the data encoding operators are aligned with the data. This view
is supported by a slight variation of the setup: we consider aligned labels
and basis states but replace the $L_{x}$ operator in the encoding scheme with
a randomized version,
$\tilde{L}_{x}=\sum_{k}(L_{\mathcal{P}(k+1),\mathcal{P}(k)}+L_{\mathcal{P}(k-1),\mathcal{P}(k)})$.
Here, $\mathcal{P}$ denotes a random permutation of the label set
$k=0,\dots,d-1$ and $L_{k,k^{\prime}}$ generates a transition from state
$k^{\prime}$ to state $k$. These operators do not implement a ladder
structure, since the $\tilde{L}_{x}$ generate transitions between random
states. We indeed observe in Fig. 5 that the median performance then decreases
to the similar level as for the situation with a ladder structure, but
randomized labels.

The right panel shows the results of the qubit and qudit data re-uploading
circuits for the MNIST handwritten digits data set limited to six randomly
selected digits (i.e. classes) and where each image is reduced to two input
dimensions using a PCA. Here, qubit and qudit approaches are comparable in
their performance, while the qubit architectures seem to slightly outperform
the qudit ones, especially for smaller circuit depths. In this problem, the
decision boundaries between the different classes are highly non-linear as
discussed before. Therefore, there is no apparent favorable alignment between
qudit basis states and class labels, and consequently also no inductive bias
which could lead to an improved qudit performance.

In our simulations, the loss function and the classification accuracy are
calculated numerically exact with full access to the quantum state. When
running on real quantum hardware, this cannot be done and one needs to prepare
and sample, i.e. measure, the quantum state multiple times in order to
estimate the probabilities/overlaps of Eq. (10). For the qudit system, where
each class label is associated with an orthogonal basis state in the
measurement basis, the statistics of the measurement outcomes directly
translate to estimating the probabilities. For qubit systems with non-
orthogonal label states (i.e., for $d>2$), different measurement protocols
such as quantum state tomography or quantum state discrimination (Barnett and
Croke, 2009) need to be employed. For fixed number for measurement shots,
these lead to a slightly increased error probability for discriminating
between non-orthogonal states. Additionally, the difference in overlap between
a true label state and an undesired label state is less pronounced when
different label states have a finite overlap. For qudits, this difference is
always one since $P_{\text{qudit}}(y|y^{\prime})=\delta_{y,y^{\prime}}$ for
label states $y,y^{\prime}$ (here, basis states). In the qubit representation,
the difference is $\leq 1$ since
$P_{\text{qubit}}(y|y^{\prime})=\delta_{y,y^{\prime}}+\sum_{y^{\prime\prime}\neq
y^{\prime}}c_{y^{\prime\prime}}\delta_{y,y^{\prime\prime}}$ with $c_{y}\geq
0$. For example, in the case of $d=6$ classes considered here,
$P_{\text{qubit}}(0|y^{\prime})=|\langle
0|y^{\prime}\rangle|^{2}=\tfrac{1}{2}$ for $y^{\prime}\in\\{2,3,4,5\\}$. This
can lead to a reduced training signal in the loss functions using the overlap
of Eq. (10), since even contributions from incorrect label states have non-
zero overlap and therefore reduce the loss. Obtaining the overlaps using a
finite number of measurement samples necessarily adds noise to the estimates,
which in turn makes the problem of discriminating between correctly and
wrongly predicted labels more difficult. As a consequence, the shot noise is
expected to have a more pronounced negative effect on the training as well as
prediction performance for multi-class problems when overlapping label states
are used.

###  5.5 Circuit structure and basic operators

For qubit circuits, the spin-$\frac{1}{2}$ Pauli matrices allow to represent
arbitrary single-qubit unitary operations inside each layer. For $d$-level
qudits, one instead needs to include all $d^{2}-1$ generators of the special
unitary group in $d$ dimensions $SU(d)$, to achieve the same arbitrary
control. However, as indicated above and shown in Kasper et al (2022) and
Giorda et al (2003), the three operators $L_{x}$, $L_{z}$ and $L_{z^{2}}$ are
sufficient to represent any unitary operation by repeated finite rotations
with multiple layers. This leads to the question whether there is a benefit
when more than this reduced set of three operators are used in the data re-
uploading circuit. We test this hypothesis by adding the following two types
of operators,

$\displaystyle X_{j}$ $\displaystyle=|0\rangle\langle 0|-|j\rangle\langle
j|\qquad(1\leq j\leq d-1)$ $\displaystyle Y_{j}$
$\displaystyle=|0\rangle\langle j|+|j\rangle\langle 0|\,.$ (20)

The motivation behind this choice is that these operators directly couple the
initial state $|0\rangle$ to all other states $|j\rangle$ and thus may allow
for a more efficient learning. We then use the simplified structure of Eq. (9)
and replace the squeezing operator by the sum over all operators in Eq. (5.5).

The results of the three types of circuit structures on the six-class reduced
MNIST data set are shown in Fig. 6. The left panel shows the accuracies as a
function of the number of circuit layers. First, one can observe that there is
no significant difference between the simplified structure of Eq. (9) and
circuit structure of Eqs. (6)-(7). On the other hand, the performance of the
circuits with the extended set of operators is significantly better. At first
glance this seems to support the hypothesis that adding more operators to the
set generators does in fact enhance the trainability of qudit quantum
circuits. However, adding more operators also introduces more free parameters
to the quantum circuit for a given number of layers, which allows for more
flexibility in the trainable circuit. When comparing the accuracies as a
function of number of free parameters, as shown in the right panel of Fig. 6,
one can observe that the performance is statistically the same for all circuit
structures and number of operators. Therefore, we conclude that it is not the
number of operators which is determining the trainability, but rather the
number of trainable parameters.

This reveals a tradeoff between the complexity of each layer, i.e. the number
of operators and free parameters in each layer, and the total number of layers
which are necessary to achieve a certain accuracy. Including more operators in
each layer allows to achieve good performance with fewer number of layers. On
quantum hardware, where gate errors play an important role, the freedom to
choose the elemental operations provides additional flexibility. And because
different hardware may natively support different gate sets, this allows to
choose configurations which result in running variational quantum circuits
with less errors. For qubits, this is not possible since the three Pauli
matrices form a basis and no additional operators can be constructed.

Figure 6:  Comparison of results of qudit data re-uploading circuits of
different structures on the $d=6$ class MNIST data set with input dimension
$D=2$. The left panels shows the results as function of the number of layers,
while the right panel shows it as function of the degrees of freedom, i.e. the
number of tunable parameters in the circuit (notice: the $x$-axis is not to
scale in the right plot)

###  5.6 Re-training on IBM hardware

Finally, we compare the classification performance of the model of Eqs.
(6)-(8) with and without the squeezing operation between numerically exact
results and the case where the re-training and evaluation is done on actual
ibmq_lima hardware. For the qubit implementation of the qudit circuits we use
the Dicke-state encoding described in Sec. 4. The left panel of Fig. 7 shows
the accuracy as a function of the quantum circuit layers for the first five
digits, i.e. qudit dimension $d=5$, and with input dimension $D=5$. The
numerically exact simulations show the same trend as previously described for
two input dimensions and approach the values of the traditional RF classifier
with an increasing circuit depth. However, when re-trained and evaluated on
actual hardware the performance is only comparable for the first two layers,
after that it saturates and then decreases strongly. This is due to the noise
and infidelities in the actual hardware realization of the entangling gates
used to implement the squeezing operations. Removing the squeezing operations
from the circuit reveals this explicitly, since the accuracies of both
approaches are then comparable as shown in the right panel of Fig. 7.

Figure 7:  Results for the classification of the first five digits of the
MNIST data set with input dimension $D=5$ with (left) and without (right)
squeezing as a function of the layers in the quantum circuit operating with a
$d=5$ qudit. The numerical exact simulations are shown in blue, whereas the
results from ibmq_lima simulations are in green. The performance of a random
forest (RF) model is displayed to the right in each plot

This is an explicit example of a situation where is more efficient to increase
the local Hilbert space and work with qudits, instead of increasing the number
of qubits.

##  6 Discussion

In this work, we demonstrated that multi-level qudit systems are well-suited
to be applied to multi-class classification problems, as each qudit basis
state can naturally encode one class of the data. We implemented data re-
uploading quantum circuits, where we used the angular momentum and the
squeezing operators to build a universal gate set. We illustrated the
capabilities of the qudit-based approach on regression and classification
benchmarks. Owing to the ability to learn highly non-linear classification
boundaries, the models were able to successfully learn on various data sets
and achieve performances comparable to standard classical machine learning
models. Interestingly, the achievable performance was strongly dependent on
the qudit states representing the class labels and their relation to the
structure of the labels in the data set. This intrinsic bias due to the label
alignment can boost the performance of qudit circuits substantially, when the
data set is structured accordingly, which might be beneficial for certain
types of application problems.

We also studied the influence of the choice of the elementary operations and
the layer structure in qudit quantum circuits. There, we found, that the
structure, i.e. the particular sequence and types of rotations, does not
appear to have significant influence on the performance, as long as the number
of degrees of freedom was accounted for. This reveals a trade-off between the
number of elementary operators in the gate set and the number of layers to
achieve the same performance. In some situations it might be advantageous to
utilize the minimum set of operators and to employ more layers, while in
others, more operators and less layers might be the better choice. This is
especially interesting on quantum hardware where different gates typically
have different error rates, and the freedom to choose between several
configurations may allow to minimize the influence of errors on the resulting
performance.

However, our data encoding layers always employed only $L_{z}$ and $L_{x}$
operators and thus implemented a ladder structure. This is linked to the
observed intrinsic bias, and selecting different operators for the data
encoding might mitigate this bias. However, we did not investigate such
extensions and leave them for future work.

It should be noted that we did not employ any of the more sophisticated
techniques to improve the performance of single-qudit data re-uploading
circuits, for example, employing different classical optimizers (Deller et al,
2023; Lavrijsen et al, 2020), fine-tuning hyperparameter settings (Moussa et
al, 2022), and finding better parameter initializations (Sack and Serbyn,
2021; Grant et al, 2019; Egger et al, 2021). All techniques have been shown to
be very beneficial in related contexts and can be used in the future to
improve the current approach.

A necessary next step is to investigate the performance of multi-qudit
circuits, since here we only investigated single-qudit circuits. Interesting
research questions include how the intrinsic bias of a single qudit is
influences a multi-qudit circuit and its learning performance, and what the
role of the set of elementary operators is in these cases. Crucially, the
effect of multi-qudit entangling gates needs to be elucidated.

In summary, our results and discussion support the conclusion that qudit
systems offer a promising alternative quantum computing architecture. There
are several differences to qubit-based systems which could potentially be
leveraged to eventually provide practical benefits for quantum algorithms and
quantum machine learning tasks in particular.

Acknowledgments NLW acknowledges funding from the Honda Research Institute
Europe GmbH for attending the conference on Quantum Techniques in Machine
Learning (QTML) 2022. NLW would like to thank the Van der Waals-Zeeman
Institute in Amsterdam for their extended hospitality. SS acknowledges funding
by the European Union under Horizon Europe Programme – Grant Agreement
101080086 – NeQST. Views and opinions expressed are however those of the
author(s) only and do not necessarily reflect those of the European Union or
European Climate, Infrastructure and Environment Executive Agency (CINEA).
Neither the European Union nor the granting authority can be held responsible
for them.

## Declarations

Conflict of interest The authors declare no competing interests.

Authors’ contributions FJ and NLW conceived the original idea on the
simulations, NLW, FJ and SS conduced the numerical simulations, NLW, MSR and
SS analyzed the results data. All authors jointly wrote and reviewed the
manuscript.

Availability of data and materials The datasets and numerical details
necessary to replicate this work are available from the corresponding author
upon reasonable request.

## References

  *   * Barnett and Croke (2009) Barnett SM, Croke S (2009) Quantum state discrimination. Advances in Optics and Photonics 1(2):238. 10.1364/AOP.1.000238
  * Bharti et al (2022) Bharti K, Cervera-Lierta A, Kyaw TH, et al (2022) Noisy intermediate-scale quantum algorithms. Reviews of Modern Physics 94(1):015,004. 10.1103/RevModPhys.94.015004
  * Biamonte et al (2017) Biamonte J, Wittek P, Pancotti N, et al (2017) Quantum machine learning. Nature 549(7671):195–202. 10.1038/nature23474
  * Bradbury et al (2018) Bradbury J, Frostig R, Hawkins P, et al (2018) JAX: composable transformations of Python+NumPy programs. URL http://github.com/google/jax
  * Bravyi et al (2022) Bravyi S, Kliesch A, Koenig R, et al (2022) Hybrid quantum-classical algorithms for approximate graph coloring. Quantum 6:678. 10.22331/q-2022-03-30-678
  * Cozzolino et al (2019) Cozzolino D, Da Lio B, Bacco D, et al (2019) High‐Dimensional Quantum Communication: Benefits, Progress, and Future Challenges. Advanced Quantum Technologies 2(12):1900,038. 10.1002/qute.201900038
  * Deller et al (2023) Deller Y, Schmitt S, Lewenstein M, et al (2023) Quantum approximate optimization algorithm for qudit systems. Physical Review A 107(6):062,410. 10.1103/PhysRevA.107.062410
  * Dunjko and Briegel (2018) Dunjko V, Briegel HJ (2018) Machine learning & artificial intelligence in the quantum domain: a review of recent progress. Reports on Progress in Physics 81(7):074,001. 10.1088/1361-6633/aab406
  * Dutta et al (2022) Dutta T, Pérez-Salinas A, Cheng JPS, et al (2022) Single-qubit universal classifier implemented on an ion-trap quantum device. Physical Review A 106(1):012,411. 10.1103/PhysRevA.106.012411
  * Egger et al (2021) Egger DJ, Mareček J, Woerner S (2021) Warm-starting quantum optimization. Quantum 5:479. 10.22331/q-2021-06-17-479
  * Fedorov et al (2022) Fedorov AK, Gisin N, Beloussov SM, et al (2022) Quantum computing at the quantum advantage threshold: a down-to-business review. arXiv
  * Fischer et al (2022) Fischer LE, Chiesa A, Tacchino F, et al (2022) Towards universal gate synthesis and error correction in transmon qudits. arXiv
  * Gasieniec et al (2019) Gasieniec LA, Bärtschi A, Eidenbenz S (2019) Deterministic Preparation of Dicke States. In: Jansson J, Levcopoulos C (eds) Fundamentals of Computation Theory, vol 11651. Springer International Publishing, Cham, p 126–139, 10.1007/978-3-030-25027-0_9, series Title: Lecture Notes in Computer Science
  * Giorda et al (2003) Giorda P, Zanardi P, Lloyd S (2003) Universal quantum control in irreducible state-space sectors: Application to bosonic and spin-boson systems. Physical Review A 68(6):062,320. 10.1103/PhysRevA.68.062320
  * Graham et al (2022) Graham TM, Song Y, Scott J, et al (2022) Multi-qubit entanglement and algorithms on a neutral-atom quantum computer. Nature 604(7906):457–462. 10.1038/s41586-022-04603-6
  * Grant et al (2019) Grant E, Wossnig L, Ostaszewski M, et al (2019) An initialization strategy for addressing barren plateaus in parametrized quantum circuits. Quantum 3:214. 10.22331/q-2019-12-09-214
  * Gyurik and Dunjko (2022) Gyurik C, Dunjko V (2022) On establishing learning separations between classical and quantum machine learning with classical data. arXiv 10.48550/arXiv.2208.06339
  * Gyurik et al (2022) Gyurik C, Cade C, Dunjko V (2022) Towards quantum advantage via topological data analysis. Quantum 6:855. 10.22331/q-2022-11-10-855
  * Husimi (1940) Husimi K (1940) Some Formal Properties of the Density Matrix. 10.11429/ppmsj1919.22.4_264
  * Jerbi et al (2023) Jerbi S, Fiderer LJ, Poulsen Nautrup H, et al (2023) Quantum machine learning beyond kernel methods. Nature Communications 14(1):517. 10.1038/s41467-023-36159-y
  * Jolliffe and Cadima (2016) Jolliffe IT, Cadima J (2016) Principal component analysis: a review and recent developments. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 374(2065):20150,202. 10.1098/rsta.2015.0202
  * Kasper et al (2022) Kasper V, González-Cuadra D, Hegde A, et al (2022) Universal quantum computation and quantum error correction with ultracold atomic mixtures. Quantum Science and Technology 7(1):015,008. 10.1088/2058-9565/ac2d39
  * Kingma and Ba (2014) Kingma DP, Ba J (2014) Adam: A Method for Stochastic Optimization. arXiv 10.48550/ARXIV.1412.6980
  * Kjaergaard et al (2020) Kjaergaard M, Schwartz ME, Braumüller J, et al (2020) Superconducting Qubits: Current State of Play. Annual Review of Condensed Matter Physics 11(1):369–395. 10.1146/annurev-conmatphys-031119-050605
  * Lavrijsen et al (2020) Lavrijsen W, Tudor A, Muller J, et al (2020) Classical Optimizers for Noisy Intermediate-Scale Quantum Devices. In: 2020 IEEE International Conference on Quantum Computing and Engineering (QCE). IEEE, Denver, CO, USA, pp 267–277, 10.1109/QCE49297.2020.00041
  * LeCun and Cortes (2005) LeCun Y, Cortes C (2005) MNIST handwritten digit database. URL http://yann.lecun.com/exdb/mnist/
  * Liu et al (2021) Liu Y, Arunachalam S, Temme K (2021) A rigorous and robust quantum speed-up in supervised machine learning. Nature Physics 17(9):1013–1017. 10.1038/s41567-021-01287-z
  * Luo et al (2014) Luo MX, Chen XB, Yang YX, et al (2014) Geometry of Quantum Computation with Qudits. Scientific Reports 4(1):4044. 10.1038/srep04044
  * Montanaro (2016) Montanaro A (2016) Quantum algorithms: an overview. npj Quantum Information 2(1):15,023. 10.1038/npjqi.2015.23
  * Moussa et al (2022) Moussa C, van Rijn JN, Bäck T, et al (2022) Hyperparameter Importance of Quantum Neural Networks Across Small Datasets. In: Pascal P, Ienco D (eds) Discovery Science, vol 13601. Springer Nature Switzerland, Cham, p 32–46, 10.1007/978-3-031-18840-4_3, series Title: Lecture Notes in Computer Science
  * Pedregosa et al (2018) Pedregosa F, Varoquaux G, Gramfort A, et al (2018) Scikit-learn: Machine Learning in Python. arXiv 10.48550/arXiv.1201.0490
  * Pino et al (2021) Pino JM, Dreiling JM, Figgatt C, et al (2021) Demonstration of the trapped-ion quantum CCD computer architecture. Nature 592(7853):209–213. 10.1038/s41586-021-03318-4
  * Pérez-Salinas et al (2020) Pérez-Salinas A, Cervera-Lierta A, Gil-Fuster E, et al (2020) Data re-uploading for a universal quantum classifier. Quantum 4:226. 10.22331/q-2020-02-06-226
  * Resch and Karpuzcu (2019) Resch S, Karpuzcu UR (2019) Quantum Computing: An Overview Across the System Stack. arXiv
  * Ringbauer et al (2022) Ringbauer M, Meth M, Postler L, et al (2022) A universal qudit quantum processor with trapped ions. Nature Physics 18(9):1053–1057. 10.1038/s41567-022-01658-0
  * Rudolph et al (2021) Rudolph MS, Sim S, Raza A, et al (2021) ORQVIZ: Visualizing High-Dimensional Landscapes in Variational Quantum Algorithms. 10.48550/ARXIV.2111.04695
  * Sack and Serbyn (2021) Sack SH, Serbyn M (2021) Quantum annealing initialization of the quantum approximate optimization algorithm. Quantum 5:491. 10.22331/q-2021-07-01-491
  * Santra et al (2022) Santra GC, Jendrzejewski F, Hauke P, et al (2022) Squeezing and quantum approximate optimization. arXiv
  * Schuld (2021) Schuld M (2021) Supervised quantum machine learning models are kernel methods. arXiv 10.48550/arXiv.2101.11020
  * Schuld and Killoran (2022) Schuld M, Killoran N (2022) Is Quantum Advantage the Right Goal for Quantum Machine Learning? PRX Quantum 3(3):030,101. 10.1103/PRXQuantum.3.030101
  * Schuld and Petruccione (2018) Schuld M, Petruccione F (2018) Supervised Learning with Quantum Computers. Quantum Science and Technology, Springer International Publishing, Cham, 10.1007/978-3-319-96424-9
  * Schuld et al (2021) Schuld M, Sweke R, Meyer JJ (2021) Effect of data encoding on the expressive power of variational quantum-machine-learning models. Physical Review A 103(3):032,430. 10.1103/PhysRevA.103.032430
  * Sheridan and Scarani (2010) Sheridan L, Scarani V (2010) Security proof for quantum key distribution using qudit systems. Physical Review A 82(3):030,301. 10.1103/PhysRevA.82.030301
  * Sweke et al (2021) Sweke R, Seifert JP, Hangleiter D, et al (2021) On the Quantum versus Classical Learnability of Discrete Distributions. Quantum 5:417. 10.22331/q-2021-03-23-417
  * Treinish et al (2023) Treinish M, Gambetta J, Thomas S, et al (2023) Qiskit/qiskit: Qiskit 0.41.0. 10.5281/ZENODO.2573505
  * Virtanen et al (2020) Virtanen P, Gommers R, Oliphant TE, et al (2020) SciPy 1.0: fundamental algorithms for scientific computing in Python. Nature Methods 17(3):261–272. 10.1038/s41592-019-0686-2
  * Wang et al (2020) Wang Y, Hu Z, Sanders BC, et al (2020) Qudits and High-Dimensional Quantum Computing. Frontiers in Physics 8:589,504. 10.3389/fphy.2020.589504
  * Weggemans et al (2022) Weggemans JR, Urech A, Rausch A, et al (2022) Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach. Quantum 6:687. 10.22331/q-2022-04-13-687


$\displaystyle\leq\lambda_{{{\bm{\beta}}}}\left(\left\|{\bm{\beta}}_{S}^{\mathcal{A}}\right\|_{1}+\left\|{\bm{\beta}}_{S^{c}}^{\mathcal{A}}\right\|_{1}\right)-\lambda_{{{\bm{\beta}}}}\left(\left\|\hat{{\bm{\beta}}}_{S}^{\mathcal{A}}\right\|_{1}+\left\|\hat{{\bm{\beta}}}_{S^{c}}^{\mathcal{A}}\right\|_{1}\right)+\frac{1}{2}\lambda_{{{\bm{\beta}}}}\left\|\hat{{\bm{u}}}^{\mathcal{A}}\right\|_{1}$
$\displaystyle\leq\frac{3}{2}\lambda_{{{\bm{\beta}}}}\left\|\hat{{\bm{u}}}_{S}^{\mathcal{A}}\right\|_{1}-\frac{1}{2}\lambda_{{{\bm{\beta}}}}\left\|\hat{{\bm{u}}}_{S^{c}}^{\mathcal{A}}\right\|_{1}+2\lambda_{{{\bm{\beta}}}}\left\|{\bm{\beta}}_{S^{c}}^{\mathcal{A}}\right\|_{1}$
$\displaystyle\leq\frac{3}{2}\lambda_{{{\bm{\beta}}}}\left\|\hat{{\bm{u}}}_{S}^{\mathcal{A}}\right\|_{1}-\frac{1}{2}\lambda_{{{\bm{\beta}}}}\left\|\hat{{\bm{u}}}_{S^{c}}^{\mathcal{A}}\right\|_{1}+2\lambda_{{{\bm{\beta}}}}C_{l}h$
(D.3)

If we assume that the claim we stated does not hold, we consider
$\mathbb{C}=\left\\{{\bm{u}}:\frac{3}{2}\left\|{\bm{u}}_{S}\right\|_{1}-\frac{1}{2}\left\|{\bm{u}}_{S^{c}}\right\|_{1}+2C_{l}h\geq
0\right\\}$. By (D.3) and the convexity of $\hat{L}$, we conclude
$\hat{{\bm{u}}}^{\mathcal{A}}\in\mathbb{C}$. Then for any $t\in(0,1)$, we can
see that

$\frac{1}{2}\left\|t\hat{{\bm{u}}}_{S^{c}}^{\mathcal{A}}\right\|_{1}=t\cdot\frac{1}{2}\left\|\hat{{\bm{u}}}_{S^{c}}^{\mathcal{A}}\right\|_{1}\leq
t\cdot\left(\frac{3}{2}\left\|\hat{{\bm{u}}}_{S}^{\mathcal{A}}\right\|_{1}+2C_{{{\bm{\beta}}}}h\right)\leq\frac{3}{2}\left\|t\hat{{\bm{u}}}_{S}^{\mathcal{A}}\right\|_{1}+2C_{l}h$

which also implies that $t\hat{{\bm{u}}}^{\mathcal{A}}\in\mathbb{C}$. There
exists certain $t$ satisfying that
$\left\|t\hat{{\bm{u}}}^{\mathcal{A}}\right\|_{2}>8\kappa_{2}C_{l}h\sqrt{\frac{\log
d}{n_{\mathcal{A}}+n_{0}}}+$
$3\frac{\sqrt{s}}{\kappa_{1}}\lambda_{{\omega}}+2\sqrt{\frac{C_{l}}{\kappa_{1}}h\lambda_{{\omega}}}$
and $\left\|t\hat{{\bm{u}}}^{\mathcal{A}}\right\|_{2}\leq 1$. We denote
$\tilde{{\bm{u}}}^{\mathcal{A}}=t\hat{{\bm{u}}}^{\mathcal{A}}$ and
$F({\bm{u}})=\hat{L}\left({\bm{\beta}}^{\mathcal{A}}+{\bm{u}},\mathcal{D}\right)-$
$\hat{L}\left({\bm{\beta}}^{\mathcal{A}}\right)+\lambda_{{{\bm{\beta}}}}\left(\left\|{\bm{\beta}}^{\mathcal{A}}+{\bm{u}}\right\|_{1}-\left\|{\bm{\beta}}^{\mathcal{A}}\right\|_{1}\right)$.
As $F(\mathbf{0})=0$ and $F\left(\hat{{\bm{u}}}^{\mathcal{A}}\right)\leq 0$,
by convexity, we establish

$F\left(\tilde{{\bm{u}}}^{\mathcal{A}}\right)=F\left(t\hat{{\bm{u}}}^{\mathcal{A}}+(1-t)\mathbf{0}\right)\leq
tF\left(\hat{{\bm{u}}}^{\mathcal{A}}\right)\leq 0$ (D.4)

However, by Lemma D.6 and the same trick we use for (D.3),

$\displaystyle F\left(\tilde{{\bm{u}}}^{\mathcal{A}}\right)$
$\displaystyle\geq\delta\hat{L}\left(\hat{{\bm{u}}}^{\mathcal{A}},\mathcal{D}\right)+\nabla\hat{L}\left({\bm{\beta}}^{\mathcal{A}}\right)^{T}\tilde{{\bm{u}}}^{\mathcal{A}}-\lambda_{{{\bm{\beta}}}}\left\|{\bm{\beta}}^{\mathcal{A}}\right\|_{1}+\lambda_{{{\bm{\beta}}}}\left\|{\bm{\beta}}^{\mathcal{A}}+\tilde{{\bm{u}}}^{\mathcal{A}}\right\|_{1}$
$\displaystyle\geq
L_{\psi}(T)\kappa_{l}\left\|\tilde{{\bm{u}}}^{\mathcal{A}}\right\|_{2}^{2}-L_{\psi}(T)\left(C_{4}\log{d}\sqrt{\frac{\Psi(p)}{{n_{\mathcal{A}}+n_{0}}}}\right)\left\|\tilde{{\bm{u}}}^{\mathcal{A}}\right\|_{1}\left\|\tilde{{\bm{u}}}^{\mathcal{A}}\right\|_{2}$
$\displaystyle-\frac{3}{2}\lambda_{{{\bm{\beta}}}}\left\|\tilde{{\bm{u}}}_{S}^{\mathcal{A}}\right\|_{1}+\frac{1}{2}\lambda_{{{\bm{\beta}}}}\left\|\tilde{{\bm{u}}}_{S^{c}}^{\mathcal{A}}\right\|_{1}-2\lambda_{{{\bm{\beta}}}}C_{l}h$
$\displaystyle\geq
L_{\psi}(T)\kappa_{l}\left\|\tilde{{\bm{u}}}^{\mathcal{A}}\right\|_{2}^{2}-L_{\psi}(T)C_{4}\log{d}\sqrt{\frac{\Psi(p)}{{n_{\mathcal{A}}+n_{0}}}}\left\|\tilde{{\bm{u}}}^{\mathcal{A}}\right\|_{1}\left\|\tilde{{\bm{u}}}^{\mathcal{A}}\right\|_{2}$
$\displaystyle-\frac{3}{2}\lambda_{{{\bm{\beta}}}}\left\|\tilde{{\bm{u}}}_{S}^{\mathcal{A}}\right\|_{1}-2\lambda_{{{\bm{\beta}}}}C_{l}h$

Due to $\tilde{{\bm{u}}}^{\mathcal{A}}\in\mathbb{C}$, it holds that

$\frac{1}{2}\left\|\tilde{{\bm{u}}}^{\mathcal{A}}\right\|_{1}\leq
2\left\|\tilde{{\bm{u}}}_{S}^{\mathcal{A}}\right\|_{1}+2C_{{{\bm{\beta}}}}h\leq
2\sqrt{s}\left\|\tilde{{\bm{u}}}^{\mathcal{A}}\right\|_{2}+2C_{l}h$

Here, we denote $\kappa_{1}=L_{\psi}(T)\kappa_{l}$,
$\kappa_{2}=C_{4}\log{d}/\kappa_{l}$, when
$n_{\mathcal{A}}+n_{0}>16\kappa_{2}^{2}s\Psi(p)$, we have
$2\frac{C_{4}}{\kappa_{l}}\log{d}\sqrt{\frac{s\Psi(p)}{n_{\mathcal{A}}+n_{0}}}\leq\frac{1}{2}$.Then
it follows

$\displaystyle
F\left(\tilde{{\bm{u}}}^{\mathcal{A}}\right)\geq\frac{1}{2}\kappa_{1}\left\|\tilde{{\bm{u}}}^{\mathcal{A}}\right\|_{2}^{2}-\left[2\kappa_{1}\kappa_{2}\sqrt{\frac{\Psi(p)}{n_{\mathcal{A}}+n_{0}}}C_{{{\bm{\beta}}}}h+\frac{3}{2}\lambda_{{{\bm{\beta}}}}\sqrt{s}\right]\left\|\tilde{{\bm{u}}}^{\mathcal{A}}\right\|_{2}-2\lambda_{{{\bm{\beta}}}}C_{l}h=$
$\displaystyle\frac{1}{2}\kappa_{1}\left\|\tilde{{\bm{u}}}^{\mathcal{A}}\right\|_{2}^{2}-\left[2\kappa_{1}\frac{C_{4}}{\kappa_{l}}\log{d}\sqrt{\frac{\Psi(p)}{n_{\mathcal{A}}+n_{0}}}C_{{{\bm{\beta}}}}h+\frac{3}{2}\lambda_{{{\bm{\beta}}}}\sqrt{s}\right]\left\|\tilde{{\bm{u}}}^{\mathcal{A}}\right\|_{2}-2\lambda_{{{\bm{\beta}}}}C_{l}h>0$

that conflicts with (D.4). Thus our claim at the beginning holds.

Next, we will prove
$\left\|\nabla\hat{L}\left({\bm{\beta}}^{\mathcal{A}}\right)\right\|_{\infty}\lesssim\sqrt{\frac{\log
d}{n_{\mathcal{A}}+n_{0}}}$ with probability at least
$1-(c_{12}d^{-c_{13}}+\sum_{k}n_{k}^{-1}+\sum_{k}e^{\log{n_{k}}-\frac{n_{k}p_{k}}{c_{14}}})$.
To see this, we notice that

$\displaystyle\nabla\hat{L}\left({\bm{\beta}}^{\mathcal{A}}\right)=$
$\displaystyle\frac{1}{n_{\mathcal{A}}+n_{0}}\sum_{k\in\\{0,\mathcal{A}\\}}\left(\bm{\mathbf{Z}}^{(k)}\right)^{T}\left[-\mathbf{Y}^{(k)}+\bm{\psi}^{\prime}\left(\bm{\mathbf{Z}}^{(k)}{\bm{\beta}}^{\mathcal{A}}\right)\right]$
$\displaystyle=$
$\displaystyle\frac{1}{n_{\mathcal{A}}+n_{0}}\sum_{k\in\\{0,\mathcal{A}\\}}\left(\bm{\mathbf{Z}}^{(k)}\right)^{T}\left[-\mathbf{Y}^{(k)}+\bm{\psi}^{\prime}\left(\bm{\mathbf{Z}}^{(k)}\bm{\beta}^{(k)}\right)\right]$
$\displaystyle+\frac{1}{n_{\mathcal{A}}+n_{0}}\sum_{k\in\\{0,\mathcal{A}\\}}\left(\bm{\mathbf{Z}}^{(k)}\right)^{T}\left[-\bm{\psi}^{\prime}\left(\bm{\mathbf{Z}}^{(k)}\bm{\beta}^{(k)}\right)+\bm{\psi}^{\prime}\left(\bm{\mathbf{Z}}^{(k)}{\bm{\beta}}^{\mathcal{A}}\right)\right]$
(D.5)

By extending Lemma 6 of [39] for network dependency in our settings, under
Assumptions D.1 and the fact $n_{\mathcal{A}}\geq Cs\log d$, we have shown in
Lemma D.7 that

$\frac{1}{n_{\mathcal{A}}+n_{0}}\left\|\sum_{k\in\\{0,\mathcal{A}\\}}\left(\bm{\mathbf{Z}}^{(k)}\right)^{T}\left[-\mathbf{Y}^{(k)}+\bm{\psi}^{\prime}\left(\bm{\mathbf{Z}}^{(k)}{\bm{\beta}}^{(k)}\right)\right]\right\|_{\infty}\lesssim\sqrt{\frac{\log
d}{n_{\mathcal{A}}+n_{0}}}$

with probability at least
$1-(c_{6}d^{-c_{7}}+\sum_{k}n_{k}^{-1}+\sum_{k}e^{\log{n_{k}}-\frac{n_{k}p_{k}}{c_{8}}})$.

The remaining work aims to bound the infinity norm of the second term in
(D.5). We denote
$U_{ij}^{(k)}=\mathbf{Z}_{ij}^{(k)}\left[-\psi^{\prime}\left(\left(\mathbf{Z}_{i}^{(k)}\right)^{T}{\bm{\beta}}^{(k)}\right)+\psi^{\prime}\left(\left(\mathbf{Z}_{i}^{(k)}\right)^{T}{\bm{\beta}}^{\mathcal{A}}\right)\right]$.
Under Assumption D.1, we have shown in Conjecture D.8 that:

$\frac{1}{n_{\mathcal{A}}+n_{0}}\sup_{j=1,\ldots,d}\left|\sum_{k\in\\{0,\mathcal{A}\\}}\sum_{i=1}^{n_{k}}U_{ij}^{(k)}\right|\lesssim\sqrt{\frac{\log
d}{n_{\mathcal{A}}+n_{0}}}$

with probability at least
$1-(c_{9}d^{-c_{10}}+\sum_{k}n_{k}^{-1}+\sum_{k}e^{\log{n_{k}}-\frac{n_{k}p_{k}}{c_{11}}})$.
Hence
$\left\|\nabla\hat{L}\left({\bm{\beta}}^{\mathcal{A}}\right)\right\|_{\infty}\lesssim\sqrt{\frac{\log
d}{n_{\mathcal{A}}+n_{0}}}$ holds with probability at least
$1-(c_{12}d^{-c_{13}}+\sum_{k}n_{k}^{-1}+\sum_{k}e^{\log{n_{k}}-\frac{n_{k}p_{k}}{c_{14}}})$.
We plug this rate into (D.2), and get

$\left\|\hat{{\bm{u}}}^{\mathcal{A}}\right\|_{2}\lesssim
h\log{d}\sqrt{\frac{\Psi(p)}{n_{\mathcal{A}}+n_{0}}}+\sqrt{\frac{s\log
d}{n_{\mathcal{A}}+n_{0}}}+\left(\frac{\log
d}{n_{\mathcal{A}}+n_{0}}\right)^{1/4}\sqrt{h}$ (D.6)

with probability at least
$1-(c_{12}d^{-c_{13}}+\sum_{k}n_{k}^{-1}+\sum_{k}e^{\log{n_{k}}-\frac{n_{k}p_{k}}{c_{14}}})$
when $\lambda_{{{\bm{\beta}}}}\asymp C_{{{\bm{\beta}}}}\sqrt{\frac{\log
d}{n_{\mathcal{A}}+n_{0}}}$ with $C_{{{\bm{\beta}}}}>0$ sufficiently large. As
$\hat{{\bm{u}}}^{\mathcal{A}}\in\mathbb{C}$, (D.6) implies

$\left\|\hat{{\bm{u}}}^{\mathcal{A}}\right\|_{1}\lesssim s\sqrt{\frac{\log
d}{n_{\mathcal{A}}+n_{0}}}+\left(\frac{\log
d}{n_{\mathcal{A}}+n_{0}}\right)^{1/4}\sqrt{sh}+h\left(1+\log
d\sqrt{\frac{s\Psi(p)}{n_{\mathcal{A}}+n_{0}}}\right)$ (D.7)

with probability at least
$1-(c_{12}d^{-c_{13}}+\sum_{k}n_{k}^{-1}+\sum_{k}e^{\log{n_{k}}-\frac{n_{k}p_{k}}{c_{14}}})$.

Step 2:
For our convenience, we state the notation again here:
$\mathcal{D}^{(0)}=\left(\bm{\mathbf{Z}}^{(0)},\mathbf{Y}^{(0)}\right)$,
$\hat{L}^{(0)}\left(\bm{\beta},\mathcal{D}^{(0)}\right)=-\frac{1}{n_{0}}\left(\mathbf{Y}^{(0)}\right)^{T}\mathbf{Z}^{(0)}\bm{\beta}+\frac{1}{n_{0}}\sum_{i=1}^{n_{0}}\psi\left(\left(\mathbf{Z}_{i}^{(0)}\right)^{T}\bm{\beta}\right)$,
$\nabla\hat{L}^{(0)}\left(\bm{\beta},\mathcal{D}^{(0)}\right)=-\frac{1}{n_{0}}\left(\mathbf{Z}^{(0)}\right)^{T}\mathbf{Y}^{(0)}+\frac{1}{n_{0}}\left(\mathbf{Z}^{(0)}\right)^{T}\bm{\psi}^{\prime}\left(\mathbf{Z}^{(0)}\bm{\beta}\right),{\delta}^{\mathcal{A}}=$
${\bm{\beta}}^{(0)}-\bm{\beta}^{\mathcal{A}},\hat{{\bm{\beta}}}^{(0)}=\hat{\bm{\beta}}^{\mathcal{A}}+\hat{{\bm{\delta}}}^{\mathcal{A}},\hat{{\mathbf{v}}}^{\mathcal{A}}=\hat{{\bm{\delta}}}^{\mathcal{A}}-{\bm{\delta}}^{\mathcal{A}}$,
and
$\delta\hat{L}^{(0)}({\bm{\delta}},\mathcal{D})=\hat{L}^{(0)}\left(\hat{\bm{\beta}}^{\mathcal{A}}+{\bm{\delta}},\mathcal{D}^{(0)}\right)-\hat{L}^{(0)}\left(\hat{\bm{\beta}}^{\mathcal{A}}+{\bm{\delta}}^{\mathcal{A}},\mathcal{D}^{(0)}\right)-\nabla\hat{L}^{(0)}\left(\hat{\bm{\beta}}^{\mathcal{A}}+{\bm{\delta}}^{\mathcal{A}},\mathcal{D}^{(0)}\right)^{T}\hat{{\mathbf{v}}}^{\mathcal{A}}$.

Following similar derivations for (D.3), when $\lambda_{\delta}\geq
2\left\|\nabla\hat{L}^{(0)}\left({\bm{\beta}}^{(0)},\mathcal{D}^{(0)}\right)\right\|_{\infty}$,
we establish

$\displaystyle\delta\hat{L}^{(0)}\left(\hat{{\bm{\delta}}}^{\mathcal{A}},\mathcal{D}\right)\leq$
$\displaystyle\lambda_{{\delta}}\left(\left\|{\bm{\delta}}^{\mathcal{A}}\right\|_{1}-\left\|\hat{{\bm{\delta}}}^{\mathcal{A}}\right\|_{1}\right)-\nabla\hat{L}^{(0)}\left(\hat{\bm{\beta}}^{\mathcal{A}}+{\bm{\delta}}^{\mathcal{A}},\mathcal{D}^{(0)}\right)^{T}\hat{{\mathbf{v}}}^{\mathcal{A}}$
$\displaystyle\leq\lambda_{{\bm{\delta}}}\left(2\left\|{\bm{\delta}}^{\mathcal{A}}\right\|_{1}-\left\|\hat{{\mathbf{v}}}^{\mathcal{A}}\right\|_{1}\right)+\left\|\nabla\hat{L}^{(0)}\left({\bm{\beta}}^{(0)},\mathcal{D}^{(0)}\right)\right\|_{\infty}\left\|\hat{{\mathbf{v}}}^{\mathcal{A}}\right\|_{1}$
$\displaystyle-\left[\nabla\hat{L}^{(0)}\left(\hat{\bm{\beta}}^{\mathcal{A}}+{\bm{\delta}}^{\mathcal{A}},\mathcal{D}^{(0)}\right)-\nabla\hat{L}^{(0)}\left({\bm{\beta}}^{(0)},\mathcal{D}^{(0)}\right)\right]^{T}\hat{{\mathbf{v}}}^{\mathcal{A}}$
$\displaystyle\leq
2\lambda_{{\delta}}\left\|{\bm{\delta}}^{\mathcal{A}}\right\|_{1}-\frac{1}{2}\lambda_{{\delta}}\left\|\hat{{\mathbf{v}}}^{\mathcal{A}}\right\|_{1}$
$\displaystyle-\frac{1}{n_{0}}\left[\bm{\psi}^{\prime}\left(\left({\mathbf{Z}}^{(0)}\right)^{T}\left(\hat{\bm{\beta}}^{\mathcal{A}}+{\bm{\delta}}^{\mathcal{A}}\right)\right)-\bm{\psi}^{\prime}\left(\left(\bm{\mathbf{Z}}^{(0)}\right)^{T}{\bm{\beta}}^{(0)}\right)\right]^{T}\hat{{\mathbf{v}}}^{\mathcal{A}}$
$\displaystyle\leq
2\lambda_{{\delta}}\left\|{\bm{\delta}}^{\mathcal{A}}\right\|_{1}-\frac{1}{2}\lambda_{{\delta}}\left\|\hat{{\mathbf{v}}}^{\mathcal{A}}\right\|_{1}+\frac{1}{4c_{0}}M_{\psi}^{2}\cdot\frac{1}{n_{0}}\left\|{\mathbf{Z}}^{(0)}\hat{{\bm{u}}}^{\mathcal{A}}\right\|_{2}^{2}$
$\displaystyle+c_{0}\cdot\frac{1}{n_{0}}\left\|{\mathbf{Z}}^{(0)}\hat{{\mathbf{v}}}^{\mathcal{A}}\right\|_{2}^{2}$
(D.8)

with $c_{0}>0$ being a constant that is enough small. The last inequality
holds according to:

$\displaystyle-\frac{1}{n_{0}}\left[\bm{\psi}^{\prime}\left(\left(\bm{\mathbf{Z}}^{(0)}\right)^{T}\left(\hat{\bm{\beta}}^{\mathcal{A}}+{\bm{\delta}}^{\mathcal{A}}\right)\right)-\bm{\psi}^{\prime}\left(\left({\mathbf{Z}}^{(0)}\right)^{T}{\bm{\beta}}^{(0)}\right)\right]^{T}\hat{{\mathbf{v}}}^{\mathcal{A}}$
$\displaystyle=\frac{1}{n_{0}}\left(\hat{\bm{u}}^{\mathcal{A}}\right)^{T}\left(\bm{\mathbf{Z}}^{(0)}\right)^{T}\Lambda^{(0)}\bm{\mathbf{Z}}^{(0)}\hat{{\mathbf{v}}}^{\mathcal{A}}$
$\displaystyle\leq\frac{1}{4c_{0}}M_{\psi}^{2}\cdot\frac{1}{n_{0}}\left\|\bm{\mathbf{Z}}^{(0)}\hat{{\bm{u}}}^{\mathcal{A}}\right\|_{2}^{2}+c_{0}\cdot\frac{1}{n_{0}}\left\|\bm{\mathbf{Z}}^{(0)}\hat{{\mathbf{v}}}^{\mathcal{A}}\right\|_{2}^{2}$

where
$\Lambda^{(0)}=\operatorname{diag}\left(\left\\{\psi^{\prime\prime}\left(\left(\bm{\mathbf{Z}}_{i}^{(0)}\right)^{T}{\bm{\beta}}^{(0)}+t_{i}\left(\bm{\mathbf{Z}}_{i}^{(0)}\right)^{T}\hat{{\bm{u}}}^{\mathcal{A}}\right)\right\\}_{i=1}^{n_{0}}\right)$
is a $n_{0}\times n_{0}$ diagonal matrix and
$\left\|\Lambda^{(0)}\right\|_{\max}\leq M_{\psi}$.

We denote $\tilde{{\mathbf{v}}}^{\mathcal{A}}=t\hat{\mathbf{v}}^{\mathcal{A}}$
and similar to what we defined before, let
$F^{(0)}({\mathbf{v}})=\hat{L}^{(0)}\left(\hat{\bm{\beta}}^{\mathcal{A}}+{\bm{\delta}}^{\mathcal{A}}+\right.$
$\left.{\mathbf{v}},\mathcal{D}^{(0)}\right)-\hat{L}^{(0)}\left(\hat{\bm{\beta}}^{\mathcal{A}}+{\bm{\delta}}^{\mathcal{A}},\mathcal{D}^{(0)}\right)+\lambda_{{\delta}}\left(\left\|{\bm{\delta}}^{\mathcal{A}}+{\mathbf{v}}\right\|_{1}-\left\|{\bm{\delta}}^{\mathcal{A}}\right\|_{1}\right)$.
As $F(\mathbf{0})=0$ and
$F^{(0)}\left(\hat{{\mathbf{v}}}^{\mathcal{A}}\right)\leq$ 0 , by convexity,
for any $t\in(0,1]$, we establish

$F^{(0)}\left(\tilde{{\mathbf{v}}}_{\mathcal{A}}\right)=F^{(0)}\left(t\hat{{\mathbf{v}}}_{\mathcal{A}}+(1-t)\mathbf{0}\right)\leq
tF^{(0)}\left(\hat{{\bm{u}}}^{\mathcal{A}}\right)\leq 0$ (D.9)

Setting $t\in(0,1]$ ensures that
$\left\|\tilde{\bm{v}}^{\mathcal{A}}\right\|_{2}\leq 1$. By noticing the fact
that
$\left\|\tilde{\bm{v}}^{\mathcal{A}}\right\|_{2}\leq\left\|\tilde{\bm{v}}^{\mathcal{A}}\right\|_{1}$,
we can apply Lemma D.6 on $\tilde{\bm{v}}^{\mathcal{A}}$ with minor
modifications. Also by (D.9) and (D.8), we establish:

$\displaystyle\kappa_{1}\left\|\tilde{{\mathbf{v}}}^{\mathcal{A}}\right\|_{2}^{2}-\kappa_{1}\kappa_{3}\left(\log{d}\sqrt{\frac{\Psi(p)}{{n_{0}}}}\right)\cdot\left\|\tilde{{\mathbf{v}}}^{\mathcal{A}}\right\|_{1}^{2}\leq$
$\displaystyle
F^{(0)}\left(\tilde{{\mathbf{v}}}^{\mathcal{A}}\right)-\nabla\hat{L}^{(0)}\left(\hat{\bm{\beta}}^{\mathcal{A}}+{\bm{\delta}}^{\mathcal{A}},\mathcal{D}^{(0)}\right)^{T}\tilde{{\mathbf{v}}}^{\mathcal{A}}$
$\displaystyle\leq
2\lambda_{{\delta}}\left\|{\bm{\delta}}^{\mathcal{A}}\right\|_{1}-\frac{1}{2}\lambda_{{\delta}}\left\|\tilde{{\mathbf{v}}}^{\mathcal{A}}\right\|_{1}+$
$\displaystyle\frac{1}{4c_{0}}M_{\psi}^{2}\cdot\frac{1}{n_{0}}\left\|{\mathbf{Z}}^{(0)}\hat{{\bm{u}}}^{\mathcal{A}}\right\|_{2}^{2}$
$\displaystyle+c_{0}\cdot\frac{1}{n_{0}}\left\|{\mathbf{Z}}^{(0)}\tilde{{\mathbf{v}}}^{\mathcal{A}}\right\|_{2}^{2}$
(D.10)

with $\kappa_{1}=L_{\psi}(T)\kappa_{l}$, $\kappa_{3}=C_{4}/\kappa_{l}$.

We showed in the proof of Step 1 that
$\left\|\hat{{\bm{u}}}_{S^{c}}^{\mathcal{A}}\right\|_{1}\leq
3\left\|\hat{{\bm{u}}}_{S}^{\mathcal{A}}\right\|_{1}+4C_{l}h$. Next we discuss
about bounding
$\frac{1}{n_{0}}\left\|{\mathbf{Z}}^{(0)}\hat{{\bm{u}}}^{\mathcal{A}}\right\|_{2}^{2}$
by $\left\|\hat{{\bm{u}}}^{\mathcal{A}}\right\|_{2}^{2}$ using this fact.

If $3\left\|\hat{{\bm{u}}}_{S}^{\mathcal{A}}\right\|_{1}\geq 4C_{l}h$, then
$\left\|\hat{{\bm{u}}}_{S^{c}}^{\mathcal{A}}\right\|_{1}\leq
6\left\|\hat{{\bm{u}}}_{S}^{\mathcal{A}}\right\|_{1}$. Then by Lemma D.9 (the
extension on Theorem 1.6 of [37] for network dependency), we have

$\frac{1}{n_{0}}\left\|{\mathbf{Z}}^{(0)}\hat{{\bm{u}}}^{\mathcal{A}}\right\|_{2}^{2}\lesssim\left\|\hat{{\bm{u}}}^{\mathcal{A}}\right\|_{2}^{2}\lesssim\frac{s\log
d}{n_{\mathcal{A}}+n_{0}}+h\cdot\sqrt{\frac{\log d}{n_{\mathcal{A}}+n_{0}}}$
(D.11)

with probability at least
$1-d^{-\tilde{K}}-n_{0}^{-1}-e^{\log{n_{0}}-\frac{n_{0}p}{c}}$.

If $3\left\|\hat{{\bm{u}}}_{S}^{\mathcal{A}}\right\|_{1}<4C_{l}h$, then
$\left\|\hat{{\bm{u}}}_{S^{c}}^{\mathcal{A}}\right\|_{1}\leq
8C_{l}h\leq\sqrt{s}$. Also
$\left\|\hat{{\bm{u}}}^{\mathcal{A}}\right\|_{2}\leq 1$ with probability
$1-(c_{12}d^{-c_{13}}+\sum_{k}n_{k}^{-1}+\sum_{k}e^{\log{n_{k}}-\frac{n_{k}p_{k}}{c_{14}}})$.
We denote

$\displaystyle\Pi_{0}(s)=\left\\{{\bm{u}}\in\mathbb{R}^{p}:\|{\bm{u}}\|_{2}\leq
1,\|{\bm{u}}\|_{0}\leq s\right\\}$
$\displaystyle\Pi_{1}(s)=\left\\{{\bm{u}}\in\mathbb{R}^{p}:\|{\bm{u}}\|_{2}\leq
1,\|{\bm{u}}\|_{1}\leq\sqrt{s}\right\\}$

Due to Lemma 3.1 of [53], $\Pi_{1}(s)\subseteq
2\overline{\operatorname{conv}}\left(\Pi_{0}(s)\right)$, where
$\overline{\operatorname{conv}}\left(\Pi_{0}(s)\right)$ is the closure of
convex hull of $\Pi_{0}(s)$. Similarly, an extension for network dependency on
the proof of Theorem 2.4 in [54] will also conclude (D.11).

Next we bound
$\frac{1}{n_{0}}\left\|\bm{\mathbf{Z}}^{(0)}\tilde{{\mathbf{v}}}^{\mathcal{A}}\right\|_{2}^{2}$
by $\left\|\tilde{{\mathbf{v}}}^{\mathcal{A}}\right\|_{2}^{2}$. From basic
inequality, we establish

$\displaystyle 0$
$\displaystyle\leq\hat{L}^{(0)}\left(\hat{{\bm{\beta}}}^{(0)},\mathcal{D}^{(0)}\right)-\hat{L}^{(0)}\left({\bm{\beta}}^{(0)},\mathcal{D}^{(0)}\right)-\nabla\hat{L}^{(0)}\left({\bm{\beta}}^{(0)},\mathcal{D}^{(0)}\right)^{T}(\hat{{\bm{\beta}}}^{(0)}-{\bm{\beta}}^{(0)})$
$\displaystyle\leq\lambda_{{\delta}}\left(\left\|{\bm{\beta}}^{(0)}-\hat{\bm{\beta}}^{\mathcal{A}}\right\|_{1}-\left\|\hat{{\bm{\delta}}}^{\mathcal{A}}\right\|_{1}\right)+\left\|\nabla\hat{L}^{(0)}\left({\bm{\beta}}^{(0)},\mathcal{D}^{(0)}\right)\right\|_{\infty}\|\hat{{\bm{\beta}}}^{(0)}-{\bm{\beta}}^{(0)}\|_{1}$
$\displaystyle\leq\lambda_{{\delta}}\left(\left\|{\bm{\beta}}^{(0)}-\hat{\bm{\beta}}^{\mathcal{A}}\right\|_{1}-\left\|\hat{{\bm{\delta}}}^{\mathcal{A}}\right\|_{1}\right)+\frac{1}{2}\lambda_{{\delta}}\|\hat{{\bm{\beta}}}^{(0)}-{\bm{\beta}}^{(0)}\|_{1}$
$\displaystyle\leq\frac{3}{2}\lambda_{{\delta}}\left\|{\bm{\beta}}^{(0)}-\hat{\bm{\beta}}^{\mathcal{A}}\right\|_{1}-\frac{1}{2}\lambda_{{\delta}}\left\|\hat{{\bm{\delta}}}^{\mathcal{A}}\right\|_{1}$
$\displaystyle\leq\frac{3}{2}\lambda_{{\delta}}C_{l}h+\frac{3}{2}\lambda_{{\delta}}\left\|\hat{{\bm{u}}}^{\mathcal{A}}\right\|_{1}-\frac{1}{2}\lambda_{{\delta}}\left\|\hat{{\bm{\delta}}}^{\mathcal{A}}\right\|_{1}$
(D.12)

implying

$\left\|\hat{{\mathbf{v}}}^{\mathcal{A}}\right\|_{1}\leq\left\|\hat{{\bm{\delta}}}^{\mathcal{A}}\right\|_{1}+C_{l}h\leq
3\left\|\hat{{\bm{u}}}^{\mathcal{A}}\right\|_{1}+4C_{l}h$

Combined with results by (D.7), we have
$\left\|\tilde{{\mathbf{v}}}^{\mathcal{A}}\right\|_{1}\leq\left\|\hat{{\mathbf{v}}}^{\mathcal{A}}\right\|_{1}\leq\sqrt{s}$
when $s\log d/\left(n_{\mathcal{A}}+n_{0}\right)$ and $h$ are small enough. We
can see
$\delta\hat{L}^{(0)}\left(\hat{{\bm{\delta}}}^{\mathcal{A}},\mathcal{D}\right)>0$
from the strict convexity, which leads to
$\left\|\hat{{\bm{\delta}}}^{\mathcal{A}}\right\|_{1}\leq$
$3\left\|\hat{{\bm{u}}}^{\mathcal{A}}\right\|_{1}+3h$. Then we get

$\left\|\hat{{\mathbf{v}}}^{\mathcal{A}}\right\|_{1}\leq\left\|{\bm{\beta}}^{(0)}-\hat{\bm{\beta}}^{\mathcal{A}}\right\|_{1}+\left\|\hat{{\bm{\delta}}}^{\mathcal{A}}\right\|_{1}\leq
4\left\|\hat{{\bm{u}}}^{\mathcal{A}}\right\|_{1}+4h\leq\sqrt{s}$ (D.13)

Similar to the analysis considering
$3\left\|\hat{{\bm{u}}}_{S}^{\mathcal{A}}\right\|_{1}<4C_{1}h$ above, we
establish

$c_{0}\cdot\frac{1}{n_{0}}\left\|{\mathbf{Z}}^{(0)}\tilde{{\mathbf{v}}}^{\mathcal{A}}\right\|_{2}^{2}\leq
c_{0}\cdot C\left\|\tilde{{\mathbf{v}}}^{\mathcal{A}}\right\|_{2}^{2}$

holds with probability at least
$1-d^{-\tilde{K}}-n_{0}^{-1}-e^{\log{n_{0}}-\frac{n_{0}p}{c}}$. As long as
$c_{0}C<c_{9}/2$, by (D.10), we have

$\displaystyle\kappa_{1}\left\|\tilde{{\mathbf{v}}}^{\mathcal{A}}\right\|_{2}^{2}-\kappa_{1}\kappa_{3}\left(\log{d}\sqrt{\frac{\Psi(p)}{{n_{0}}}}\right)\cdot\left\|\tilde{{\mathbf{v}}}^{\mathcal{A}}\right\|_{1}^{2}$
$\displaystyle\leq$ $\displaystyle
2\lambda_{{\delta}}\left\|{\mathcal{\bm{\delta}}}^{\mathcal{A}}\right\|_{1}-\frac{1}{2}\lambda_{{\delta}}\left\|\tilde{{\mathbf{v}}}^{\mathcal{A}}\right\|_{1}+C\frac{s\log
d}{n_{\mathcal{A}}+n_{0}}+Ch\sqrt{\frac{\log
d}{n_{\mathcal{A}}+n_{0}}}+c_{3}/2\left\|\tilde{{\mathbf{v}}}^{\mathcal{A}}\right\|_{2}^{2}$
(D.14)

with probability at least $1-C^{\prime}n_{0}^{-1}$,
$\kappa_{1}=L_{\psi}(T)\kappa_{l}$, $\kappa_{3}=C_{4}/\kappa_{l}$.

If satisfying
$\lambda_{{\delta}}\left\|{\bm{\delta}}^{\mathcal{A}}\right\|_{1}\leq
C\frac{s\log d}{n_{\mathcal{A}}+n_{0}}+Ch\sqrt{\frac{\log
d}{n_{\mathcal{A}}+n_{0}}}$, then

$\displaystyle\left\|\tilde{{\mathbf{v}}}^{\mathcal{A}}\right\|_{1}\lesssim\left[\frac{s\log
d}{n_{\mathcal{A}}+n_{0}}+h\sqrt{\frac{\log
d}{n_{\mathcal{A}}+n_{0}}}\right]\cdot\sqrt{\frac{1}{\log
d}\sqrt{\frac{n_{0}}{\Psi(p)}}}+\left\|\tilde{{\mathbf{v}}}^{\mathcal{A}}\right\|_{2}^{2}$

Because $\left\|\tilde{{\mathbf{v}}}^{\mathcal{A}}\right\|_{2}\leq 1$, by
(D.14), the following inequality holds

$\left\|\tilde{{\mathbf{v}}}^{\mathcal{A}}\right\|_{2}^{2}\lesssim\frac{s\log
d}{n_{\mathcal{A}}+n_{0}}+h\sqrt{\frac{\log
d}{n_{\mathcal{A}}+n_{0}}}\lesssim\frac{s\log
d}{n_{\mathcal{A}}+n_{0}}+\left[h\sqrt{\frac{\log d}{n_{0}}}\right]\wedge
h^{2}$

with probability at least $1-C^{\prime}n_{0}^{-1}$.

If
$\lambda_{\delta}\left\|{\bm{\delta}}^{\mathcal{A}}\right\|_{1}>C\frac{s\log
d}{n_{\mathcal{A}}+n_{0}}+Ch\sqrt{\frac{\log d}{n_{\mathcal{A}}+n_{0}}}$, then
$\left\|\tilde{{\mathbf{v}}}^{\mathcal{A}}\right\|_{1}\lesssim
h+\left\|\tilde{{\mathbf{v}}}^{\mathcal{A}}\right\|_{2}^{2}$, leading to

$\left\|\tilde{{\mathbf{v}}}^{\mathcal{A}}\right\|_{2}^{2}\lesssim
2\lambda_{{\delta}}\left\|{\bm{\delta}}^{\mathcal{A}}\right\|_{1}-\frac{1}{2}\lambda_{{\delta}}\left\|\tilde{{\mathbf{v}}}^{\mathcal{A}}\right\|_{1}$

which implies $\left\|\tilde{{\mathbf{v}}}^{\mathcal{A}}\right\|_{1}\leq
4\left\|{\bm{\delta}}^{\mathcal{A}}\right\|_{1}\leq 4C_{l}h$. By plugging this
result into (D.14), we obtain

$\left\|\tilde{{\mathbf{v}}}^{\mathcal{A}}\right\|_{2}^{2}\lesssim\frac{s\log
d}{n_{\mathcal{A}}+n_{0}}+\left[h\sqrt{\frac{\log d}{n_{0}}}\right]\wedge
h^{2}$ (D.15)

with probability at least $1-C^{\prime}n_{0}^{-1}$.

When $s\log d/\left(n_{\mathcal{A}}+n_{0}\right)$ and $h$ is small enough, due
to $h\sqrt{\frac{\log d}{{n_{0}}}}=o(1)$, the right side of (D.15) can be very
small, implying $\left\|\tilde{{\mathbf{v}}}^{\mathcal{A}}\right\|_{2}\leq
c<1$ with probability at least $1-C^{\prime}n_{0}^{-1}$. We should notice that
this result holds for any $t\in(0,1]$ such that
$\left\|\tilde{{\mathbf{v}}}^{\mathcal{A}}\right\|_{2}\leq 1$. Finally let’s
consider the vector of interest: $\hat{{\mathbf{v}}}^{\mathcal{A}}$. Suppose
$\left\|\tilde{{\mathbf{v}}}^{\mathcal{A}}\right\|_{2}^{2}\geq\frac{s\log
d}{n_{\mathcal{A}}+n_{0}}+\left[h{\left(\sqrt{\frac{\log
d}{{n_{0}}}}\right)}\right]\wedge h^{2}$ for some constant $C>0$ with
probability at least $C^{\prime}n_{0}^{-1}$, then there exists $t\in(0,1]$
such that $c<\left\|\tilde{{\mathbf{v}}}^{\mathcal{A}}\right\|_{2}\leq 1$.
This contradicts with the fact
$\left\|\tilde{{\mathbf{v}}}^{\mathcal{A}}\right\|_{2}\leq c$ with probability
at least $1-C^{\prime}n_{0}^{-1}$. Hence we establish

$\left\|\hat{{\mathbf{v}}}^{\mathcal{A}}\right\|_{2}^{2}\lesssim\frac{s\log
d}{n_{\mathcal{A}}+n_{0}}+\left[h\sqrt{\left({\frac{\log
d}{{n_{0}}}}\right)}\right]\wedge h^{2}\lesssim 1$

with probability at least $1-C^{\prime}n_{0}^{-1}$.

Similarly, the $\ell_{1}$-bound on $\hat{{\mathbf{v}}}^{\mathcal{A}}$ will be
obtained by going over the analysis procedure of
$\tilde{{\mathbf{v}}}^{\mathcal{A}}$

$\left\|\hat{{\mathbf{v}}}^{\mathcal{A}}\right\|_{1}\lesssim\left[s\sqrt{\frac{\log
d}{n_{\mathcal{A}}+n_{0}}}+h\right]\cdot\sqrt{\sqrt{\frac{1}{\Psi(p)}}}$

with probability at least $1-C^{\prime}n_{0}^{-1}$.

Lastly, we combine the conclusions in this Step 2 with the upper bounds on
$\left\|\hat{{\bm{u}}}^{\mathcal{A}}\right\|_{2}$ and
$\left\|\hat{{\bm{u}}}^{\mathcal{A}}\right\|_{1}$ in Step 1, to complete the
proof.

Combining the above inequalities, we obtain:

$\displaystyle\left\|\hat{\bm{\beta}}^{(0)}-\bm{\beta}^{(0)}\right\|_{2}$
$\displaystyle\leq\left\|\hat{\bm{u}}\right\|_{2}+\left\|\hat{\mathbf{v}}\right\|_{2}\lesssim
h\log{d}\sqrt{\frac{\Psi(p)}{n_{\mathcal{A}}+n_{0}}}+\sqrt{\frac{s\log
d}{n_{\mathcal{A}}+n_{0}}}+\left(\frac{\log
d}{n_{\mathcal{A}}+n_{0}}\right)^{1/4}\sqrt{h}.$

And

$\displaystyle\left\|\hat{\bm{\beta}}^{(0)}-\bm{\beta}^{(0)}\right\|_{1}$
$\displaystyle\leq\left\|\hat{\bm{u}}\right\|_{1}+\left\|\hat{\mathbf{v}}\right\|_{1}\lesssim
s\sqrt{\frac{\log d}{n_{\mathcal{A}}+n_{0}}}+\left(\frac{\log
d}{n_{\mathcal{A}}+n_{0}}\right)^{1/4}\sqrt{sh}+$ $\displaystyle h\left(1+\log
d\sqrt{\frac{s\Psi(p)}{n_{\mathcal{A}}+n_{0}}}\right)+\left[s\sqrt{\frac{\log
d}{n_{\mathcal{A}}+n_{0}}}+h\right]\cdot\sqrt{\sqrt{\frac{1}{\Psi(p)}}}.$

##  Appendix E Additional Experimental Results

In this section, we first conduct additional simulation studies considering
other network models such as SBM and graphon models, and also consider
multiple convolution layers $M=2$ (see in Appendix E.1). Subsequently, we
present complete results of real data analyses including the summary of
averaged Macro F1 and standard deviation of Micro and Macro F1 scores for
transfer learning tasks, as well as the performance considering varying source
and target data training rate in Appendix E.2.

###  E.1 Additional Simulation Results

Here, we conduct simulation studies considering similar settings in Section
5.1 but generating the adjacency matrices from SBM or graphon models.

Figure S1 presents the results for SBM models. Figures S1 (a)(b) were
performed when SBM generated the adjacency matrices of both target and source
domains with between-community connection probability as 0.08 and the within-
community probability as 0.1. Figures S1 (c)(d) were performed when the
adjacency matrices of both target and source domains were generated by SBM
with between-community connection probability as 0.08 and within-community
probability as 0.04.

Figure S1: Performance comparison (MSE) of Trans-GCR (red), GCR (black), Naive
TL (blue) across varying (a)(c) Source sample size, (b)(d) Source-target gap
$h$, for two additional SBM models.

Figure S2 presents the results for graphon models. Figures S2 (a)(b), and
(c)(d) were performed with the adjacency matrices of both target and source
domains generated by two types of graphons, respectively.

Figure S2: Performance comparison (MSE) of Trans-GCR (red), GCR (black), Naive
TL (blue) across varying (a)(c) Source sample size, (b)(d) Source-target gap
$h$, for two additional graphon models.

We also show the performance comparisons when we consider multiple convolution
layers such as $M=2$ in Figure S3.

Figure S3: Performance comparison (MSE) of Trans-GCR (red), GCR (black), Naive
TL (blue) across varying (a) Source sample size, (b) Source-target gap $h$,
(c) Source network density (0.05 means identical densities) (d) Source network
within-community probability (higher value means more discrepancy) when
convolution layers $M=2$.

###  E.2 Additional Real Data Results

Here we present more detailed results from the real data analysis. Table S2
shows the averaged Macro-F1 scores. Table S3 presents the standard deviation
(SD) across various methods and tasks, corresponding to the averaged Micro and
Macro-F1 values we presented in Table 1 and Table S2. We also present the
effect of source training rate and target training rate on Micro-F1 in Figure
S4 for the transfer learning tasks D $\rightarrow$ C, C $\rightarrow$ D, and A
$\rightarrow$ D, in Figure S5 for the transfer learning tasks D $\rightarrow$
A, C $\rightarrow$ A, and A $\rightarrow$ C, respectively.

Table S2: Averaged Macro F1 score of various methods, over 10 replicates, with
source training rate fixed at 0.75 and target training rate fixed at 0.03.

Target | Source | Trans-GCR | GCR | AdaGCN | node2vec | GraphSAGE | GCN | APPNP | attri2vec | SGC | GAT
---|---|---|---|---|---|---|---|---|---|---|---
Macro-F1 (%)
D | C | 73.69 | 69.55 | 73.53 | 60.77 | 66.76 | 66.92 | 59.95 | 63.48 | 66.99 | 66.29
A | 72.94 | 66.95 | 73.37 | 57.97 | 62.01 | 62.76 | 55.43 | 58.08 | 61.78 | 61.97
C&A | 73.74 | 68.89 | 73.61 | 49.13 | 46.15 | 56.73 | 57.55 | 57.54 | 67.13 | 54.65
C | D | 77.23 | 69.67 | 75.41 | 58.02 | 66.02 | 66.71 | 62.61 | 69.02 | 66.61 | 67.61
A | 78.49 | 73.98 | 78.10 | 62.67 | 67.69 | 69.98 | 63.13 | 66.29 | 75.56 | 68.48
D&A | 78.94 | 74.68 | 77.15 | 47.59 | 54.30 | 63.03 | 62.09 | 67.63 | 75.53 | 62.87
A | D | 73.45 | 71.09 | 72.50 | 54.78 | 62.95 | 65.92 | 55.92 | 61.67 | 63.49 | 66.30
C | 74.21 | 72.03 | 73.60 | 59.93 | 65.30 | 64.04 | 56.18 | 63.68 | 72.01 | 67.47
D&C | 75.01 | 72.23 | 74.03 | 44.56 | 56.81 | 60.21 | 54.62 | 62.93 | 70.39 | 63.11

Table S3: Standard deviation for Micro and Macro F1 score of various methods,
over 10 replicates, with source training rate fixed at 0.75 and target
training rate fixed at 0.03.

Target | Source | Trans-GCR | GCR | AdaGCN | node2vec | GraphSAGE | GCN | APPNP | attri2vec | SGC | GAT
---|---|---|---|---|---|---|---|---|---|---|---
Micro-F1 (%)
D | C | <0.01 | <0.01 | 0.01 | 0.01 | 0.01 | 0.01 | 0.02 | 0.01 | 0.02 | 0.01
A | <0.01 | <0.01 | 0.01 | 0.01 | 0.01 | 0.02 | 0.02 | 0.01 | 0.02 | 0.01
C&A | 0.01 | <0.01 | 0.02 | 0.01 | 0.01 | 0.02 | 0.01 | 0.01 | 0.02 | 0.03
C | D | <0.01 | <0.01 | 0.02 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01
A | <0.01 | <0.01 | 0.01 | 0.01 | 0.01 | 0.01 | 0.02 | 0.01 | 0.01 | 0.01
D&A | <0.01 | <0.01 | 0.02 | 0.02 | 0.02 | 0.03 | 0.01 | 0.01 | 0.02 | 0.02
A | D | <0.01 | <0.01 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01
C | <0.01 | <0.01 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01
D&C | <0.01 | <0.01 | 0.01 | 0.01 | 0.02 | 0.04 | 0.01 | 0.01 | 0.03 | 0.02
Macro-F1 (%)
D | C | <0.01 | <0.01 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01 | 0.03 | 0.01
A | <0.01 | <0.01 | 0.01 | 0.01 | 0.01 | 0.02 | 0.02 | 0.01 | 0.04 | 0.02
C&A | 0.01 | <0.01 | 0.02 | 0.02 | 0.01 | 0.04 | 0.01 | 0.04 | 0.02 | 0.03
C | D | <0.01 | <0.01 | 0.02 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01 | 0.02 | 0.02
A | <0.01 | <0.01 | 0.01 | 0.01 | 0.01 | 0.02 | 0.02 | 0.01 | 0.02 | 0.02
D&A | <0.01 | <0.01 | 0.02 | 0.04 | 0.02 | 0.06 | 0.01 | 0.01 | 0.02 | 0.02
A | D | <0.01 | <0.01 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01
C | <0.01 | <0.01 | 0.02 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01 | 0.01
D&C | <0.01 | <0.01 | 0.01 | 0.03 | 0.02 | 0.07 | 0.01 | 0.01 | 0.04 | 0.02

Figure S4: Multi-label classification with varying source training rates
(first column, with target training rate fixed to be 0.03), with varying
target training rate (second column, with source training rate fixed to be
0.75).  Figure S5: Multi-label classification with varying source training
rates (first column, with target training rate fixed to be 0.03), with varying
target training rate (second column, with source training rate fixed to be
0.75).

##  Appendix F Pseudo Code for Algorithms

Here, we summarize the procedure of Trans-GCR in Algorithm 1, and the
procedure of source domain selection in Algorithm 2.

Algorithm 1 Trans-GCR Algorithm

Target data $(\mathbf{A}^{(0)},\mathbf{X}^{(0)},\mathbf{Y}^{(0)})$; Source
data $(\mathbf{A}^{(k)},\mathbf{X}^{(k)},\mathbf{Y}^{(k)}),k\in\mathcal{A}$;
Hyperparameter $M$ and $\lambda$.

Step 1. Preprocessing. Calculate the normalized adjacency matrix
$\mathbf{S}^{(k)}$ based on $\mathbf{A}^{(k)}$, $k\in\\{0,\mathcal{A}\\}$.

Step 2. Pooled source samples. Get pooled source sample with
$\mathbf{S}^{\mathcal{A}}\in\mathbb{R}^{n_{\mathcal{A}}\times
n_{\mathcal{A}}}$,
$\mathbf{X}^{\mathcal{A}}\in\mathbb{R}^{n_{\mathcal{A}}\times d}$,
$\mathbf{Y}^{\mathcal{A}}\in\\{0,1\\}^{n_{\mathcal{A}}\times C}$.

Step 3. Source domain parameter estimation. Get
$\hat{\bm{\beta}}^{\mathcal{A}}$ by Eq. 2.3, using the pooled source samples
$(\mathbf{S}^{\mathcal{A}},\mathbf{X}^{\mathcal{A}},\mathbf{Y}^{\mathcal{A}})$.

Step 4. Domain shift estimation. Obtain domain shift estimate
$\hat{\delta}^{\mathcal{A}}$ using Eq. 3.1 and target data.

Step 5. Target domain parameter estimation. Obtain
$\hat{\bm{\beta}}^{(0)}=\hat{\bm{\beta}}^{\mathcal{A}}+\hat{\delta}^{\mathcal{A}}$.

Output: $\hat{\bm{\beta}}^{(0)}$.

Algorithm 2 Source Domain Transferability Score Calculation Algorithm

Data: Target data $(\mathbf{A}^{(0)},\mathbf{X}^{(0)},\mathbf{Y}^{(0)})$;
Source data
$(\mathbf{A}^{(k)},\mathbf{X}^{(k)},\mathbf{Y}^{(k)}),k=1,\ldots,K$;

Hyperparameters: Number of layers $M$; Cross-validation folds $V$; Number of
selected source data $L$.

Step 1. Target data partition. Randomly partition data points in the target
domain $\\{1,\ldots,n_{0}\\}$ into $V$ subsets of approximately equal size
$s_{1},\ldots,s_{V}$.

Step 2. Training and testing target data construction. Construct testing
target data $(\mathbf{A}^{(0)},\mathbf{X}^{(0)}$, $\mathbf{Y}_{s_{v}}^{(0)})$,
where we only use the label information of nodes in $s_{v}$. Similarly,
construct training target data $(\mathbf{A}^{(0)}$, $\mathbf{X}^{(0)}$,
$\mathbf{Y}_{-s_{v}}^{(0)})$ by excluding the label information of nodes in
$s_{v}$.

Step 3. Cross-validation based score. For $k$th source data, $k=1,\ldots,K$,
repeat the following procedure.

For $v=1,\ldots,V$,

  * •

Model estimation. Apply the transfer learning Algorithm 1 using the source
data $\\{\mathbf{A}^{(k)},\mathbf{X}^{(k)},\mathbf{Y}^{(k)}\\}$ and training
target data
$\\{\mathbf{A}^{(0)},\mathbf{X}^{(0)},\mathbf{Y}_{-s_{v}}^{(0)}\\}$ to obtain
the estimate $\hat{{\bm{\beta}}}_{vk}^{(0)}$ for the target data after
transfer learning.

  * •

Model evaluation Using the learned $\hat{{\bm{\beta}}}_{vk}^{(0)}$ from the
previous step, evaluate its prediction performance in the target domain
testing data
$\\{\mathbf{A}^{(0)},\mathbf{X}^{(0)},\mathbf{Y}_{s_{v}}^{(0)}\\}$ by
calculating the negative log-likelihood value $\mbox{NL}_{v}^{(k)}$ for nodes
in $s_{v}$.

Averaged score over folds. Calculate averaged negative log-likelihood over $V$
folds for each $k$ source data,
$\mbox{NL}^{(k)}=\frac{1}{V}\sum_{v=1}^{V}\mbox{NL}_{v}^{(k)}$

Step 4. Selection. Rank the $K$ sources according to $\mbox{NL}^{(k)}$ and
select among the top $L$ lowest sources as $\hat{\mathcal{A}}$.

Output: $\hat{\mathcal{A}}$ and Transferability score $\mbox{NL}^{(k)}$,
$k=1,\ldots,K$.