Analyzing Convergence in Quantum Neural Networks: Deviations from Neural
  Tangent Kernels
A quantum neural network (QNN) is a parameterized mapping efficiently
implementable on near-term Noisy Intermediate-Scale Quantum (NISQ) computers.
It can be used for supervised learning when combined with classical
gradient-based optimizers. Despite the existing empirical and theoretical
investigations, the convergence of QNN training is not fully understood.
Inspired by the success of the neural tangent kernels (NTKs) in probing into
the dynamics of classical neural networks, a recent line of works proposes to
study over-parameterized QNNs by examining a quantum version of tangent
kernels. In this work, we study the dynamics of QNNs and show that contrary to
popular belief it is qualitatively different from that of any kernel
regression: due to the unitarity of quantum operations, there is a
non-negligible deviation from the tangent kernel regression derived at the
random initialization. As a result of the deviation, we prove the at-most
sublinear convergence for QNNs with Pauli measurements, which is beyond the
explanatory power of any kernel regression dynamics. We then present the actual
dynamics of QNNs in the limit of over-parameterization. The new dynamics
capture the change of convergence rate during training and implies that the
range of measurements is crucial to the fast QNN convergence.
Xuchen You, Shouvanik Chakrabarti, Boyang Chen, Xiaodi Wu
# Analyzing Convergence in Quantum Neural Networks: Deviations from Neural Tangent Kernels

###### Abstract

A quantum neural network (QNN) is a parameterized mapping efficiently implementable on near-term Noisy Intermediate-Scale Quantum (NISQ) computers. It can be used for supervised learning when combined with classical gradient-based optimizers. Despite the existing empirical and theoretical investigations, the convergence of QNN training is not fully understood. Inspired by the success of the neural tangent kernels (NTKs) in probing into the dynamics of classical neural networks, a recent line of works proposes to study over-parameterized QNNs by examining a quantum version of tangent kernels. In this work, we study the dynamics of QNNs and show that contrary to popular belief it is qualitatively different from that of any kernel regression: due to the unitarity of quantum operations, there is a non-negligible deviation from the tangent kernel regression derived at the random initialization. As a result of the deviation, we prove the at-most sublinear convergence for QNNs with Pauli measurements, which is beyond the explanatory power of any kernel regression dynamics. We then present the actual dynamics of QNNs in the limit of over-parameterization. The new dynamics capture the change of convergence rate during training, and implies that the range of measurements is crucial to the fast QNN convergence.

## 1 Introduction

Analogous to the classical logic gates, quantum gates are the basic building blocks for quantum computing. A variational quantum circuit (also referred to as an ansatz) is composed of parameterized quantum gates. A quantum neural network (QNN) is nothing
but an instantiation of learning with parametric models using variational quantum circuits and quantum measurements: A \(p\)-parameter \(d\)-dimensional QNN for a dataset \(\{\mathbf{x}_{i},y_{i}\}\) is specified by an encoding \(\mathbf{x}_{i}\mapsto\boldsymbol{\rho}_{i}\) of the feature vectors into quantum states in an underlying \(d\)-dimensional Hilbert space \(\mathcal{H}\), a variational circuit \(\mathbf{U}(\boldsymbol{\theta})\) with real parameters \(\boldsymbol{\theta}\in\mathbb{R}^{p}\), and a quantum measurement \(\mathbf{M}_{0}\). The predicted output \(\hat{y}_{i}\) is obtained by measuring \(\mathbf{M}_{0}\) on the output \(\mathbf{U}(\boldsymbol{\theta})\boldsymbol{\rho}_{i}\mathbf{U}^{\dagger}( \boldsymbol{\theta})\). Like deep neural networks, the parameters \(\boldsymbol{\theta}\) in the variational circuits are optimized by gradient-based methods to minimize an objective function that measures the misalignments of the predicted outputs and the ground truth labels.

With the recent development of quantum technology, the near-term Noisy Intermediate-Scale Quantum (NISQ) (Preskill, 2018) computer has become an important platform for demonstrating quantum advantage with practical applications. As a hybrid of classical optimizers and quantum representations, QNNs is a promising candidate for demonstrating such advantage on quantum computers available to us in the near future: quantum machine learning models are proved to have a margin over the classical counterparts in terms of the expressive power due the to the exponentially large Hilbert space of quantum states (Huang et al., 2021; Anschuetz, 2022). On the other hand by delegating the optimization procedures to classical computers, the hybrid method requires significantly less quantum resources, which is crucial for readily available quantum computers with limited coherence time and error correction. There have been proposals of QNNs (Dunjko and Briegel, 2018; Schuld and Killoran, 2019) for classification (Farhi et al., 2020; Romero et al., 2017) and generative learning (Lloyd and Weedbrook, 2018; Zoufal et al., 2019; Chakrabarti et al., 2019).

Despite their potential there are challenges in the practical deployment of QNNs. Most notably, the optimization problem for training QNNs can be highly non-convex. The landscape of QNN training may be swarmed with spurious local minima and saddle points that can trap gradient-based optimization methods (You and Wu, 2021; Anschuetz and Kiani, 2022). QNNs with large dimensions also suffer from a phenomenon called the _barren plateau_(McClean et al., 2018), where the gradients of the parameters vanish at random initializations, making convergence slow even in a trap-free landscape. These difficulties in training QNNs, together with the challenge of classically simulating QNNs at a decent scale, calls for a theoretical understanding of the convergence of QNNs.

Neural Tangent KernelsMany of the theoretical difficulties in understanding QNNs have also been encountered in the study of classical deep neural networks: despite the landscape of neural networks being non-convex and susceptible to spurious local minima and saddle points, it has been empirically observed that the training errors decays exponentially in the training time (Livni et al., 2014; Arora et al., 2019) in the highly _over-parameterized_ regime with sufficiently many number of trainable parameters. This phenomenon is theoretically explained by connecting the training dynamics of neural networks to the kernel regression: the kernel regression model generalizes the linear regression by equipping the linear model with non-linear feature maps. Given a training set \(\{\mathbf{x}_{j},y_{j}\}_{j=1}^{m}\subset\mathcal{X}\times\mathcal{Y}\) and a non-linear feature map \(\phi:\mathcal{X}\rightarrow\mathcal{X}^{\prime}\) mapping the features to a potentially high-dimensional feature space \(\mathcal{X}^{\prime}\). The kernel regression solves for the optimal weight \(\mathbf{w}\) that minimizes the mean-square loss \(\frac{1}{2m}\sum_{j=1}^{m}(\mathbf{w}^{T}\phi(\mathbf{x}_{j})-y_{j})^{2}\). The name of kernel regression stems from the fact that the optimal hypothesis \(\mathbf{w}\) depends on the high-dimensional feature vectors \(\{\phi(\mathbf{x}_{j})\}_{j=1}^{m}\) through a
\(m\times m\)_kernel_ matrix \(\mathbf{K}\), such that \(K_{ij}=\phi(\mathbf{x}_{i})^{T}\phi(\mathbf{x}_{j})\). The kernel regression enjoys a linear convergence (i.e. the mean square loss decaying exponentially over time) when \(\mathbf{K}\) is positive definite.

The kernel matrix associated with a neural network is determined by tracking how the predictions for each training sample evolve jointly at random initialization. The study of the neural network convergence then reduces to characterizing the corresponding kernel matrices (the neural tangent kernel, or the NTK). In addition to the convergence results, NTK also serves as a tool for studying other aspect of neural networks including generalization (Canatar et al., 2021; Chen et al., 2020) and stability (Bietti and Mairal, 2019).

