Quantum Ridgelet Transform: Winning Lottery Ticket of Neural Networks
  with Quantum Computation
A significant challenge in the field of quantum machine learning (QML) is to
establish applications of quantum computation to accelerate common tasks in
machine learning such as those for neural networks. Ridgelet transform has been
a fundamental mathematical tool in the theoretical studies of neural networks,
but the practical applicability of ridgelet transform to conducting learning
tasks was limited since its numerical implementation by conventional classical
computation requires an exponential runtime $\exp(O(D))$ as data dimension $D$
increases. To address this problem, we develop a quantum ridgelet transform
(QRT), which implements the ridgelet transform of a quantum state within a
linear runtime $O(D)$ of quantum computation. As an application, we also show
that one can use QRT as a fundamental subroutine for QML to efficiently find a
sparse trainable subnetwork of large shallow wide neural networks without
conducting large-scale optimization of the original network. This application
discovers an efficient way in this regime to demonstrate the lottery ticket
hypothesis on finding such a sparse trainable neural network. These results
open an avenue of QML for accelerating learning tasks with commonly used
classical neural networks.
Hayata Yamasaki, Sathyawageeswar Subramanian, Satoshi Hayakawa, Sho Sonoda
# Quantum Ridgelet Transform:

###### Abstract

Ridgelet transform has been a fundamental mathematical tool in the theoretical studies of neural networks. However, the practical applicability of ridgelet transform to conducting learning tasks was limited since its numerical implementation by conventional classical computation requires an exponential runtime \(\exp(O(D))\) as data dimension \(D\) increases. To address this problem, we develop a quantum ridgelet transform (QRT), which implements the ridgelet transform of a quantum state within a linear runtime \(O(D)\) of quantum computation. As an application, we also show that one can use QRT as a fundamental subroutine for quantum machine learning (QML) to efficiently find a sparse trainable subnetwork of large shallow wide neural networks without conducting large-scale optimization of the original network. This application discovers an efficient way in this regime to demonstrate the lottery ticket hypothesis on finding such a sparse trainable neural network. These results open an avenue of QML for accelerating learning tasks with commonly used classical neural networks.

Machine Learning, ICML

## 1 Introduction

Quantum machine learning (QML) is an emerging field of research to take advantage of quantum computation for accelerating machine-learning tasks (Biamonte et al., 2017; Ciliberto et al., 2018; Schuld and Petruccione, 2021). Quantum computation can achieve significant speedups compared to the best existing algorithms with conventional classical computation in solving various computational tasks (Nielsen and Chuang, 2011; de Wolf, 2019), such as Shor's algorithm for integer factorization (Shor, 1997). QML indeed has advantages in learning data obtained from quantum states (Sweke et al., 2021; Huang et al., 2021, 2022; Chen et al., 2022), yet machine learning commonly deals with classical data rather than quantum states. For a classical dataset constructed carefully so that its classification reduces to a variant of Shor's algorithm, QML achieves the classification superpolynomially faster than classical algorithms (Liu et al., 2021); however, the applicability of such QML to practical datasets has been unknown. Meanwhile, motivated by the success of neural networks (Goodfellow et al., 2016), various attempts have been made to apply quantum computation to more practical tasks for neural networks. For example, one widely studied approach in QML is to use parameterized quantum circuits, often called "quantum neural networks", as a potential substitute for conventional classical neural networks; however, problematically, the parameterized quantum circuits do not successfully emulate essential components of the neural networks, e.g., perceptrons and nonlinear activation functions, due to linearlity of the transformation implemented by the quantum circuits (Schuld and Petruccione, 2021). Thus, a significant challenge in QML has been to develop a novel technique to bridge the gap between quantum computation and classical neural networks, so as to clarify what advantage QML could offer on top of the empirically proven merit of the classical neural networks.