The key observation that justifies the study of neural networks with neural tangent kernels, is that the NTK becomes a constant (over time) during training in the limit of infinite layer widths. This has been theoretically established starting with the analysis of wide fully-connected neural networks (Jacot et al., 2018; Arora et al., 2019; Chizat et al., 2019) and later generalized to a variety of architectures (e.g. Allen-Zhu et al. (2019)).

Quantum NTKsInspired by the success of NTKs, recent years have witnessed multiple works attempting to associate over-parameterized QNNs to kernel regression. Along the line there are two types of studies. The first category investigates and compares the properties of the "quantum" kernel induced by the quantum encoding of classical features, where \(K_{ij}\) associated with the \(i\)-th and \(j\)-th feature vectors \(\mathbf{x}_{i}\) and \(\mathbf{x}_{j}\) equals \(\mathrm{tr}(\boldsymbol{\rho}_{i}\boldsymbol{\rho}_{\mathrm{j}})\) with \(\boldsymbol{\rho}_{i}\) and \(\boldsymbol{\rho}_{j}\) being the quantum state encodings, without referring to the dynamics of training (Schuld and Killoran, 2019; Huang et al., 2021; Liu et al., 2022b). The second category seeks to directly establish the quantum version of NTK for QNNs by examining the evolution of the model predictions at random initialization, which is the recipe for calculating the classical NTK in Arora et al. (2019): Shirai et al. (2021) empirically evaluates the direct training of the quantum NTK instead of the original QNN formulation. On the other hand, by analyzing the time derivative of the quantum NTK at initialization, Liu et al. (2022a) conjectures that in the limit of over-parameterization, the quantum NTK is a constant over time and therefore the dynamics reduces to a kernel regression.

Despite recent efforts, a rigorous answer remains evasive whether the quantum NTK is a constant during training for over-parameterized QNNs. We show that the answer to this question is indeed, surprisingly negative: as a result of the unitarity of quantum circuits, there is a finite change in the conjectured quantum NTK as the training error decreases, even in the the limit of over-parameterization.

ContributionsIn this work, we focus on QNNs equipped with the mean square loss, trained using gradient flow, following Arora et al. (2019). In Section 3, we show that, despite the formal resemblance to kernel regression dynamics, the over-parameterized QNN does not follow the dynamics of _any_ kernel regression due to the unitarity: for the widely-considered setting of classifications with Pauli measurements, we show that the objective function at time \(t\) decays at most as a polynomial function of \(1/t\) (Theorem 3.2). This contradicts the dynamics of any kernel regression with a positive definite kernel, which exhibits convergence with \(L(t)\leq L(0)\exp(-ct)\) for some positive constant \(c\). We also identify the true asymptotic dynamics of QNN training as regression with a time-varying Gram matrix \(\mathbf{K}_{\text{asym}}\) (Lemma 4.1),
and show rigorously that the real dynamics concentrates to the asymptotic one in the limit \(p\to\infty\) (Theorem 4.2). This reduces the problem of investigating QNN convergence to studying the convergence of the asymptotic dynamics governed by \(\mathbf{K}_{\mathsf{asym}}\).

We also consider a model of QNNs where the final measurement is post-processed by a linear scaling. In this setting, we provide a complete analysis of the convergence of the asymptotic dynamics in the case of 1 training sample (Corollary 4.3), and provide further theoretical evidence of convergence in the neighborhood of most global minima when the number of samples \(m>1\) (Theorem 4.4). These theoretical evidences are supplemented with an empirical study that demonstrates in generality, the convergence of the asymptotic dynamics when \(m\geq 1\). Coupled with our proof of convergence, these form the strongest concrete evidences of the convergence of training for over-parameterized QNNs.

Connections to previous worksOur result extends the existing literature on QNN landscapes (e.g. Anschuetz (2022), Russell et al. (2017)) and looks into the training dynamics, which allows us to characterize the rate of convergence and to show how the range of the measurements affects the convergence to global minima. The dynamics for over-parameterized QNNs proposed by us can be reconciled with the existing calculations of quantum NTK as follows: in the regime of over-parameterization, the QNN dynamics coincides with the quantum NTK dynamics conjectured in Liu et al. (2022) at random initialization; yet it deviates from quantum NTK dynamics during training, and the deviation does not vanish in the limit of \(p\to\infty\).

## 2 Preliminaries

Empirical risk minimization (ERM)A supervised learning problem is specified by a joint distribution \(\mathcal{D}\) over the feature space \(\mathcal{X}\) and the label space \(\mathcal{Y}\), and a family \(\mathcal{F}\) of mappings from \(\mathcal{X}\) to \(\mathcal{Y}\) (i.e. the hypothesis set). The goal is to find an \(f\in\mathcal{F}\) that well predicts the label \(y\) given the feature \(\mathbf{x}\) in expectation, for pairs of \((\mathbf{x},y)\in\mathcal{X}\times\mathcal{Y}\) drawn \(i.i.d.\) from the distribution \(\mathcal{D}\).

Given a training set \(\mathcal{S}=\{\mathbf{x}_{j},y_{j}\}_{j=1}^{m}\) composed of \(m\) pairs of features and labels, we search for the optimal \(f\in\mathcal{F}\) by the _empirical risk minimization_ (ERM): let \(\ell\) be a loss function \(\ell:\mathcal{Y}\times\mathcal{Y}\to\mathbb{R}\), ERM finds an \(f\in\mathcal{F}\) that minimizes the average loss: \(\min_{f\in\mathcal{F}}\frac{1}{m}\sum_{i=1}^{m}\ell(\hat{y}_{i},y_{i}),\; \text{where}\;\hat{y}_{i}=f(\mathbf{x}_{i})\). We focus on the common choice of the _square loss_\(\ell(\hat{y},y)=\frac{1}{2}(\hat{y}-y)^{2}\).

Classical neural networksA popular choice of the hypothesis set \(\mathcal{F}\) in modern-day machine learning is the _classical neural networks_. A vanilla version of the \(L\)-layer feed-forward neural network takes the form \(f(x;\mathbf{W}_{1},\cdots,\mathbf{W}_{L})=\mathbf{W}_{L}\sigma(\cdots\mathbf{ W}_{2}\sigma(\mathbf{W}_{1}\sigma(x))\cdots)\), where \(\sigma(\cdot)\) is a non-linear activation function, and for all \(l\in[L]\), \(\mathbf{W}_{l}\in\mathbb{R}^{d_{l}\times d_{l-1}}\) is the weights in the \(l\)-th layer, with \(d_{L}=1\) and \(d_{0}\) the same as the dimension of the feature space \(\mathcal{X}\). It has been shown that, in the limit \(\min_{l=1}^{L-1}d_{l}\to\infty\), the training of neural networks with square loss is close to kernel learning, and therefore enjoys a linear convergence rate (Jacot et al., 2018; Arora et al., 2019; Allen-Zhu et al., 2019; Oymak and Soltanolkotabi, 2020).
Quantum neural networksQuantum neural networks is a family of parameterized hypothesis set analogous to its classical counterpart. At a high level, it has the layered-structure like a classical neural network. At each layer, a linear transformation acts on the output from the last layer. A quantum neural network is different from its classical counterpart in the following three aspects.

(1) Quantum states as inputsA \(d\)-dimensional quantum state is represented by a _density matrix_\(\mathbf{\rho}\), which is a positive semidefinite \(d\times d\) Hermitian with trace 1. A state is said to be pure if \(\mathbf{\rho}\) is rank-1. Pure states can therefore be equivalently represented by a state vector \(\mathbf{v}\) such that \(\mathbf{\rho}=\mathbf{vv}^{\dagger}\). The inputs to QNNs are quantum states. They can either be drawn as samples from a quantum-physical problem or be the encodings of classical feature vectors.

(2) ParameterizationIn classical neural networks, each layer is composed of a linear transformation and a non-linear activation, and the matrix associated with the linear transformation can be directly optimized at each entry. In QNNs, the entries of each linear transformation can not be directly manipulated. Instead we update parameters in a variational ansatz to update the linear transformations. More concretely, a general \(p\)-parameter ansatz \(\mathbf{U}(\mathbf{\theta})\) in a \(d\)-dimensional Hilbert space can be specified by a set of \(d\times d\) unitaries \(\{\mathbf{U}_{0},\mathbf{U}_{1},\cdots,\mathbf{U}_{p}\}\) and a set of non-zero \(d\times d\) Hermitians \(\{\mathbf{H}^{(1)},\mathbf{H}^{(2)},\cdots,\mathbf{H}^{(p)}\}\) as

\[\mathbf{U}_{p}\exp(-i\theta_{p}\mathbf{H}^{(p)})\mathbf{U}_{p-1} \exp(-i\theta_{p-1}\mathbf{H}^{(p-1)})\cdots\exp(-i\theta_{2}\mathbf{H}^{(2)}) \mathbf{U}_{1}\exp(-i\theta_{1}\mathbf{H}^{(1)})\mathbf{U}_{0}. \tag{1}\]

Without loss of generality, we assume that \(\text{tr}(\mathbf{H}^{(l)})=0\). This is because adding a Hermitian proportional to \(\mathbf{I}\) on the generator \(\mathbf{H}^{(l)}\) does not change the density matrix of the output states. Notice that most \(p\)-parameter ansatze \(\mathbf{U}:\mathbb{R}^{p}\rightarrow\mathbb{C}^{d\times d}\) can be expressed as Equation 1. One exception may be the anastz design with intermediate measurements (e.g. Cong et al. (2019)). In Section 4, we will also consider the periodic anastz:

**Definition 1** (Periodic ansatz).: A \(d\)-dimensional \(p\)-parameter periodic anasatz \(\mathbf{U}(\mathbf{\theta})\) is defined as

\[\mathbf{U}_{p}\exp(-i\theta_{p}\mathbf{H})\cdot\cdots\cdot\mathbf{U}_{1}\exp( -i\theta_{1}\mathbf{H})\mathbf{U}_{0}, \tag{2}\]

where \(\mathbf{U}_{l}\) are sampled \(i.i.d.\) with respect to the Haar measure over the special unitary group \(SU(d)\), and \(\mathbf{H}\) is a non-zero trace-0 Hermitian.

Up to a unitary transformation, the periodic ansatz is equivalent to an ansatz in Line (1) where \(\{\mathbf{H}^{(l)}\}_{l=1}^{p}\) sampled as \(\mathbf{V}_{l}\mathbf{HV}_{l}^{\dagger}\) with \(\mathbf{V}_{l}\) being haar random \(d\times d\) unitary matrices. Similar ansatze have been considered in McClean et al. (2018); Anschuetz (2022); You and Wu (2021); You et al. (2022).

(3) Readout with measurementsContrary to classical neural networks, the readout from a QNN requires performing quantum _measurements_. A measurement is specified by a Hermitian \(\mathbf{M}\). The outcome of measuring a quantum state \(\mathbf{\rho}\) with a measurement \(\mathbf{M}\) is \(\text{tr}(\mathbf{\rho}\mathbf{M})\), which is a linear function of \(\mathbf{\rho}\). A common choice is the Pauli measurement: Pauli
matrices are \(2\times 2\) Hermitians that are also unitary. The Pauli measurements are tensor products of Pauli matrices, featuring eigenvalues of \(\pm 1\).

A common choice is the Pauli measurement: Pauli matrices are \(2\times 2\) Hermitians that are also unitary:

\[\sigma_{X}=\begin{bmatrix}0&1\\ 1&0\end{bmatrix},\sigma_{Y}=\begin{bmatrix}0&-i\\ i&0\end{bmatrix},\sigma_{Z}=\begin{bmatrix}1&0\\ 0&-1\end{bmatrix}.\]

The Pauli measurements are tensor products of Pauli matrices, featuring eigenvalues of \(\pm 1\).

ERM of quantum neural network.We focus on quantum neural networks equipped with the mean-square loss. Solving the ERM for a dataset \(\mathcal{S}:=\{(\boldsymbol{\rho}_{j},y_{j})\}_{j=1}^{m}\subseteq(\mathbb{C}^ {d\times d}\times\mathbb{R})^{m}\) involves optimizing the objective function \(\min_{\boldsymbol{\theta}}L(\boldsymbol{\theta}):=\frac{1}{2m}\sum_{j=1}^{m} \big{(}\hat{y}_{j}(\boldsymbol{\theta})-y_{j}\big{)}^{2}\), where \(\hat{y}_{j}(\boldsymbol{\theta})=\text{tr}(\boldsymbol{\rho}_{j}\mathbf{U}^{ \dagger}(\boldsymbol{\theta})\mathbf{M}_{0}\mathbf{U}(\boldsymbol{\theta}))\) for all \(j\in[m]\) with \(\mathbf{M}_{0}\) being the quantum measurement and \(\mathbf{U}(\boldsymbol{\theta})\) being the variational ansatz. Typically, a QNN is trained by optimizing the ERM objective function by gradient descent: at the \(t\)-th iteration, the parameters are updated as \(\boldsymbol{\theta}(t+1)\leftarrow\boldsymbol{\theta}(t)-\eta\nabla L( \boldsymbol{\theta}(t))\), where \(\eta\) is the learning rate; for sufficiently small \(\eta\), the dynamics of gradient descent reduces to that of the gradient flow: \(d\boldsymbol{\theta}(t)/dt=-\eta\nabla L(\boldsymbol{\theta}(t))\). Here we focus on the gradient flow setting following Arora et al. (2019).

Rate of convergenceIn the optimization literature, the rate of convergence describes how fast an iterative algorithm approaches an (approximate) solution. For a general function \(L\) with variables \(\boldsymbol{\theta}\), let \(\boldsymbol{\theta}(t)\) be the solution maintained at the time step \(t\) and \(\boldsymbol{\theta}^{\star}\) be the optimal solution. The algorithm is said to be converging _exponentially fast_ or at a _linear rate_ if \(L(\boldsymbol{\theta}(t))-L(\boldsymbol{\theta}^{\star})\leq\alpha\exp(-ct)\) for some constants \(c\) and \(\alpha\). In contrast, algorithms with the sub-optimal gap \(L(\boldsymbol{\theta}(t))-L(\boldsymbol{\theta}^{\star})\) decreasing slower than exponential are said to be converging with a _sublinear_ rate (e.g. \(L(\boldsymbol{\theta}(t))-L(\boldsymbol{\theta}^{\star})\) decaying with \(t\) as a polynomial of \(1/t\)). We will mainly consider the setting where \(L(\boldsymbol{\theta}^{\star})=0\) (i.e. the _realizable_ case) with continuous time \(t\).