To address this challenge, we here develop a fundamental quantum algorithm for making the tasks for classical neural networks more efficient, based on ridgelet transform. Ridgelet transform, one of the well-studied integral transforms in signal processing, is a fundamental mathematical tool for studying neural networks in the over-parameterized regime (Murata, 1996; Candes, 1998; Rubin, 1998; Starck et al., 2010; Sonoda et al., 2021, 2022;b). Let \(f:\mathbb{R}^{D}\rightarrow\mathbb{R}\) denote a function with \(D\)-dimensional input, to be learned with a neural network. For an activation function \(g:\mathbb{R}\rightarrow\mathbb{R}\) such as the rectified linear unit (ReLU), a shallow feed-forward neural network with a single hidden layer is represented by \(f(\mathbf{x})\approx\sum_{n=1}^{N}w_{n}g(\mathbf{a}_{n}^{\top}\mathbf{x}-b_{n})\), where \(N\) is the number of nodes in the hidden layer, and \(w_{n}\) is the weight of the map \(g(\mathbf{a}_{n}^{\top}\mathbf{x}-b_{n})\) parameterized by \((\mathbf{a}_{n},b_{n})\) at node \(n\in\{1,\dots,N\}\)(Goodfellow et al., 2016). In the over-parameterized (continuous) limit \(N\rightarrow\infty\), the representation simplifies into an **integral representation** of the neural network (Barron, 1993; Murata, 1996; Candes, 1998;
Sonoda Murata (2017), i.e.,

\[f(\mathbf{x})=S[w](\mathbf{x})\coloneqq\int_{\mathbb{R}^{D}\times\mathbb{R}}\!\!d\mathbf{a} \,db\,w(\mathbf{a},b)g(\mathbf{a}^{\top}\mathbf{x}-b), \tag{1}\]

where \((\mathbf{a},b)\) runs over all possible parameters in the continuous space, and \(w:\mathbb{R}^{D}\times\mathbb{R}\to\mathbb{R}\) at each \((\mathbf{a},b)\) corresponds to the weight \(w_{n}\) at the node \(n\) with parameter \((\mathbf{a}_{n},b_{n})=(\mathbf{a},b)\). With a ridgelet function \(r:\mathbb{R}^{D}\to\mathbb{R}\) that we appropriately choose corresponding to \(g\), the \(D\)-dimensional **ridgelet transform**\(R[f]\) is defined as an inverse transform of \(S[w]\) in (1), characterizing a weight \(w\) to represent \(f\), given by

\[w(\mathbf{a},b)=R[f](\mathbf{a},b)\coloneqq\int_{\mathbb{R}^{D}}d\mathbf{x}\,f(\mathbf{x})r( \mathbf{a}^{\top}\mathbf{x}-b). \tag{2}\]

A wide class of function \(f\) is known to be representable as (1); moreover, if \(g\) and \(r\) satisfy a certain admissibility condition, we can reconstruct \(f\) from the ridgelet transform of \(f\), i.e., \(f\propto S[R[f]]\), up to a normalization factor Sonoda Murata (2017). For theoretical analysis, an essential benefit of the integral representation is to simplify the analysis by the linearity; that is, we can regard (1) as the linear combination of an non-orthogonal over-complete basis of functions, i.e., \(\{g(\mathbf{a}^{\top}\mathbf{x}-b):(\mathbf{a},b)\in\mathbb{R}^{D}\times\mathbb{R}\}\), with weight \(w(\mathbf{a},b)\) given by the ridgelet transform of \(f\).

Progressing beyond using the ridgelet transform for theoretical analysis, our key idea is to study its use for conducting tasks for neural networks. However, \(D\)-dimensional ridgelet transform has been computationally hard to use in practice since the existing algorithms for ridgelet transform with conventional classical computation require \(\exp(O(D))\) runtime as \(D\) increases Doetteretterli (2003); Carre Andres (2004); Helbert et al. (2006); Sonoda Murata (2014). After all, the \(D\)-dimensional ridgelet transform is a transform of \(D\)-dimensional functions in an \(\exp(O(D))\)-size space (see Sec. 2 for detail), and classical algorithms for such transforms conventionally need \(\exp(O(D))\) runtime; e.g., fast Fourier transform may be a more established transform algorithm but still needs \(O(n\log(n))=\exp(O(D))\) runtime for the space of size \(n=\exp(O(D))\). To solve these problems, we discover that we can employ quantum computation. Our results are as follows.

1. (Sec. 2) To make exact implementation of ridgelet transform possible for computer with a finite number of bits and quantum bits (qubits), we formulate a new discretized version of ridgelet transform, which we call **discrete ridgelet transform**. We prove that our discretized ridgelet transform can be used for exactly representing any function on the discretized domain.
2. (Sec. 3) We develop a quantum algorithm to apply the \(D\)-dimensional discrete ridgelet transform to a quantum state of \(O(D)\) qubits, i.e., a state in an \(\exp(O(D))\)-dimensional space, only within linear runtime \(O(D)\). We call this quantum algorithm **quantum ridgelet transform (QRT)**. QRT is exponentially faster in \(D\) than the \(\exp(O(D))\) runtime of the best existing classical algorithm for ridgelet transform in the \(\exp(O(D))\)-size space, in the same spirit as **quantum Fourier transform (QFT)**Coppersmith (1994) being exponentially faster than the corresponding classical algorithm of fast Fourier transform.
3. (Sec. 4) As an application, we demonstrate that we can use QRT to learn a sparse representation of an unknown function \(f\) by sampling a subnetwork of a shallow wide neural network to approximate \(f\) well. We analytically show the advantageous cases of our algorithm and also conduct a numerical simulation to support the advantage. This application is important as a demonstration of the **lottery ticket hypothesis**Frankle Carbin (2019), as explained in the following.

Contribution to QML with neural networksState-of-the-art neural networks have billions of parameters to attain high learning accuracy, but such large-scale networks may be problematic for practical use, e.g., with mobile devices and embedded systems. Pruning techniques for neural networks gain growing importance in learning with neural networks. The lottery ticket hypothesis by Frankle Carbin (2019) claims that, in such a large-scale neural network, one can find a sparse trainable subnetwork. However, it is computationally demanding to search for the appropriate subnetwork in the large-scale neural network.

To apply QML to this pruning problem, our idea is to use QRT for preparing a quantum state so that, by measuring the state, we can sample the parameters of the important nodes for the subnetwork with high probability. To make this algorithm efficient, we never store all parameters of the large original neural network in classical memory but represent them by the amplitude of the quantum state prepared directly from given data. Conventionally, quantum computation can use QFT to achieve superpolynomial speedups over classical computation for various search problems Simon (1994); Shor (1997); Bernstein Vazirani (1997); Yamakawa Zhandry (2022). By contrast, we make quantum computation applicable to searching in the parameter space of neural networks, by developing QRT to be used in place of QFT.

Consequently, our results show that QRT can be used as a fundamental subroutine for QML to accelerate the tasks for the classical neural networks. A potential drawback may be that our current technique is designed simply for the shallow neural networks with a single hidden layer; however, studies of shallow neural networks capture various essential features of neural networks. We leave the generalization to deep neural networks for future research, but our development opens a promising route in this direction.
## 2 Discrete ridgelet transform

### Formulation of discrete ridgelet transform

In this section, we formulate the **discrete ridgelet transform**. Then, we also derive a **Fourier slice theorem** that characterizes our discrete ridgelet transform using Fourier transform. Although multiple definitions of discrete versions of ridgelet transform have been proposed, none of them has such Fourier expression (Do & Vetterli, 2003; Carre & Andres, 2004; Helbert et al., 2006). By contrast, the significance of the Fourier slice theorem is that it makes the ridgelet analysis tractable with the well-established techniques for the Fourier transform, which we will use in Sec. 3 for constructing the quantum algorithm as well.

Our formulation assumes the following.

* Since computers using a finite number of bits and qubits cannot exactly deal with real number, we use a finite set \(\mathbb{Z}_{P}\coloneqq\{0,1,\ldots,P-1\}\) in place of the set of real number \(\mathbb{R}\), where \(P\) is a precision parameter representing the cardinality of \(\mathbb{Z}_{P}\). This is conventional in data representation; e.g., for a gray scale image, we may use \(8\) bits \(\{0,1,\ldots,2^{8}-1\}\) to represent the intensity of each pixel. In our setting, we can make \(P\) larger to achieve better precision in the data representation; e.g., for a more precise representation of the gray scale image, we may use \(16\) bits \(\{0,1,\ldots,2^{16}-1\}\) in place of the \(8\) bits for each pixel. For this improvement of the precision, we may normalize the data by rescaling while the intervals in the discretization are fixed to \(1\) for simplicity of presentation. When we write a sum, \(\mathbf{x}\), \(\mathbf{a}\), and \(\mathbf{u}\) run over \(\mathbb{Z}_{P}^{D}\), and \(y\), \(b\), and \(v\) over \(\mathbb{Z}_{P}\) unless specified otherwise. Let \(\mathcal{F}_{D}\) and \(\mathcal{F}_{1}\) denote the \(D\)-dimensional and \(1\)-dimensional discrete Fourier transforms on \(\mathbb{Z}_{P}^{D}\) and \(\mathbb{Z}_{P}\), respectively, i.e., \[\mathcal{F}_{D}[f](\mathbf{u}) \coloneqq P^{-\frac{D}{2}}\sum_{\mathbf{x}}f(\mathbf{x})\mathrm{e}^{\frac{ -2\pi\mathrm{i}\mathbf{u}^{\top}\mathbf{x}}{P}},\] (3) \[\mathcal{F}_{1}[g](v) \coloneqq P^{-\frac{1}{2}}\sum_{b}r(b)\mathrm{e}^{\frac{-2\pi \mathrm{i}\mathbf{v}}{P}}.\] (4)
* We assume in the following that \(P\) is taken as a prime number, considering \(\mathbb{Z}_{P}\) as a finite field. This is not a restrictive assumption in achieving the better precision since we can take an arbitrarily large prime number as \(P\). For example, the maximum of \(32\)-bit signed integers \(P=2^{31}-1\) can be used.
* An activation function \(g:\mathbb{R}\to\mathbb{R}\) is assumed to be normalized as \[\sum_{b}g(b)=0,\quad\|g\|_{2}^{2}\coloneqq\sum_{b}|g(b)|^{2}=1.\] (5) Indeed, any non-constant function, such as ReLU, can be used as \(g\) with normalization by adding and multiplying appropriate constants.
* Corresponding to \(g\), we choose a ridgelet function \(r:\mathbb{R}\to\mathbb{R}\) in such a way that \(g\) and \(r\) satisfy an admissibility condition \[C_{g,r}\coloneqq\sum_{v}\mathcal{F}_{1}[g](v)\overline{\mathcal{F}_{1}[r](v)} \neq 0,\] (6) where \(\overline{\cdots}\) denotes the complex conjugate. We also normalize \(r\) as \(\|r\|_{2}^{2}=1\). Note that it is conventional to choose \(r=g\), leading to \(C_{g,g}=\|\mathcal{F}_{1}[g]\|_{2}^{2}=\|g\|_{2}^{2}=1\), while our setting allows any non-unique choice of \(r\) satisfying (6) in general.

Then, by replacing the integral over \(\mathbb{R}\) in \(S\) of (1) and \(R\) of (2) with the finite sum over \(\mathbb{Z}_{P}\), we correspondingly define the **discretized neural network** and the **discrete ridgelet transform** of \(f:\mathbb{R}^{D}\to\mathbb{R}\) as, respectively,

\[\mathcal{S}[w](\mathbf{x})\coloneqq P^{-\frac{D}{2}}\sum_{\mathbf{a},b}w( \mathbf{a},b)g((\mathbf{a}^{\top}\mathbf{x}-b)\bmod P), \tag{7}\] \[\mathcal{R}[f](\mathbf{a},b)\coloneqq P^{-\frac{D}{2}}\sum_{\mathbf{x}}f( \mathbf{x})r((\mathbf{a}^{\top}\mathbf{x}-b)\bmod P), \tag{8}\]

where \(P^{-\frac{D}{2}}\) represents a normalization constant. Note that the discretized neural network \(\mathcal{S}[w](\mathbf{x})\) has discrete parameters \((\mathbf{a},b)\in\mathbb{Z}_{P}^{D}\times\mathbb{Z}_{P}\) for nodes in the hidden layer, but the weights \(w(\mathbf{a},b)\in\mathbb{R}\) of the nodes are real numbers.

The following theorem, **Fourier slice theorem**, characterizes the discrete ridgelet transform \(R[f]\) in terms of Fourier transforms of \(f\) and \(h\). In the case of continuous ridgelet transform, ridgelet analysis can be seen as a form of wavelet analysis in the Radon domain, which combines wavelet and Radon transforms (Fadili & Starck, 2012). The Fourier slice theorem for the continuous ridgelet transform follows from that for continuous Radon transform. However, problematically, discrete versions of the Radon transforms are nonunique and usually more involved, not necessarily having exact expression in terms of discrete Fourier transform (Beylkin, 1987; Kelley & Madisetti, 1993; Gotz & Druckmuller, 1996; Brady, 1998; Boag et al., 2000; Brandt et al., 2000; Press, 2006). As a result, the existing definitions of discrete versions of ridgelet transform have no such Fourier expression either (Do & Vetterli, 2003; Carre & Andres, 2004; Helbert et al., 2006). By contrast, we here show that our formulation of the discrete ridgelet transform \(\mathcal{R}[f]\) has the following exact characterization in the Fourier transform. See Appendix A for proof.

**Theorem 2.1** (Fourier slice theorem for discrete ridgelet transform).: _For any function \(f:\mathbb{R}^{D}\to\mathbb{R}\) and any point \(\mathbf{a}\in\mathbb{Z}_{P}^{D},v\in\mathbb{Z}_{P}\) in the discretized space, it holds that_

\[\mathcal{F}_{1}[\mathcal{R}[f](\mathbf{a},\cdot)](v)=\mathcal{F}_{D}[f](v\mathbf{a} \bmod P)\ \overline{\mathcal{F}_{1}[r](v)}. \tag{9}\]
### Exact representation of functions as neural networks

Using the discrete ridgelet transform in Sec. 2.1, we here show that any function \(f\) on the discretized domain has an **exact representation** in terms of a shallow neural network with a finite number of parameters in the discretized space. In the continuous case, any square-integrable function \(f\) is represented as the continuous limit of the shallow neural networks, i.e., \(f=S[w]\) in (1), with the weight given by the ridgelet transform \(w\propto R[f]\)(Sonoda and Murata, 2017). With discretization, it is nontrivial to show such an exact representation due to finite precision in discretizing the real number. Nevertheless, we here show that any function \(f(\mathbf{x})\) for \(\mathbf{x}\in\mathbb{Z}_{P}^{D}\) can be exactly represented as \(f(\mathbf{x})=\mathcal{S}[w](\mathbf{x})\) as well, with the weight given by our formulation of the discrete ridgelet transform \(w\propto\mathcal{R}[f]\), which we may call exact representation as a discretized neural network.

In particular, the following theorem shows that any \(D\)-dimensional real function \(f\) on the discrete domain can be exactly represented as a linear combination of non-orthogonal basis functions \(\{g((\mathbf{a}^{\top}\mathbf{x}-b)\bmod P):(\mathbf{a},b)\in\mathbb{Z}_{P}^{D}\times \mathbb{Z}_{P}\}\) with coefficients given by \(\mathcal{R}[f]\). Due to the non-orthogonality, the coefficients may not be unique, and different choices of the ridgelet function \(r\) in (8) lead to different \(\mathcal{R}[f]\) while any of the choices can exactly reconstruct \(f\). The proof is based on the Fourier slice theorem in Theorem 2.1, crucially using the existence of an inverse element for each element of a finite field \(\mathbb{Z}_{P}\); thus, it is essential to assume that \(P\) is a prime number. See Appendix B for proof.

**Theorem 2.2** (Exact representation of function as discretized neural network).: _For any function \(f:\mathbb{R}^{D}\rightarrow\mathbb{R}\) and any point \(\mathbf{x}\in\mathbb{Z}_{P}^{D}\) in the discretized domain, we have_

\[f(\mathbf{x})=C_{g,r}^{-1}\;\mathcal{S}[\mathcal{R}[f]](\mathbf{x}), \tag{10}\]

_where \(C_{g,r}\) is a constant defined in (6)._

## 3 Quantum ridgelet transform

In this section, we introduce **quantum ridgelet transform (QRT)**, an efficient quantum algorithm for implementing the discrete ridgelet transform formulated in Sec. 2. In various quantum algorithms, we may use quantum Fourier transform (QFT) as a fundamental subroutine. In addition to QFT, various discrete transforms can be efficiently implemented with quantum computation, such as wavelet transform (Hoyer, 1997; Fijany and Williams, 1998; Labunets et al., 2001a; Arguello, 2009; Taha, 2016; Li et al., 2019, 2022), Radon transform (Ma et al., 2022), fractional Walsh transform (Labunets et al., 2001b), Hartley transform (Tseng and Hwang, 2004), and curvelet transform (Liu, 2009). However, the existing discrete versions of ridgelet transform (Do and Vetterli, 2003; Carre and Andres, 2004; Helbert et al., 2006) were lacking implementation by quantum computation. In contrast, our QRT opens a way to use the discrete ridgelet transform as a fundamental subroutine for QML to deal with tasks for classical neural networks.

Basic notions and notations of quantum computation to describe our quantum algorithms are summarized in Appendix C. In classical computation, we may use \(\lceil\log_{2}(P)\rceil\) bits for representing \(\mathbb{Z}_{P}\), where \(\lceil x\rceil\) denotes the ceiling function, i.e., the smallest integer that is not smaller than \(x\). The quantum algorithm uses a \(\lceil\log_{2}(P)\rceil\)-qubit quantum register for \(\mathbb{Z}_{P}\). This quantum register for \(\mathbb{Z}_{P}\) is represented as a \(2^{\lceil\log_{2}(P)\rceil}\)-dimensional complex vector space \(\mathcal{H}_{P}\coloneqq(\mathbb{C}^{2})^{\otimes\lceil\log_{2}(P)\rceil}\). Using the conventional bra-ket notation, each state in the standard orthonormal basis of the registers is written as a ket (i.e., a vector) \(\ket{\mathbf{x}}\in\mathcal{H}_{P}^{\otimes D}\) for representing \(\mathbf{x}\in\mathbb{Z}_{P}^{D}\) and \(\ket{\mathbf{a},b}\coloneqq\ket{\mathbf{a}}\otimes\ket{b}\in\mathcal{H}_{P}^{\otimes D }\otimes\mathcal{H}_{P}\) for \((\mathbf{a},b)\in\mathbb{Z}_{P}^{D}\times\mathbb{Z}_{P}\), respectively.

The task of QRT is to transform a given unknown quantum state \(\ket{\psi}=\sum_{\mathbf{x}}\psi(\mathbf{x})\ket{\mathbf{x}}\) into \(\mathbf{R}\ket{\psi}=\sum_{\mathbf{a},b}\mathcal{R}[\psi](\mathbf{a},b)\ket{\mathbf{a},b}\), where \(\mathbf{R}\) is a matrix given by

\[\mathbf{R}\coloneqq P^{-\frac{D}{2}}\sum_{\mathbf{x},\mathbf{a},b}r((\mathbf{a}^{\top}\mathbf{x}-b) \bmod P)\ket{\mathbf{a},b}\bra{\mathbf{x}}. \tag{11}\]

Our algorithm works with the following assumption along with those assumed in Sec. 2.1.

* We choose the ridgelet function \(r:\mathbb{R}\rightarrow\mathbb{R}\) in such a way that a quantum state representing \(r\) by its amplitude \(\ket{r}\coloneqq\sum_{y}r(y)\ket{y}\) can be prepared efficiently in runtime \(O(\mathrm{polylog}(P))\). This assumption is not restrictive since we can use the quantum algorithm by Grover and Rudolph (2002) to meet the assumption for representative choices of \(r\) that are integrable efficiently, such as ReLU, tanh, and sigmoid.

Algorithm 1 shows our quantum algorithm for QRT. We construct the algorithm by implementing the discrete Fourier transform in the Fourier slice theorem (Theorem 2.2) by QFT. QFT applies a unitary matrix representing discrete Fourier transform

\[\mathbf{F}_{P}\coloneqq\sum_{v,b}P^{-\frac{1}{2}\mathrm{e}^{\frac{-2\pi\mathrm{i \hbar}}{P}}}\ket{v}\bra{b} \tag{12}\]

to a given quantum state of \(\mathcal{H}_{P}\) within runtime \(O(\mathrm{polylog}(P))\)(Mosca and Zalka, 2004). The runtime of QFT \(\mathbf{F}_{P}\) is exponentially faster in \(P\) than the classical algorithm for fast Fourier transform in the space of size \(P\). The following theorem shows that this speedup is also the case in QRT compared to classical algorithms for computing ridgelet transform. See Appendix C for proof.

**Theorem 3.1** (Runtime of quantum ridgelet transform).: _The runtime of QRT in Algorithm 1 is_

\[O(D\times\mathrm{polylog}(P)). \tag{13}\]
## 4 Application of quantum ridgelet transform to lottery ticket hypothesis

### Setting of finding winning ticket of neural networks

In this section, as an application of quantum ridgelet transform (QRT) in Sec. 3, we propose an algorithm for finding a sparse subnetwork approximating a large neural network efficiently by quantum computation, based on the **lottery ticket hypothesis** on neural networks. The lottery ticket hypothesis by Frankle and Carbin (2019) claims that a randomly-initialized fully-connected neural network contains a subnetwork that is initialized in such a way that, when trained in isolation, it can match the accuracy of the original network after training for at most the same number of iterations. This hypothesis has been confirmed numerically in various settings. The theoretical analysis of deep neural networks is inevitably hard in general, and studies of shallow neural networks are also important for capturing essences of neural networks, which we here consider in a setting of regression from given data as described in the following.

For \(D\in\{1,2,\ldots\}\) with a fixed prime number \(P\), we consider a family of problems to approximate an unknown function \(f^{(D)}:\mathbb{R}^{D}\rightarrow\mathbb{R}\) by a shallow neural network, i.e.,

\[\hat{f}^{(D)}(\mathbf{x})\coloneqq\sum_{n=1}^{N}w_{n}g((\mathbf{a}_{n}^{\top}\mathbf{x}-b_{ n})\bmod P). \tag{16}\]

Let \(p_{\mathrm{data}}^{(D)}\) be a probability mass function for the input data, which is assumed to be supported on \(\mathbb{Z}_{P}^{D}\). Suppose that we are given \(M\) input-output pairs of examples \((\mathbf{x}_{1},y_{1}=f(\mathbf{x}_{1})),\ldots,(\mathbf{x}_{M},y_{M}=f(\mathbf{x}_{M}))\in \mathbb{Z}_{P}^{D}\times\mathbb{R}\). Let \(\hat{p}_{\mathrm{data}}^{(D)}\) denote the empirical distribution of \(\mathbf{x}_{1},\ldots,\mathbf{x}_{M}\). Given \(\epsilon>0\), we will analyze empirical risk minimization (Bach, 2021), i.e., minimization of the empirical risk \(\sum_{\mathbf{x}}\hat{p}_{\mathrm{data}}^{(D)}(\mathbf{x})|f^{(D)}(\mathbf{x})-\hat{f}^{( D)}(\mathbf{x})|^{2}\) to \(O(\epsilon)\). If obvious, we may omit \(D\) in superscripts; e.g., we may write \(f^{(D)}\) as \(f\).

The setting of our analysis, along with the assumptions in Sec. 3, is as follows. Based on the exact representation of \(f(\mathbf{x})\) in terms of the neural network \(\mathcal{S}[w](\mathbf{x})\) in Theorem 2.2, we can approximate \(f\) by a neural network

\[f(\mathbf{x})\!\approx\!\mathcal{S}[w_{\lambda}^{*}](\mathbf{x})\!=\!\!\sum_{\mathbf{a},b} P^{-\frac{D}{2}}w_{\lambda}^{*}(\mathbf{a},b)g((\mathbf{a}^{\top}\mathbf{x}\!-\!b)\bmod P), \tag{17}\]

where \(w_{\lambda}^{*}\) is the optimal solution of the ridge regression with the empirical distribution, i.e.,

\[w_{\lambda}^{*}(\mathbf{a},b)\coloneqq\arg\min_{w}\{\tilde{J}(w)\}, \tag{18}\]

\(\tilde{J}(w)\coloneqq J(w)+\lambda\Omega(w)\), \(J(w)\coloneqq\sum_{\mathbf{x}}\hat{p}_{\mathrm{data}}(\mathbf{x})|f(\mathbf{x})-\mathcal{S }[w](\mathbf{x})|^{2}\), \(\Omega(w)\coloneqq\|P^{-\frac{D}{2}}w\|_{2}^{2}=\sum_{\mathbf{a},b}|P^{-\frac{D}{2} }w(\mathbf{a},b)|^{2}\), and \(\lambda>0\) is a hyperparameter for regularization. Learning a general class of function \(f^{(D)}\) on \(\mathbb{Z}_{P}^{D}\) would be inevitably demanding as its representation would require \(\exp(O(D))\) parameters to specify the values \(f^{(D)}(\mathbf{x})\) for all \(\mathbf{x}\in\mathbb{Z}_{P}^{D}\) in the worst case. We have shown such a general representation in Theorem 2.2. By contrast, our goal here is to achieve the approximation feasibly with much fewer parameters, using a subnetwork of the large original network \(\mathcal{S}[w_{\lambda}^{*}](\mathbf{x})\).

To this goal, recall that it is conventional in statistical learning theory to consider a reasonably restricted class of functions, e.g., those with bounded norms (Bach, 2021); correspondingly, we work on a setting where the norm \(\|P^{-\frac{D}{2}}w_{\lambda}^{*}\|_{1}\coloneqq\sum_{\mathbf{a},b}|P^{-\frac{D}{2 }}w_{\lambda}^{*}(\mathbf{a},b)|\) of the weights for representing \(f^{(D)}\) should be bounded even on the large scales \(D\rightarrow\infty\). In particular, let \(((\mathbf{a}_{j},b_{j})\in\mathbb{Z}_{P}^{D}\times\mathbb{Z}_{P}:j\in\{1,\ldots, P^{D+1}\})\) denote a sequence of parameters of all nodes in the hidden layer of \(\mathcal{S}[w_{\lambda}^{*}](\mathbf{x})\) aligned in the descending order of \(w_{\lambda}^{*}\), i.e., \(|w_{\lambda}^{*}(\mathbf{a}_{1},b_{1})|\geq|w_{\lambda}^{*}(\mathbf{a}_{2},b_{2})| \geq\cdots\). These nodes of \(\mathcal{S}[w_{\lambda}^{*}]\) are ordered in the same way; i.e., the weight of the \(j\)th node is \(w_{\lambda}^{*}(\mathbf{a}_{j},b_{j})\). Then, we assume the following.
* Following the convention of assumptions in the previous works by, e.g., Donoho (1993); Hayakawa and Suzuki (2020), we assume that there exist constants \(\alpha,\beta>0\) such that it holds uniformly for any \(D\) and \(j\) that \[|P^{-\frac{D}{2}}w_{\lambda}^{*}(\mathbf{a}_{j},b_{j})|\leqq\alpha j^{-(1+\beta)},\] (19) which specifies the decay rate for large \(j\), leading to \(\|P^{-\frac{D}{2}}w_{\lambda}^{*}\|_{1}\leqq\sum_{j=1}^{\infty}\alpha j^{-(1+ \beta)}\leqq\alpha+\int_{1}^{\infty}\frac{\alpha}{x^{1+\beta}}dx=\alpha+\frac {\alpha}{\beta}<\infty\). We also write the \(L^{2}\) norm as \[\gamma\coloneqq\|P^{-\frac{D}{2}}w_{\lambda}^{*}\|_{2}^{2},\] (20) which is upper bounded by \(\gamma\leqq\sum_{j=1}^{\infty}\alpha^{2}j^{-2(1+\beta)}\leqq\alpha^{2}+\int_ {1}^{\infty}\frac{\alpha^{2}}{x^{2(1+\beta)}}dx=\alpha^{2}+\frac{\alpha^{2}}{ 1+2\beta}\). Functions \((f^{(D)}:D=1,2,\ldots)\) satisfying (19) are called \((\alpha,\beta)\)-class functions, which are to be learned in our setting.

For given \(\epsilon>0\), our analysis focuses on the task of finding a sparse representation \(\hat{f}\) to approximate \(\mathcal{S}[w_{\lambda}^{*}]\) up to \(\epsilon\), i.e.,

\[\sum_{\mathbf{x}}\hat{p}_{\mathrm{data}}(\mathbf{x})|\mathcal{S}[w_{\lambda}^{*}](\bm {x})-\hat{f}(\mathbf{x})|^{2}=O(\epsilon), \tag{21}\]

with keeping the number of nodes \(N\) in the hidden layer of \(\hat{f}\) in (16) as small as possible. We assume that \(\lambda>0\) is chosen appropriately so that (21) leads to \(\sum_{\mathbf{x}}\hat{p}_{\mathrm{data}}(\mathbf{x})|f(\mathbf{x})-\hat{f}(\mathbf{x})|^{2}=O(\epsilon)\), achieving the empirical risk minimization with \(\hat{f}\). Note that if we fix \(D\), then for any \(f\), we may be able to find sufficiently large \(\alpha\) and small \(\beta\) to meet (19), but our analysis will show that assuming smaller \(\alpha\) and larger \(\beta\) guarantees smaller \(N\) to achieve (21) for the \((\alpha,\beta)\)-class functions for arbitrary \(D\).

### Quantum algorithm for sampling from optimized probability distribution

We here construct a quantum algorithm for sampling from an **optimized probability distribution** (defined later as \(p_{\lambda,\Delta}^{*}(\mathbf{a},b)\) in (22)) of parameters of nodes in the hidden layer of the large original network \(\mathcal{S}[w_{\lambda}^{*}]\) in (17), which we can use for efficiently finding a sparse subnetwork of \(\mathcal{S}[w_{\lambda}^{*}]\) to approximate \(f\) well. The original network \(\mathcal{S}[w_{\lambda}^{*}]\) has \(\exp(O(D))\) nodes to represent any function \(f\), as with Theorem 2.2. By contrast, studies on the lottery ticket hypothesis provide numerical evidences that \(f\) in practice can usually be approximated by a sparse subnetwork with much fewer parameters. One existing way to find such a subnetwork is to train the overall large network and then perform masking to eliminate the low-weight nodes while keeping those with higher weights (Frankle and Carbin, 2019). However, this approach is inefficient since one needs large-scale optimization to train the large original network before the pruning. Then, more recent studies by Zhou et al. (2019); Ramanujan et al. (2020); Wang et al. (2020); Malach et al. (2020); Orseau et al. (2020); Pensia et al. (2020) have suggested that one should be able to find the subnetwork only by pruning the initial network directly, even without the optimization for training. Still, to perform this pruning appropriately, one needs to perform a large-scale search for the subnetwork within the parameter space of the large original neural network. As \(D\) increases, it would become infeasible to deal with the large original network for training or searching as long as we use the existing methods based on classical computation.

To address this problem, our key idea is to represent the weights of the \(\exp(O(D))\) nodes in the hidden layer of the neural network \(\mathcal{S}[w_{\lambda}^{*}]\) efficiently as the amplitude of quantum state of only \(O(D)\) qubits. Roughly speaking, as in Theorem 2.2, these weights can be given by the discrete ridgelet transform \(\mathcal{R}[f]\) of \(f\), which is implementable efficiently by QRT. In particular, if we initially have a quantum state \(\ket{f}=\sum_{\mathbf{x}}f(\mathbf{x})\ket{\mathbf{x}}\), then QRT of \(\ket{f}\) can prepare \(\mathbf{R}\ket{f}=\sum_{\mathbf{a},b}\mathcal{R}[f](\mathbf{a},b)\ket{\mathbf{a},b}\) in time \(\widetilde{O}(D)\) as shown in Theorem 3.1, where \(\widetilde{O}\) may ignore polylogarithmic factors. A measurement of this quantum state \(\mathbf{R}\ket{f}\) in basis \(\{\ket{\mathbf{a},b}\}\) provides a measurement outcome \((\mathbf{a},b)\) sampled from a probability distribution proportional to the square of the amplitude, i.e., \(|\mathcal{R}[f](\mathbf{a},b)|^{2}\). In this way, we can find parameter \((\mathbf{a},b)\) for a node with large \(|\mathcal{R}[f](\mathbf{a},b)|^{2}\) with high probability, in runtime \(\widetilde{O}(D)\) per sampling. The state is corrupted by the measurement, and to perform the sampling \(N\) times, we repeat the preparation and measurement \(N\) times. To sample \((\mathbf{a},b)\) for all high-weight nodes with high probability in a theoretically guaranteed way, for \(\Delta>0\), we introduce an **optimized probability distribution**

\[p_{\lambda,\Delta}^{*}(\mathbf{a},b)\coloneqq\frac{1}{Z}\frac{|P^{-\frac{D}{2}}w_{ \lambda}^{*}(\mathbf{a},b)|^{2}}{|P^{-\frac{D}{2}}w_{\lambda}^{*}(\mathbf{a},b)|^{2}+ \Delta}, \tag{22}\]

where \(Z\) is a constant for normalization \(\sum_{\mathbf{a},b}p_{\lambda,\Delta}^{*}(\mathbf{a},b)=1\). Appropriate \(\Delta\) for our task in (21) will be specified later in Theorem 4.2. To sample from \(p_{\lambda,\Delta}^{*}\), we prepare

\[\ket{p_{\lambda,\Delta}^{*}}\coloneqq\frac{1}{\sqrt{Z}}\sum_{\mathbf{a},b}\frac{ P^{-\frac{D}{2}}w_{\lambda}^{*}(\mathbf{a},b)}{\sqrt{|P^{-\frac{D}{2}}w_{\lambda}^{*}( \mathbf{a},b)|^{2}+\Delta}}\ket{\mathbf{a},b}, \tag{23}\]

followed by performing the measurement of \(\ket{p_{\lambda,\Delta}^{*}}\) in the same way as described above.

We explicitly construct an input model for our quantum algorithm by quantum circuit as follows.

* As an input, our algorithm uses quantum circuits to prepare \(\ket{\hat{p}_{\mathrm{data}}}=\sum_{\mathbf{x}}\sqrt{\hat{p}_{\mathrm{data}}(\mathbf{x })}\ket{\mathbf{x}}\) and \(\ket{\psi_{\mathrm{in}}}\propto\sum_{\mathbf{x}}\hat{p}_{\mathrm{data}}(\mathbf{x})f(\mathbf{ x})\ket{\mathbf{x}}\). Regarding \(\ket{\hat{p}_{\mathrm{data}}}\), if we prepare \(\ket{\hat{p}_{\mathrm{data}}}\) and measure it in basis \(\{\ket{\mathbf{x}}\}\), we can randomly sample \(\mathbf{x}\) according to the empirical distribution \(\hat{p}_{\mathrm{data}}(\mathbf{x})\). For a classical algorithm, sampling from
\(\hat{p}_{\rm data}\) can be easily realized in time \(O(D\operatorname{polylog}(M))\) over \(M\) examples of \(D\)-dimensional input, by sampling \(m\in\{1,\ldots,M\}\) from the uniform distribution over \(O(\log(M))\) bits and outputting \(\mathbf{x}_{m}\in\mathbb{Z}_{D}^{D}\) out of \(\mathbf{x}_{1},\ldots,\mathbf{x}_{M}\) stored in random access memory (RAM). As for the quantum algorithm, the preparation of \(|\hat{p}_{\rm data}\rangle\) with maintaining quantum superposition may be more technical. But we show that this preparation is also implementable in time \(O(D\operatorname{polylog}(M))\), by storing the \(M\) examples upon collecting them in a sparse binary-tree data structure (Kerenidis and Prakash, 2017) with quantum RAM (QRAM) (Giovannetti et al., 2008; b), where QRAM is implemented explicitly as a parallelized quantum circuit of depth \(O(\operatorname{polylog}(M))\)(Matteo et al., 2020; Hann et al., 2021). Using the same data structure, we also show that the preparation of \(|\psi_{\rm in}\rangle\) is implemented within the same runtime \(O(D\operatorname{polylog}(M))\). As a whole, our assumption is to store the \(M\) examples in these data structures upon collecting them, so that each preparation of \(|\hat{p}_{\rm data}\rangle\) and \(|\psi_{\rm in}\rangle\) has runtime \(O(D\operatorname{polylog}(M))=\widetilde{O}(D)\). See Appendix D for detail.

The following theorem shows that we have a quantum algorithm that can prepare and measure \(|p^{*}_{\lambda,\Delta}\rangle\) to sample from \(p^{*}_{\lambda,\Delta}\) within a linear runtime \(\widetilde{O}(\frac{D}{\lambda\Delta})\). Our algorithm is based on the analytical formula for the solution of ridge regression in (18); in particular, with \(r=g\), the formula leads to

\[|p^{*}_{\lambda,\Delta}\rangle\propto\left(\mathbf{W}_{\lambda}+\frac{\Delta}{ \gamma}\mathbf{I}\right)^{-\frac{1}{2}}\!\left(\mathbf{R}\hat{\mathbf{P}}_{\rm data}\mathbf{R}^ {\top}+\lambda\mathbf{I}\right)^{-1}\!\!\mathbf{R}\,|\psi_{\rm in}\rangle\,, \tag{24}\]

where \(\mathbf{W}_{\lambda}\coloneqq\gamma^{-1}\sum_{\mathbf{a},\mathbf{b}}|P^{-\frac{D}{2}}w^{* }_{\lambda}(\mathbf{a},b)|^{2}\left|\mathbf{a},b\right\rangle\left\langle\mathbf{a},b\right|\) and \(\hat{\mathbf{P}}_{\rm data}\coloneqq\sum_{\mathbf{a}}\hat{p}_{\rm data}(\mathbf{x})\left| \mathbf{x}\right\rangle\left\langle\mathbf{x}\right|\). The algorithm is also explicitly presented as Algorithm 2 in Appendix D. See Appendix D for proof of its runtime as well.

**Theorem 4.1** (Runtime of quantum algorithm for sampling from the optimized probability distribution).: _Given \(\lambda,\Delta>0\), for any \(D\), a quantum algorithm can prepare and measure \(|p^{*}_{\lambda,\Delta}\rangle\) to sample from \(p^{*}_{\lambda,\Delta}(\mathbf{a},b)\) within runtime \(\widetilde{O}\left(\frac{D}{\lambda\Delta}\times\gamma\right)\) per sampling, where \(\gamma\) is a constant in (20)._

Remarkably, our construction of the quantum algorithm for Theorem 4.1 is based on two significant technical contributions. First, estimation of classical description of \(|p^{*}_{\lambda,\Delta}\rangle\) would need \(\exp(O(D))\) runtime and may cancel out the advantage of QML (Aaronson, 2015), but we avoid such slowdown. In particular, our quantum algorithm prepares \(|p^{*}_{\lambda,\Delta}\rangle\) directly from the \(M\) examples and then measure it to obtain parameter \((\mathbf{a},b)\) for a high-weight node of \(\mathcal{S}[w^{*}_{\lambda}]\) per single preparation and measurement. In this way, we circumvent the costly process of expectation-value estimation throughout our algorithm. Second, we develop a technique for implementing the inverses of \(\exp(O(D))\times\exp(O(D))\) matrices in (24) with quantum computation efficiently, yet without imposing restrictive assumptions. In particular, the inverses of \(\exp(O(D))\times\exp(O(D))\) matrices are hard to compute in classical computation, and conventional techniques in QML have required sparsity or low-rankness of the matrices to implement matrix inversion with large quantum speedups (Gilyen et al., 2019). More recent quantum-inspired classical algorithms also require the low-rank assumption (Tang, 2019). However, the matrices to be inverted in our algorithm are not necessarily sparse or low-rank, and thus imposing such assumptions would limit the applicability of QML. By contrast, we avoid imposing these assumptions by directly clarifying the quantum circuits for implementing these matrices efficiently with QRT. In the existing research, this type of technique for avoiding the sparsity and low-rankness assumptions in QML was established only for Fourier transform (Yamasaki et al., 2020; Yamasaki and Sonoda, 2021). Our development discovers wide applicability of such techniques even to a broader class of transforms including ridgelet transform.

### Quantum algorithm for finding winning ticket of neural networks and performance analysis

Using the quantum algorithm for sampling from \(p^{*}_{\lambda,\Delta}(\mathbf{a},b)\) in Theorem 4.1, we describe **an algorithm for finding a winning ticket**, i.e., a sparse trainable subnetwork of the large original network \(\mathcal{S}[w^{*}_{\lambda}]\) in (17) for approximating \(f\). We also analyze its performance with theoretical guarantee.

We here describe our algorithm for finding a winning ticket, which is also explicitly presented as Algorithm 3 in Appendix E. In our algorithm, we repeat the sampling from \(p^{*}_{\lambda,\Delta}(\mathbf{a},b)\) in total \(N\) times by the quantum algorithm in Theorem 4.1, where \(N\) is given later in (26). Letting \(\hat{\mathbb{W}}\) denote the set of sampled parameters in these \(N\) repetitions, we approximate \(\mathcal{S}[w^{*}_{\lambda}]\) by the subnetwork

\[\mathcal{S}[w^{*}_{\lambda}]\!\approx\!\hat{f}(\mathbf{x})\!=\!\!\!\!\sum_{(\mathbf{a},b )\in\hat{\mathbb{W}}}\hat{w}^{*}(\mathbf{a},b)g((\mathbf{a}^{\top}\mathbf{x}\!-\!b)\! \!\mod P), \tag{25}\]

where we write \(\hat{\mathbf{w}}^{*}\coloneqq(\hat{w}^{*}(\mathbf{a},b)\in\mathbb{R}:(\mathbf{a},b)\in \hat{\mathbb{W}})\). Each sampling provides parameter \((\mathbf{a},b)\in\hat{\mathbb{W}}\) of each node in the hidden layer of this subnetwork but not the value of \(\hat{w}^{*}(\mathbf{a},b)\). Once we fix \(\{g((\mathbf{a}^{\top}\mathbf{x}-b)\!\!\mod P):(\mathbf{a},b)\in\hat{\mathbb{W}}\}\) of the subnetwork, we then train \(\hat{\mathbf{w}}^{*}\) efficiently by the established procedure of convex optimization such as stochastic gradient descent (SGD) (Harvey et al., 2019), using the \(M\) examples. In this way, we achieve our task (21) with trainability.

The following theorem guarantees \(\Delta\) and \(N\) required for achieving our task (21). By combining Theorems 4.1 and 4.2, the overall runtime of our algorithm is \(\widetilde{O}(N\times\frac{D}{\lambda\Delta}\gamma)=\widetilde{O}(\frac{D}{ \lambda e^{1+\beta/\beta}})\), dominated by the \(N\) repetitions of
the sampling in Theorem 4.1. A comparison with classical algorithms analogous to our sampling-based approach is made in Sec. 4.4. See Appendix E for proof.

**Theorem 4.2** (Bounds for finding winning ticket of neural networks).: _Given \(\epsilon,\delta>0\), there exist \(\Delta\) and \(N\) satisfying_

\[\Delta=\Omega\left(\epsilon^{1+\frac{1}{\beta}}\right),\ N=O\left(\epsilon^{- \frac{1}{2\beta}}\log\left(\epsilon^{-1}\delta^{-1}\right)\right), \tag{26}\]

_such that the algorithm described above returns a subnetwork \(\hat{f}\) of the neural network \(\mathcal{S}[w_{\lambda}^{*}]\) with the number of nodes in the hidden layer of \(\hat{f}\) smaller than \(N\), and \(\hat{f}\) achieves the task of approximating \(\mathcal{S}[w_{\lambda}^{*}]\) to \(O(\epsilon)\) in (21) with high probability greater than \(1-\delta\)._

### Advantage of using quantum ridgelet transform

We numerically demonstrate the advantage of our algorithm for winning the lottery ticket of the neural network in Theorem 4.2. For fair comparison between our algorithm and a similar approach for classical algorithms, recall that the essential idea of our algorithm is to avoid computationally hard optimization of the initial neural network by sampling the nodes in its hidden layer to decide the basis functions \(\{g((\boldsymbol{a}^{\top}\boldsymbol{x}-b)\ \mathrm{mod}\ P):( \boldsymbol{a},b)\in\hat{\mathbb{W}}\}\) in (25), followed by efficiently training their coefficients \(\hat{\boldsymbol{w}}^{\star}\) via convex optimization. This idea can be regarded as a generalized form of random features by Rahimi & Recht (2008, 2009), where one randomly samples feature maps, i.e., \(\{g((\boldsymbol{a}^{\top}\boldsymbol{x}-b)\ \mathrm{mod}\ P)\}\), and then find their coefficients by convex optimization. The difference is that we use the optimized distribution \(p_{\lambda,\Delta}^{*}(\boldsymbol{a},b)\) depending on \(f\) and \(\hat{p}_{\mathrm{data}}\), but the random features conventionally performs sampling from a distribution independent of \(f\) and \(\hat{p}_{\mathrm{data}}\), e.g., a uniform distribution \(p_{\mathrm{uniform}}(\boldsymbol{a},b)\coloneqq\frac{1}{P^{D+1}}\). Note that a more recent work by Bach (2017) has proposed to sample optimized random features depending on the data distribution (but still not on \(f\) itself), and this sampling is also efficiently achievable with a quantum algorithm shown by Yamasaki et al. (2020); Yamasaki & Sonoda (2021); however, without QRT in this work, it would not be straightforward to apply such techniques to neural networks. Despite this difference, a quantitative advantage of our algorithm over the random features would be still unclear without numerical simulation, due to the non-orthogonality of the basis functions \(\{g((\boldsymbol{a}^{\top}\boldsymbol{x}-b)\ \mathrm{mod}\ P)\}\) used for the neural network.

We numerically show that our algorithm can find a subnetwork achieving a significantly better empirical risk than that obtained from the random features, as illustrated in Fig. 1. In our numerical experiment, choosing \(D=1\) and \(P=127\), we set the function \(f\) to be learned as a sine function, the empirical distribution as the uniform distribution \(\hat{p}_{\mathrm{data}}(\boldsymbol{x})=\frac{1}{P^{D}}\), and the activation function \(g\) and the ridgelet function \(r\) as ReLU. The sampling from \(p_{\lambda,\Delta}^{*}\) was classically simulated via rejection sampling, and convex optimization of \(\hat{w}^{*}\) was solved by MOSEK (ApS, 2022) and YALMIP (Lofberg, 2004). For \(N\leqq 120\), we plotted the achievable empirical risk with \(N\) repetitions of the sampling from \(p_{\lambda,\Delta}^{*}\) and that from \(p_{\mathrm{uniform}}\). See Appendix F for detail. The advantage of our algorithm in finding a sparse trainable subnetwork over the random features can be order of magnitude in terms of the empirical risk achievable by the subnetwork. We emphasize that our classical simulation using rejection sampling of \(p_{\lambda,\Delta}^{*}\) is not scalable as \(D\) increases; by contrast, our results make it possible to take the advantage in higher dimension \(D\gg 1\) if we can use quantum computation for accelerating the task.

## 5 Conclusion

We have formulated the discrete ridgelet transform that can be characterized via Fourier slice theorem and can represent any function exactly in the discretized domain. Furthermore, as a fundamental subroutine for quantum machine learning (QML), we have constructed quantum ridgelet transform (QRT), a quantum algorithm for applying \(D\)-dimensional discrete ridgelet transform to a quantum state efficiently in linear time \(\widetilde{O}(D)\). We have also clarified an application of QRT for finding a sparse trainable subnetwork of a large-scale neural network to approximate a function to be learned, opening an efficient way to demonstrate lottery ticket hypothesis. These results discover a promising use of QML to accelerate the tasks for classical neural networks. Also from a broader perspective, our quantum algorithms may need a fault-tolerant quantum computer that is actively under development, and our achievement lays a solid theoretical foundation for further hardware development and social

Figure 1: The empirical risks achievable with the subnetworks of the large original neural network found by \(N\) repetitions of sampling from the optimized distribution \(p_{\lambda,\Delta}^{*}(\boldsymbol{a},b)\) in (22) via our algorithm in Theorem 4.2 (blue thick line), and that from the uniform distribution via random features (red dashed line). Each line represents the average over \(20\) executions of the algorithms, while each error bar represents the unbiased estimation of the standard deviation for these executions. The advantage of using our algorithm over the simple application of the random features can be order of magnitude in terms of the empirical risk in this regime.
implementation toward realizing quantum computation.

## Acknowledgements

Hayata Yamasaki was supported by JSPS Overseas Research Fellowship, JST PRESTO Grant Number JPMJPR201A and MEXT Quantum Leap Flagship Program (MEXT QLEAP) JPMXS0118069605, JPMXS0120351339. Sathyawageswar Subramanian was supported by Royal Commission for the Exhibition of 1851 Research Fellowship in Science and Engineering. Sho Sonoda was supported by JST PRESTO Grant Number JPMJPR2125.