Other notationsWe use \(\left\lVert\cdot\right\rVert_{\text{op}}\), \(\left\lVert\cdot\right\rVert_{F}\) and \(\left\lVert\cdot\right\rVert_{\text{tr}}\) to denote the operator norm (i.e. the largest eigenvalue in terms of the absolute values), Frobenius norm and the trace norm of matrices; we use \(\left\lVert\cdot\right\rVert_{p}\) to denote the \(p\)-norm of vectors, with the subscript omitted for \(p=2\). We use \(\text{tr}(\cdot)\) to denote the trace operation.

## 3 Deviations of QNN Dynamics from NTK

Consider a regression model on an \(m\)-sample training set: for all \(j\in[m]\), let \(y_{j}\) and \(\hat{y}_{j}\) be the label and the model prediction of the \(j\)-th sample. The _residual_ vector \(\mathbf{r}\) is a \(m\)-dimensional vector with \(r_{j}:=y_{j}-\hat{y}_{j}\). The dynamics of the kernel regression is signatured by the first-order linear dynamics of the residual vectors: let \(\mathbf{w}\) be the learned model parameter, and let \(\phi(\cdot)\) be the fixed non-linear map. Recall that the kernel regression minimizes \(L(\mathbf{w})=\frac{1}{2m}\sum_{j=1}^{m}(\mathbf{w}^{T}\phi(\mathbf{x}_{j})-y _{j})^{2}\) for a training set \(\mathcal{S}=\{(\mathbf{x}_{j},y_{j})\}_{j=1}^{m}\), and the gradient with respect to \(\mathbf{w}\) is \(\frac{1}{m}\sum_{j=1}^{m}(\mathbf{w}^{T}\phi(\mathbf{x}_{j})-y_{j})\phi( \mathbf{x}_{j})=-\frac{1}{m}\sum_{j=1}^{m}r_{j}\phi(\mathbf{x}_{j})\). Under the gradient flow with learning rate \(\eta\), the weight \(\mathbf{w}\) updates as \(\frac{d\mathbf{w}}{dt}=\frac{\eta}{m}\sum_{j=1}^{m}r_{j}\phi(\mathbf{x}_{j})\), and the \(i\)-th entry of the
residual vector updates as \(dr_{i}/dt=-\phi(\mathbf{x}_{i})^{T}\frac{d\mathbf{w}}{dt}=-\frac{\eta}{m}\sum_{j= 1}^{m}\phi(\mathbf{x}_{i})^{T}\phi(\mathbf{x}_{j})r_{j}\), or more succinctly \(d\mathbf{r}/dt=-\frac{\eta}{m}\mathbf{K}\mathbf{r}\) with \(\mathbf{K}\) being the kernel/Gram matrix defined as \(K_{ij}=\phi(\mathbf{x}_{i})^{T}\phi(\mathbf{x}_{j})\) (see also Arora et al. (2019)). Notice that the kernel matrix \(\mathbf{K}\) is a constant of time and is independent of the weight \(\mathbf{w}\) or the labels.

Dynamics of residual vectorsWe start by characterizing the dynamics of the residual vectors for the general form of \(p\)-parameter QNNs and highlight the limitation of viewing the over-parameterized QNNs as kernel regressions. Similar to the kernel regression, \(\frac{dr_{j}}{dt}=-\frac{d\hat{y}_{j}}{dt}=-\operatorname{tr}(\boldsymbol{ \rho}_{j}\frac{d}{dt}\mathbf{U}^{\dagger}(\boldsymbol{\theta}(t))\mathbf{M}_ {0}\mathbf{U}(\boldsymbol{\theta}(t)))\) in QNNs. We derive the following dynamics of \(\mathbf{r}\) by tracking the parameterized measurement \(\mathbf{M}(\boldsymbol{\theta})=\mathbf{U}^{\dagger}(\boldsymbol{\theta}) \mathbf{M}_{0}\mathbf{U}(\boldsymbol{\theta})\) as a function of time \(t\).

**Lemma 3.1** (Dynamics of the residual vector).: _Consider a QNN instance with an ansatz \(\mathbf{U}(\boldsymbol{\theta})\) defined as in Line (1), a training dataset \(\mathcal{S}=\{(\boldsymbol{\rho}_{j},y_{j})\}_{j=1}^{m}\), and a measurement \(\mathbf{M}_{0}\). Under the gradient flow for the objective function \(L(\boldsymbol{\theta})=\frac{1}{2m}\sum_{j=1}^{m}\big{(}\operatorname{tr}( \boldsymbol{\rho}_{j}\mathbf{U}^{\dagger}(\boldsymbol{\theta})\mathbf{M}_{0} \mathbf{U}(\boldsymbol{\theta}))-y_{j}\big{)}^{2}\) with learning rate \(\eta\), the residual vector \(\mathbf{r}\) satisfies the differential equation_

\[\frac{d\mathbf{r}(\boldsymbol{\theta}(t))}{dt}=-\frac{\eta}{m}\mathbf{K}( \mathbf{M}(\boldsymbol{\theta}(t)))\mathbf{r}(\boldsymbol{\theta}(t)), \tag{3}\]

_where \(\mathbf{K}\) is a positive semi-definite matrix-valued function of the parameterized measurement. The \((i,j)\)-th element of \(\mathbf{K}\) is defined as_

\[\sum_{l=1}^{p}\big{(}\operatorname{tr}\big{(}\mathrm{i}[\mathbf{M}( \boldsymbol{\theta}(t)),\boldsymbol{\rho}_{i}]\mathbf{H}_{l}\big{)} \operatorname{tr}\big{(}\mathrm{i}[\mathbf{M}(\boldsymbol{\theta}(t)), \boldsymbol{\rho}_{j}]\mathbf{H}_{l}\big{)}\big{)}. \tag{4}\]

_Here \(\mathbf{H}_{l}:=\mathbf{U}_{0}^{\dagger}\mathbf{U}_{1:l-1}^{\dagger}( \boldsymbol{\theta})\mathbf{H}^{(l)}\mathbf{U}_{1:l-1}(\boldsymbol{\theta}) \mathbf{U}_{0}\), is a function of \(\boldsymbol{\theta}\) with \(\mathbf{U}_{1:r}(\boldsymbol{\theta})\) being the shorthand for \(\mathbf{U}_{r}\exp(-i\theta_{r}\mathbf{H}^{(r)})\cdots\mathbf{U}_{1}\exp(-i \theta_{1}\mathbf{H}^{(1)})\)._

While Equation (3) takes a similar form to that of the kernel regression, the matrix \(\mathbf{K}\) is _dependent_ on the parameterized measurement \(\mathbf{M}(\boldsymbol{\theta})\). This is a consequence of the unitarity: consider an alternative parameterization, where the objective function \(\mathbf{L}(\mathbf{M})=\frac{1}{2m}\sum_{j=1}^{m}\big{(}\operatorname{tr}( \boldsymbol{\rho}_{j}\mathbf{M})-y_{j}\big{)}^{2}\) is optimized over all Hermitian matrices \(\mathbf{M}\). It can be easily verified that the corresponding dynamics is exactly the kernel regression with \(K_{ij}=\operatorname{tr}(\boldsymbol{\rho}_{i}\boldsymbol{\rho}_{j})\).

Due to the unitarity of the evolution of quantum states, the spectrum of eigenvalues of the parameterized measurement \(\mathbf{M}(\boldsymbol{\theta})\) is required to remain the same throughout training. In the proof of Lemma 3.1 (deferred to Section A.1 in the appendix), we see that the derivative of \(\mathbf{M}(\boldsymbol{\theta})\) takes the form of a linear combination of commutators \(i[\mathbf{A},\mathbf{M}(\boldsymbol{\theta})]\) for some Hermitian \(\mathbf{A}\). As a result, the traces of the \(k\)-th matrix powers \(\operatorname{tr}(\mathbf{M}^{k}(\boldsymbol{\theta}))\) are constants of time for any integer \(k\), since \(d\operatorname{tr}(\mathbf{M}^{k}(\boldsymbol{\theta}))/dt=k\operatorname{tr}( \mathbf{M}^{k-1}(\boldsymbol{\theta})d\mathbf{M}(\boldsymbol{\theta})/dt)=k \operatorname{tr}(\mathbf{M}^{k-1}(\boldsymbol{\theta})i[\mathbf{A},\mathbf{M}( \boldsymbol{\theta})])=0\) for any Hermitian \(\mathbf{A}\). The spectrum of eigenvalues remains unchanged because the coefficients of the characteristic polynomials of \(\mathbf{M}(\boldsymbol{\theta})\) is completely determined by the traces of matrix powers. On the contrary, the eigenvalues are in general not preserved for \(\mathbf{M}\) evolving under the kernel regression.

Another consequence of the unitarity constraint is that a QNN can not make predictions outside the range of the eigenvalues of \(\mathbf{M}_{0}\), while for the kernel regression with a strictly positive definite kernel, the model can (over-)fit training sets with arbitrary label assignments. Here we further show that the unitarity is pronounced in a typical QNN instance where the predictions are within the range of the measurement.
Sublinear convergence in QNNsOne of the most common choices for designing QNNs is to use a (tensor product of) Pauli matrices as the measurement (see e.g. Farhi et al. (2020); Dunjko and Briegel (2018)). Such a choice features a measurement \(\mathbf{M}_{0}\) with eigenvalues \(\{\pm 1\}\) and trace zero. Here we show that in the setting of supervised learning on pure states with Pauli measurements, the (neural tangent) kernel regression is insufficient to capture the convergence of QNN training. For the kernel regression with a positive definite kernel \(\mathbf{K}\), the objective function \(L\) can be expressed as \(\frac{1}{2m}\sum_{j=1}^{m}(\hat{y}_{j}-y_{j})^{2}=\frac{1}{2m}\mathbf{r}^{T} \mathbf{r}\); under the kernel dynamics of \(\frac{d\mathbf{r}}{dt}=-\frac{\eta}{m}\mathbf{K}\mathbf{r}\), it is easy to verify that \(\frac{d\ln L}{dt}=-\frac{2\eta}{m}\frac{\mathbf{r}^{T}\mathbf{K}\mathbf{r}}{ \mathbf{r}^{T}\mathbf{r}}\leq-\frac{2\eta}{m}\lambda_{\min}(\mathbf{K})\) with \(\lambda_{\min}(\mathbf{K})\) being the smallest eigenvalue of \(\mathbf{K}\). This indicates that \(L\) decays at a linear rate, i.e. \(L(T)\leq L(0)\exp(-\frac{2\eta}{m}\lambda_{\min}(\mathbf{K})T)\). In contrast, we show that the rate of convergence of the QNN dynamics _must_ be sublinear, slower than the linear convergence rate predicted by the kernel regression model with a positive definite kernel.

**Theorem 3.2** (No faster than sublinear convergence).: _Consider a QNN instance with a training set \(\mathcal{S}=\{(\boldsymbol{\rho}_{j},y_{j})\}\) such that \(\boldsymbol{\rho}_{j}\) are pure states and \(y_{j}\in\{\pm 1\}\), and a measurement \(\mathbf{M}_{0}\) with eigenvalues in \(\{\pm 1\}\). Under the gradient flow for the objective function \(L(\boldsymbol{\theta})=\frac{1}{2m}\sum_{j=1}^{m}\operatorname{tr}(\boldsymbol{ \rho}_{j}\mathbf{M}(\boldsymbol{\theta})-y_{j})^{2}\), for any ansatz \(\mathbf{U}(\boldsymbol{\theta})\) defined in Line (1), \(L\) converges to zero at most at a sublinear convergence rate. More concretely, for \(\mathbf{U}(\boldsymbol{\theta})\) generated by \(\{\mathbf{H}^{(l)}\}_{l=1}^{p}\), let \(\eta\) be the learning rate and \(m\) be the sample size, the objective function at time \(t\):_

\[L(\boldsymbol{\theta}(t))\geq 1/(c_{0}+c_{1}t)^{2}. \tag{5}\]

_Here the constant \(c_{0}=1/\sqrt{L(\boldsymbol{\theta}(0))}\) depends on the objective function at initialization, and \(c_{1}=12\eta\sum_{l=1}^{p}\left\|\mathbf{H}^{(l)}\right\|_{\mathsf{op}}^{2}\)._

The constant \(c_{1}\) in the theorem depends on the number of parameters \(p\) through \(\sum_{l=1}^{p}\left\|\mathbf{H}^{(l)}\right\|_{\mathsf{op}}^{2}\) if the operator norm of \(\mathbf{H}^{(l)}\) is a constant of \(p\). We can get rid of the dependency on \(p\) by scaling the learning rate \(\eta\) or changing the time scale, which does not affect the sublinearity of convergence.

By expressing the objective function \(L(\boldsymbol{\theta}(t))\) as \(\frac{1}{2m}\mathbf{r}(\boldsymbol{\theta}(t))^{T}\mathbf{r}(\boldsymbol{ \theta}(t))\), Lemma 3.1 indicates that the decay of \(\frac{dL(\boldsymbol{\theta}(t))}{dt}\) is lower-bounded by \(\frac{-2\eta}{m}\lambda_{\max}(\mathbf{K}(\boldsymbol{\theta}(t)))L( \boldsymbol{\theta}(t))\), where \(\lambda_{\max}(\cdot)\) is the largest eigenvalue of a Hermitian matrix. The full proof of Theorem 3.2 is deferred to Section A.2, and follows from the fact that when the QNN prediction for an input state \(\boldsymbol{\rho}_{j}\) is close to the ground truth \(y_{j}=1\) or \(-1\), the diagonal entry \(K_{jj}(\boldsymbol{\theta}(t))\) vanishes. As a result the largest eigenvalue \(\lambda_{\max}(\mathbf{K}(\boldsymbol{\theta}(t)))\) also vanishes as the objective function \(L(\boldsymbol{\theta}(t))\) approaches \(0\) (which is the global minima). Notice the sublinearity of convergence is independent of the system dimension \(d\), the choices of \(\{\mathbf{H}^{(l)}\}_{l=1}^{p}\) in \(\mathbf{U}(\boldsymbol{\theta})\) or the number of parameters \(p\). This means that the dynamics of QNN training is completely different from kernel regression even in the limit where \(d\) and/or \(p\to\infty\).

Experiments: sublinear QNN convergenceTo support Theorem 3.2, we simulate the training of QNNs using \(\mathbf{M}_{0}\) with eigenvalues \(\pm 1\). For dimension \(d=32\) and \(64\), we randomly sample four \(d\)-dimensional pure states that are orthogonal, with two of samples labeled \(+1\) and the other two labeled \(-1\). The training curves (plotted under the log scale) in Figure 1
flattens as \(L\) approaches \(0\), suggesting the rate of convergence \(-d\ln L/dt\) vanishes around global minima, which is a signature of the sublinear convergence. Note that the sublinearity of convergence is independent of the number of parameters \(p\). For gradient flow or gradient descent with sufficiently small step-size, the scaling of a constant learning rate \(\eta\) leads to a scaling of time \(t\) and does not fundamentally change the (sub)linearity of the convergence. For the purpose of visual comparison, we scale \(\eta\) with \(p\) by choosing the learning rate as \(10^{-3}/p\). For more details on the experiments, please refer to Section D.

## 4 Asymptotic Dynamics of QNNs

As demonstrated in the previous section, the dynamics of the QNN training deviates from the kernel regression for any choices of the number of parameters \(p\) and the dimension \(d\) in the setting of Pauli measurements for classification. This calls for a new characterization of the QNN dynamics in the regime of over-parameterization. For a concrete definition of over-parameterization, we consider the family of the periodic ansatze in Definition 1, and refer to the limit of \(p\to\infty\) with a fixed generating Hamiltonian \(\mathbf{H}\) as the regime of over-parameterization. In this section, we derive the asymptotic dynamics of QNN training when number of parameters \(p\) in the periodic ansatze goes to infinity. We start by decomposing the dynamics of the residual \(\mathbf{r}(\boldsymbol{\theta}(t))\) into a term corresponding to the asymptotic dynamics, and a term of perturbation that vanishes as \(p\to\infty\). As mentioned before, in the context of the gradient flow, the choice of \(\eta\) is merely a scaling of the time and therefore arbitrary. For a QNN instance with \(m\) training samples and a \(p\)-parameter ansatz generated by a Hermitian \(\mathbf{H}\) as defined in Line (2), we choose \(\eta\) to be \(\frac{m}{p}\frac{d^{2}-1}{\operatorname{tr}(\mathbf{H}^{2})}\) to facilitate the presentation:

**Lemma 4.1** (Decomposition of the residual dynamics).: _Let \(\mathcal{S}\) be a training set with \(m\) samples \(\{(\boldsymbol{\rho}_{j},y_{j})\}_{j=1}^{m}\), and let \(\mathbf{U}(\boldsymbol{\theta})\) be a \(p\)-parameter ansatz generated by a non-zero \(\mathbf{H}\) as in Line 2. Consider a QNN instance with a training set \(\mathcal{S}\), ansatz \(\mathbf{U}(\boldsymbol{\theta})\) and a measurement

Figure 1: Sublinear convergence of QNN training. For QNNs with Pauli measurements for a classification task, the (log-scaled) training curves flatten as the number of iterations increases, indicating a sublinear convergence. The flattening of training curves remains for increasing numbers of parameters \(p=10,20,40,80\). The training curves are averaged over \(10\) random initialization, and the error bars are the halves of standard deviations.
\(\mathbf{M}_{0}\). Under the gradient flow with \(\eta=\frac{m}{p}\frac{d^{2}-1}{\operatorname{tr}(\mathbf{H}^{2})}\), the residual vector \(\mathbf{r}(t)\) as a function of time \(t\) through \(\boldsymbol{\theta}(t)\) evolves as_

\[\frac{d\mathbf{r}(t)}{dt}=-(\mathbf{K}_{\mathsf{asym}}(t)+\mathbf{K }_{\mathsf{pert}}(t))\mathbf{r}(t) \tag{6}\]

_where both \(\mathbf{K}_{\mathsf{asym}}\) and \(\mathbf{K}_{\mathsf{pert}}\) are functions of time through the parameterized measurement \(\mathbf{M}(\boldsymbol{\theta}(t))\), such that_

\[(\mathbf{K}_{\mathsf{asym}}(t))_{ij} :=\operatorname{tr}\big{(}i[\mathbf{M}(t),\boldsymbol{\rho}_{i}] \ i[\mathbf{M}(t),\boldsymbol{\rho}_{j}]\big{)}, \tag{7}\] \[(\mathbf{K}_{\mathsf{pert}}(t))_{ij} :=\operatorname{tr}\big{(}i[\mathbf{M}(t),\boldsymbol{\rho}_{i}] \otimes i[\mathbf{M}(t),\boldsymbol{\rho}_{j}]\Delta(t)\big{)}. \tag{8}\]

_Here \(\Delta(t)\) is a \(d^{2}\times d^{2}\) Hermitian as a function of \(t\) through \(\boldsymbol{\theta}(t)\)._

Under the random initialization by sampling \(\{\mathbf{U}_{l}\}_{l=1}^{p}\) i.i.d. from the haar measure over the special unitary group \(SU(d)\), \(\Delta(0)\) concentrates at zero as \(p\) increases. We further show that \(\Delta(t)-\Delta(0)\) has a bounded operator norm decreasing with number of parameters. This allows us to associate the convergence of the over-parameterized QNN with the properties of \(\mathbf{K}_{\mathsf{asym}}(t)\):

**Theorem 4.2** (Linear convergence of QNN with mean-square loss).: _Let \(\mathcal{S}\) be a training set with \(m\) samples \(\{(\boldsymbol{\rho}_{j},y_{j})\}_{j=1}^{m}\), and let \(\mathbf{U}(\boldsymbol{\theta})\) be a \(p\)-parameter ansatz generated by a non-zero \(\mathbf{H}\) as in Line (2). Consider a QNN instance with the training set \(\mathcal{S}\), ansatz \(\mathbf{U}(\boldsymbol{\theta})\) and a measurement \(\mathbf{M}_{0}\), trained by gradient flow with \(\eta=\frac{m}{p}\frac{d^{2}-1}{\operatorname{tr}(\mathbf{H}^{2})}\). Then for sufficiently large number of parameters \(p\), if the smallest eigenvalue of \(\mathbf{K}_{\mathsf{asym}}(t)\) is greater than a constant \(C_{0}\), then with high probability over the random initialization of the periodic ansatz, the loss function converges to zero at a linear rate_

\[L(t)\leq L(0)\exp(-\frac{C_{0}t}{2}). \tag{9}\]

We defer the proof to Section B.2. Similar to \(\mathbf{r}(t)\), the evolution of \(\mathbf{M}(t)\) decomposes into an asymptotic term

\[\frac{d}{dt}\mathbf{M}(t)=\sum_{j=1}^{m}r_{j}[\mathbf{M}(t),[ \mathbf{M}(t),\boldsymbol{\rho}_{j}]] \tag{10}\]

and a perturbative term depending on \(\Delta(t)\). Theorem 4.2 allows us to study the behavior of an over-parameterized QNN by simulating/characterizing the asymptotic dynamics of \(\mathbf{M}(t)\), which is significantly more accessible.

Application: QNN with one training sampleTo demonstrate the proposed asymptotic dynamics as a tool for analyzing over-parameterized QNNs, we study the convergence of the QNN with one training sample \(m=1\). To set a separation from the regime of the sublinear convergence, consider the following setting: let \(\mathbf{M}_{0}\) be a Pauli measurement, for any input state \(\boldsymbol{\rho}\), instead of assigning \(\hat{y}=\operatorname{tr}(\boldsymbol{\rho}\mathbf{U}(\boldsymbol{\theta})^{ \dagger}\mathbf{M}_{0}\mathbf{U}(\boldsymbol{\theta}))\), take \(\gamma\operatorname{tr}(\boldsymbol{\rho}\mathbf{U}(\boldsymbol{\theta})^{ \dagger}\mathbf{M}_{0}\mathbf{U}(\boldsymbol{\theta}))\) as the prediction \(\hat{y}\) at \(\boldsymbol{\theta}\) for a scaling factor \(\gamma>1.0\). The \(\gamma\)-scaling of the measurement outcome can
be viewed as a classical processing in the context of quantum information, or as an activation function (or a link function) in the context of machine learning, and is equivalent to a QNN with measurement \(\gamma\mathbf{M}_{0}\). The following corollary implies the convergence of 1-sample QNN for \(\gamma>1.0\) under a mild initial condition:

**Corollary 4.3**.: _Let \(\boldsymbol{\rho}\) be a \(d\)-dimensional pure state, and let \(y\) be \(\pm 1\). Consider a QNN instance with a Pauli measurement \(\mathbf{M}_{0}\), an one-sample training set \(\mathcal{S}=\{(\boldsymbol{\rho},y)\}\) and an ansatz \(\mathbf{U}(\boldsymbol{\theta})\) defined in Line (2). Assume the scaling factor \(\gamma>1.0\) and \(p\to\infty\) with \(\eta=\frac{d^{2}-1}{p\,\mathrm{tr}(\mathbf{H}^{2})}\). Under the initial condition that the prediction at \(t=0\), \(\hat{y}(0)\) is less than 1, the objective function converges linearly with_

\[L(t)\leq L(0)\exp(-C_{1}t) \tag{11}\]

_with the convergence rate \(C_{1}\geq\gamma^{2}-1\)._

With a scaling factor \(\gamma\) and training set \(\{(\boldsymbol{\rho}_{j},y_{j})\}_{j=1}^{m}\), the objective function, as a function of the parameterized measurement \(\mathbf{M}(t)\), reads as: \(L(\mathbf{M}(t))=\frac{1}{2m}\sum_{j=1}^{m}(\gamma\,\mathrm{tr}(\boldsymbol{ \rho}_{j}\mathbf{M}(t))-y_{j})^{2}\). As stated in Theorem 4.2, for sufficiently large number of parameters \(p\), the convergence rate of the residual \(\mathbf{r}(t)\) is determined by \(\mathbf{K}_{\mathsf{asym}}(t)\), as the asymptotic dynamics of \(\mathbf{r}(t)\) reads as \(\frac{d}{dt}\mathbf{r}=-\mathbf{K}_{\mathsf{asym}}(\mathbf{M}(t))\mathbf{r}(t)\) with the chosen \(\eta\). For \(m=1\), the asymptotic matrix \(\mathbf{K}_{\mathsf{asym}}\) reduces to a scalar \(k(t)=-\,\mathrm{tr}([\gamma\mathbf{M}(t),\boldsymbol{\rho}]^{2})=2(\gamma^{2}- \hat{y}(t)^{2})\). \(\hat{y}(t)\) approaches the label \(y\) if \(k(t)\) is strictly positive, which is guaranteed for \(\hat{y}(t)<\gamma\). Therefore \(|\hat{y}(0)|<1\) implies that \(|\hat{y}(t)|<1\) and \(k(t)\geq 2(\gamma^{2}-1)\) for all \(t>0\).

In Figure 2 (top), we plot the training curves of one-sample QNNs with \(p=320\) and varying \(\gamma=1.2,1.4,2.0,4.0,8.0\) with the same learning rate \(\eta=1e-3/p\). As predicted in Corollary 4.3, the rate of convergence increases with the scaling factor \(\gamma\). The proof of the corollary additionally implies that \(k(t)\) depends on \(\hat{y}(t)\): the convergence rate changes over time as the prediction \(\hat{y}\) changes. Therefore, despite the linear convergence, the dynamics is different from that of kernel regression, where the kernel remains constant during training in the limit \(p\to\infty\).

In Figure 2 (bottom), we plot the empirical rate of convergence \(-\frac{d}{dt}\ln L(t)\) against the rate predicted by \(\hat{y}\). Each data point is calculated for QNNs with different \(\gamma\) at different time steps by differentiating the logarithms of the training curves. The scatter plot displays an approximately linear dependency, indicating the proposed asymptotic dynamics is capable of predicting how the convergence rate changes during training, which is beyond the explanatory power of the kernel regression model. Note that the slope of the linear relation is not exactly one. This is because we choose a learning rate much smaller than \(\eta\) in the corollary statement to simulate the dynamics of gradient flow.

QNNs with one training sample have been considered before (e.g. Liu et al. (2022)), where the linear convergence has been shown under the assumption of "frozen QNTK", namely assuming \(\mathbf{K}\), the time derivative of the log residual remains almost constant throughout training. In the corollary above, we provide an end-to-end proof for the one-sample linear convergence without assuming a frozen \(\mathbf{K}\). In fact, we observe that in our setting \(\mathbf{K}=2(\gamma^{2}-\hat{y}(t))\) changes with \(\hat{y}(t)\) (see also Figure 2) and is therefore not frozen.
Figure 2: (Top) The training curves of one-sample QNNs with varying \(\gamma\). The smallest convergence rate \(-d\ln L/dt\) during training (i.e. the slope of the training curves under the log scale) increases with \(\gamma\). (Bottom) The convergence rate \(-d\ln L/dt|_{t=T}\) as a function of \(2(\gamma^{2}-\hat{y}^{2}(T))\) (jointly scaled by \(1/\gamma^{2}\) for visualization) are evaluated at different time steps \(T\) for different \(\gamma\). The approximately linear dependency shows that the proposed dynamics captures the QNN convergence beyond the explanatory power of the kernel regressions.
QNN convergence for \(m>1\)To characterize the convergence of QNNs with \(m>1\), we seek to empirically study the asymptotic dynamics in Line (10). According to Theorem 4.2, the (linear) rate of convergence is lower-bounded by the smallest eigenvalue of \(\mathbf{K}_{\mathsf{asym}}(t)\), up to an constant scaling. In Figure 3, we simulate the asymptotic dynamics with various combinations of \((\gamma,d,m)\), and evaluate the smallest eigenvalue of \(\mathbf{K}_{\mathsf{asym}}(t)\) throughout the dynamics (Figure 3, details deferred to Section D). For sufficiently large dimension \(d\), the smallest eigenvalue of \(\mathbf{K}_{\mathsf{asym}}\) depends on the ratio between the number of samples and the system dimension \(m/d\) and is proportional to the square of the scaling factor \(\gamma^{2}\).

Empirically, we observe that the smallest convergence rates for training QNNs are obtained near the global minima (See Figure 6 in the appendix), suggesting the bottleneck of convergence occurs when \(L\) is small.

We now give theoretical evidence that, at most of the global minima, the eigenvalues of \(\mathbf{K}_{\mathsf{asym}}\) are lower bounded by \(2\gamma^{2}(1-1/\gamma^{2}-O(m^{2}/d))\), suggesting a linear convergence in the neighborhood of these minima. To make this notion precise, we define the uniform measure over global minima as follows: consider a set of pure input states \(\{\mathbf{\rho}_{j}=\mathbf{v}_{j}\mathbf{v}_{j}^{\dagger}\}_{j=1}^{m}\) that are mutually orthogonal (i.e. \(\mathbf{v}_{i}^{\dagger}\mathbf{v}_{j}=0\) if \(i\neq j\)). For a large dimension \(d\), the global

Figure 3: The smallest eigenvalue of \(\mathbf{K}_{\mathsf{asym}}\) for the asymptotic dynamics with varying system dimension \(d\), scaling factor \(\gamma\) and number of training samples \(m\). For sufficiently large \(d\), the smallest eigenvalue depends on the ratio \(m/d\) and is proportional to the square of the scaling factor \(\gamma^{2}\).
minima of the asymptotic dynamics is achieved when the objective function is \(0\). Let \(\mathbf{u}_{j}(t)\) (resp. \(\mathbf{w}_{j}(t)\)) denote the components of \(\mathbf{v}_{j}\) projected to the positive (resp. negative) subspace of the measurement \(\mathbf{M}(t)\) at the global minima. Recall that for a \(\gamma\)-scaled QNN with a Pauli measurement, the predictions \(\hat{y}(t)=\gamma\operatorname{tr}(\rho_{j}\mathbf{M}(t))=\gamma(\mathbf{u}_{ j}^{\dagger}(t)\mathbf{u}_{j}(t)-\mathbf{w}_{j}^{\dagger}(t)\mathbf{w}_{j}(t))\). At the global minima, we have \(\mathbf{u}_{j}(t)=\frac{1}{2}(1\pm 1/\gamma)\hat{\mathbf{u}}_{j}(t)\) for some unit vector \(\hat{\mathbf{u}}_{j}(t)\) for the \(j\)-th training sample with label \(\pm 1\). On the other hand, given a set of unit vectors \(\{\hat{\mathbf{u}}_{j}\}_{j=1}^{m}\) in the positive subspace, there is a corresponding set of \(\{\mathbf{u}_{j}(t)\}_{j=1}^{m}\) and \(\{\mathbf{w}_{j}(t)\}_{j=1}^{m}\) such that \(L=0\) for sufficiently large \(d\). By uniformly and independently sampling a set of unit vectors \(\{\hat{\mathbf{u}}_{j}\}_{j=1}^{m}\) from the \(d/2\)-dimensional subspace associated with the positive eigenvalues of \(\mathbf{M}(t)\), we induce a uniform distribution over all the global minima. The next theorem characterizes \(\mathbf{K}_{\mathsf{asym}}\) under such an induced uniform distribution over all the global minima:

**Theorem 4.4**.: _Let \(\mathcal{S}=\{(\boldsymbol{\rho}_{j},y_{j})\}_{j=1}^{m}\) be a training set with orthogonal pure states \(\{\boldsymbol{\rho}_{j}\}_{j=1}^{m}\) and equal number of positive and negative labels \(y_{j}\in\{\pm 1\}\). Consider the smallest eigenvalue \(\lambda_{g}\) of \(\mathbf{K}_{\mathsf{asym}}\) at the global minima of the asymptotic dynamics of an over-parameterized QNN with the training set \(\mathcal{S}\), scaling factor \(\gamma\) and system dimension \(d\). With probability \(\geq 1-\delta\) over the uniform measure over all the global minima_

\[\lambda_{g}\geq 2\gamma^{2}(1-\frac{1}{\gamma^{2}}-C_{2}\max\{\frac{m^{2}}{d}, \frac{m}{d}\log\frac{2}{\delta}\}), \tag{12}\]

_which is strictly positive for large \(\gamma>1\) and \(d=\Omega(\mathsf{poly}(m))\). Here \(C_{2}\) is a positive constant._

We defer the proof of Theorem 4.4 to Section C in the appendix. A similar notion of a uniform measure over global minima was also used in Canatar et al. (2021). Notice that the uniformness is dependent on the parameterization of the global minima, and the uniform measure over all the global minima is not necessarily the measure induced by random initialization and gradient-based training. Therefore Theorem 4.4 is not a rigorous depiction of the distribution of convergence rate for a randomly-initialized over-parameterized QNN. Yet the prediction of the theorem aligns well with the empirical observations in Figure 3 and suggests that by scaling the QNN measurements, a faster convergence can be achieved: In Figure 4, we simulate \(p\)-parameter QNNs with dimension \(d=32\) and \(64\) with a scaling factor \(\gamma=4.0\) using the same setup as in Figure 1. The training early stops when the average \(L(t)\) over the random seeds is less than \(1\times 10^{-2}\). In contrast to Figure 1, the convergence rate \(-d\ln L/dt\) does not vanish as \(L\to 0\), suggesting a simple (constant) scaling of the measurement outcome can lead to convergence within much fewer number of iterations.

Another implication of Theorem 4.4 is the deviation of QNN dynamics from any kernel regressions. By straight-forward calculation, the normalized matrix \(\mathbf{K}_{\mathsf{asym}}(0)/\gamma^{2}\) at the random initialization is independent of the choices of \(\gamma\). In contrast, the typical value of \(\lambda_{g}/\gamma^{2}\) in Theorem 4.4 is dependent on \(\gamma^{2}\), suggesting non-negligible changes in the matrix \(\mathbf{K}_{\mathsf{asym}}(t)\) governing the dynamics of \(\mathbf{r}\) for finite scaling factors \(\gamma\). Such phenomenon is empirically verified in Figure 5 in the appendix.

## 5 Limitations and Outlook

In the setting of \(m>1\), the proof of the linear convergence of QNN training (Section 4) relies on the convergence of the asymptotic QNN dynamics as a premise. Given our empirical
results, an interesting future direction might be to rigorously characterize the condition for the convergence of the asymptotic dynamics. Also we mainly consider (variants of) two-outcome measurements \(\mathbf{M}_{0}\) with two eigensubspaces. It might be interesting to look into measurements with more complicated spectrums and see how the shapes of the spectrums affect the rates of convergence.

A QNN for learning a classical dataset is composed of three parts: a classical-to-quantum encoder, a quantum classifier and a readout measurement. Here we have mainly focused on the stage after encoding, i.e. training a QNN classifier to manipulate the density matrices containing classical information that are potentially too costly for a classically-implemented linear model. Our analysis highlights the necessity for measurement design, assuming the design of the quantum classifier mixes to the full \(d\times d\) special unitary group. Our result can be combined with existing techniques of classifier designs (i.e. ansatz design) (Ragone et al. (2022); Larocca et al. (2021); Wang et al. (2022); You et al. (2022)) by engineering the invariant subspaces, or be combined with encoder designs explored in (Huang et al., 2021; Du et al., 2022).

## Acknowledgements

We thank E. Anschuetz, B. T. Kiani, J. Liu and anonymous reviewers for useful comments. This work received support from the U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Accelerated Research in Quantum Computing and Quantum Algorithms Team programs, as well as the U.S. National Science Foundation grant CCF-1816695, and CCF-1942837 (CAREER).

Figure 4: Training curves of QNNs with \(\gamma=4.0\) for learning a 4-sample dataset with labels \(\pm 1\). For \(p=10,20,40,80\), the rate of convergence is greater than 0 as \(L\to 0\), and it takes less than 1000 iterations for \(L\) in most of the instances to convergence below \(1\times 10^{-2}\). In contrast, in Figure 1, \(L>1\times 10^{-1}\) after 10000 iterations despite the increasing number of parameters.
## Disclaimer

This paper was prepared with synthetic data and for informational purposes by the teams of researchers from the various institutions identified above, including the Global Technology Applied Research Center of JPMorgan Chase & Co. This paper is not a product of the JPMorgan Chase Institute. Neither JPMorgan Chase & Co. nor any of its affiliates make any explicit or implied representation or warranty and none of them accept any liability in connection with this paper, including, but limited to, the completeness, accuracy, reliability of information contained herein and the potential legal, compliance, tax or accounting effects thereof. This document is not intended as investment research or investment advice, or a recommendation, offer or solicitation for the purchase or sale of any security, financial instrument, financial product or service, or to be used in any way for evaluating the merits of participating in any transaction.
