Classically Approximating Variational Quantum Machine Learning with Random Fourier Features
Authors: Jonas Landman
Slimane Thabet
Constantin Dalyac
Hela Mhiri
Elham Kashefi
Venue: ICLR 2023 poster (2023)
Keywords: Quantum Machine Learning
Variational Quantum Circuits
Random Fourier Features
Kernel Approximation
Quantum Computing

Abstract: Many applications of quantum computing in the near term rely on variational quantum circuits (VQCs). They have been showcased as a promising model for reaching a quantum advantage in machine learning with current noisy intermediate scale quantum computers (NISQ). It is often believed that the power of VQCs relies on their exponentially large feature space, and extensive works have explored the expressiveness and trainability of VQCs in that regard. In our work, we propose a classical sampling method that can closely approximate most VQCs with Hamiltonian encoding, given only the description of their architecture. It uses the seminal proposal of Random Fourier Features (RFF) and the fact that VQCs can be seen as large Fourier series. We show theoretically and experimentally that models built from exponentially large quantum feature space can be classically reproduced by sampling a few frequencies to build an equivalent low dimensional kernel. Precisely, we show that the number of required samples grows favourably with the size of the quantum spectrum. This tool therefore questions the hope for quantum advantage from VQCs in many cases, but conversely helps to narrow the conditions for their potential success. We expect VQCs with various and complex encoding Hamiltonians, or with large input dimension, to become more robust to classical approximations.

Published as a conference paper at ICLR 2023
CLASSICALLY APPROXIMATING VARIATIONAL QUAN- TUM MACHINE LEARNING WITH RANDOM FOURIER FEATURES
Jonas Landman
Slimane Thabet LIP6. Sorbonne Université PASQAL SAS
Constantin Dalyac
University of Edinburgh
LIP6, Sorbonne Université PASQAL SAS
QC Ware
Hela Mhiri
Elham Kashefi
LIP6, Sorbonne Université
University of Edinburgh LIP6, Sorbonne Université
ENSTA Paris
ABSTRACT
Many applications of quantum computing in the near term rely variational quantum circuits (VQCs). They have been showcased as a promising model for reaching a quantum advantage machine learning with current noisy intermedi- ate scale quantum computers (NISQ). It is often believed that the power of VQCs relies on their exponentially large feature space, and extensive works have ex- plored the expressiveness and trainability of VQCs in that regard. In our work, we propose a classical sampling method that can closely approximate most VQCs with Hamiltonian encoding, given only the description of their architecture. It uses the seminal proposal of Random Fourier Features (RFF) and the fact that VQCs can be seen as large Fourier series. We show theoretically and experimentally that models built from exponentially large quantum feature space can be classically reproduced by sampling few frequencies to build equivalent low dimensional kernel. Precisely, we show that the number of required samples grows favorably with the size of the quantum spectrum. This tool therefore questions the hope for quantum advantage from VQCs in many cases, but conversely helps to narrow the conditions for their potential success. We expect VQCs with various and complex encoding Hamiltonians, or with large input dimension, to become more robust to classical approximations.
INTRODUCTION
Many applications of quantum computing in the near term rely on variational quantum circuits (VQCs) (Bharti et al. (2021); Cerezo et al. (202T), )), and in particular for solving machine learning (ML) tasks. VQCs are trained using classical optimization of their gates' parameters, a method borrowed from classical neural networks. Although the term VQCs encompasses various methods for different ML tasks, in this paper we refer to VQCs as a family of quantum models for supervised learning on classical data, as defined in B. Many early works have shown promising results, both empirically and in theory (Cong et al. (2019); Huang et al. (202T). However, whether these variational methods can provide quantum advantage in the general case with scaling number of qubits has yet to be proved.
The notion of quantum advantage with respect to classical methods is plural and can be defined as advantage in trainability (Larocca et al. (202T)), expressivity (Schuld et al. (202T)) or generalization (Caro et al.) (2022)). In this paper, we focus on the expressive power of VQCs as it is crucial to understand the capacity of VQCs to generate models that would be hard to do with classical approaches. The most common and intuitive answer for expressive power of VQCs is the formation of large feature space, due to the projection of data points in exponentially large Hilbert space. Understanding what is happening in this Hilbert space, and most importantly, knowing how we exploit its size is an important question for this field. Regarding expressivity, Fair comparison

---

Published as a conference paper at ICLR 2023
Training Quantum Computer
iipl
19)
Quantum Circuit Description
ini
Training with Classical Approximation
Spectrum Extraction
Random Fourier Features
Figure I: Random Fourier Features as a classical approximator of quantum models. Instead of training a Variational Quantum Circuit by using quantum computer, we propose to train a classical kernel built by sampling a few frequencies of the quantum model. These frequencies can derived from the quantum circuit architecture, in particular from the encoding gates. Using Random Fourier Features, one can build a classical model which performs as good as the quantum model with a bounded error and number of samples that grows nicely.
between VQCs and classical ML algorithms is crucial challenge. Recent works (Schuld et al. (202T: Schuld (202); ;) Schreiber al. (022)) have shown equivalence between VQCs and both Fourier series and kernel methods. In fact, VQCs are powerful Fourier series: the functions they can
learn are predetermined by set of frequencies which can become numerous with the dimension of the input, and the number and complexity of the quantum gates used.
In this work, we adapt Random Fourier Features (RFF) from Rahimi Recht 2009). a classical sampling algorithm aimed at efficiently approximating some large classical kernel methods. We design three different RFF strategies to approximate VQCs. For each one, we analyze efficiency in reproducing results obtained by a VQC. To do so, we study in detail the expressivity power of VQCs and compare each time with RFF.
Our method consists in analyzing the encoding gates of the VQC to extract the final frequencies of its model and sample from them. Notably, if the VQCs possesses simple encoding gates such as Pauli gates (e.g. Rz), show that the large quantum feature space is not fully exploited, making RFF even more efficient. the number of frequencies in the VQC grows exponentially, the number of samples required by RFF grows only linearly. Finally, have empirically compared VQCs and RFF on real and artificial use cases. On these, RFF were able to match the VQC's answer, and sometimes outperform it.
As a whole, the novelty of our work is to identify cases where the quantum model emanating from VQC can be classically approximated. albeit the VQC being non-classically simulatable. We therefore reduce the hope for expressive advantage of VQCs in such cases. In practice, our method limited by several parameters: inputs with very large dimension, encoding Hamiltonians that are hard to diagonalize, large depths and others (see Appendix FF. We can therefore use the limitations of our method as recipe to build VQCs that are resilient to classical approximation.
SPECTRAL PROPERTIES OF VARIATIONAL QUANTUM CIRCUITS (VQCs)
In this Section, we succinetly recall some properties of VQCs in the context of machine learning, which will be useful for this work. We invite readers that are not familiar with VQCs to consult instead the detailed definitions and explanations provided in the Appendix
VQCs are quantum circuits with parametrized gates. this paper the encoding gates are unitary matrices of the form cxp(-ia) ix, H), where H is Hamiltonian that the quantum computer im- plement, and (... .2a) E Rd is some input data. The other class of gates trainable gates and use parameters that are optimized during the learning phase. At the end of the circuit, measurements performed and yield a classical output called the quantum model f.
2

---

Published as a conference paper at ICLR 2023
f()= =
Σ
(ox) + by sin((x))
H
g
H2
10]
+
Hg
emict
Q
Am Au2
Agp 12
Q = 1A, Ay)
In VQC, classical data is used pa- rameter of encoding gates e -irff where is Hamiltonian matrix (blue). The other gates are trainable ones (green). The result- ing model Fourier series and each type of gate as proper impact on
(h) The frequencies composing the VQC model come from all the combinations of cigenvalues X from cach encoding Hamil- tonian Hj. seen
tree. Redundancy or concentration in the leaves common if the eigenvalues are similar.
Figure 2: Variational Quantum Circuits (I-dimensional example) give rise to Fourier Series (a) and its frequencies can be derived from Hamiltonians of encoding gates (b).
With one-dimensional input (x TK), as shown in Figure this function can be expressed as discrete Fourier series f(z 0) Ewen o (os( + b sin(wr) (Schuld et al. (2021)). We understand that the spectrum Ω will be the key element that defines the potentral expressivity f. The frequencies w E ll are fact derived from the eigenvalues {X] of each encoding Hamiltonian
H.. With L encoding gates, we have
A Aj. i.j E [N]]] where A; X + +... +
are sum of eigenvalues, one per Hamiltonian (see Figure 2
With d-dimensional input, Ω constructed as the Cartesian product over the spectrum of each dimension, therefore Q is set of d-dimensional frequenciess.
We will sometimes focus on Pauli encoding gates, where all encoding Hamiltonians are simple Pauli matrices, with two eigenvalues À = =1 In this case, and with I-dimensional inputs, we have = LI], the set of positive integer frequencies. In dimension d, the spectrum's size becomes [2] O(L") (see Eq 11 for details). A scaled version of Pauli encoding exists, where the Pauli are multiplied with a factor as in Kyriienko et al. (202)); Shin et al. (2022). resulting in larger Q.
We can also write the quantum model in the form f(=;0) = ww)) Schuld 2021 ) where cos(w" xx) sin T x)
aw
bw
<(x)
is the feature vector, and w(f)
is the weight vector
Via
WER
WES
Φ(x) is a mapped version of the input could be key argument to the quantum advantage of VQC. We define the associated kernel as k(x,,') = ((x))"((')) In Appendix B. we show that i has a shift-invarance property, which will be useful later on, when using the Random Fourier Feature framework.
space of dimension 2 An exponential size for Ω
RANDOM FOURIER FEATURES APPROXIMATES DIGHSIINENSON KERNELS
In this Section, we explain the key results of the classical method called Random Fourier Features (RFF) (Rahimi & Recht (2009) Li al. 20019): Sutherland & Schneider (2015). We will use this method to create several classical sampling algorithms for approximating VQCs.
Let X 2 be compact domain and k X X - R be a kernel function. We assume l: is shift invariant, meaning k(r, y) k(x y) T(()), where T= X IR is single variable function, and
3

---

Published as a conference paper at ICLR 2023
will note k = lc to simplify the notation. From Rudin 2017), Bochner's theorem insures that the Fourier transform of a positive function and we can write k(6)
-iw" (im)le-w"" dw. If we assume is also normalized, then the Fourier transform p(w) of ks can be assimilated to a probability distribution. With dataset of M points, fitting a Kernel Ridge Regression (KRR) model with the kernel necessitates M operations to compute the kernel matrix and (M))) to invert it. This becomes impractical when M reaches high value in modern big datasets.
p(w)e
WEE
The idea of the Random Fourier Feature method (Rahimi & Recht 2009 to approximate the
cos(w x)
kernel k by k(x,y) = ((1)) where ((x)
1 /n
sin [m[
where the w,s are
D frequencies i.i.d sampled from the frequency distribution p(w). Formally, it is a Monte-Carlo estimate of k. Note that p(w) can be analytically found in some cases such as Gaussian or Cauchy kernels (Rahimi & Recht (209)). Then instead of fitting a KRR for hi one will solve a Linear Ridge Regression (LRR) with (see details in C). The two problems are equivalent (Bishop & Nasrabadi (2006)), and the number of operations needed for the LRR is OMM + D*). If is much smaller than M, it is much faster than solving the KRR directly. Even if D is big that the linear regression cannot be exactly solved, one can employ stochastic gradient descent or adaptive momentum optimizers such as Adam (Kingma & Ba (2014)). The output of the LRR gradient descent is simply weight vector W that is used to create the approximate function f w ((x).
In Sutherland & Schneider (2055), authors bound the resulting approximation error in the RFF method. We provide the main theorems in Appendix In Theorem we consider the error between the final functions/ f and j. We see that if the error must be constrained such that -x())- [(x)] S e, for > O, one can derive a lower bound on the number D of necessary frequency samples for the approximation hold. Fortunately, the bound on D grows linearly with the input dimension d, and logarithmically with on which is linked to the variance of the frequency distribution p(w).
Finally, note that important take into account the Shannon criterion, stating that one needs at least 2wmax training points to estimate the coefficients of Fourier series of maximum frequency Wmax. In practice, it puts some limitation on the largest frequency one can expect to learn (both classically and quantumly) given an input dataset. Exponentially large frequencies with VQCs, as in Kyriienko et al. (2022); (Shin et al. (2022) would have limited interest with subexponential number of training points. The efficiency of RFF against VQCs in such cases becomes even more interesting, as it allows reducing the number of sample compared to the actual exponential size of Ω.
3 RFF METHODS FOR APPROXIMATING VQCs
In this Section, we present our solutions to approximate a VQC model using classical methods. The intuitive idea is sample some frequencies from the VQC's frequency domain Ω, and train classical model from them, using the RFF methods from Section 2 We present different strategies sample these frequencies and detail in which cases expect our methods to perform well. In Appendix F we study potential limitations to our methods, opening the way for VQCs with strong advantage over classical methods.
3.1 RFF WITH DISTINCT SAMPLING
This strategy described in Algorithm iis the basic approach of using RFF for approximating VQCs. We assume the ability to sample from Q. It is straightforwardly following the method described in Section 2 Indeed, as explained in Section [ the corresponding kernel of the VQC is built from frequencies E Ω and is shift-invariant (see Appendix [B.). which ensures the efficiency of RFF to approximate them. Applying the RFF method would consist in sampling from and reconstructing classical model to approximate the VQC output function f. As shown in Theorem one might require a number of samples for which lower bound scales linearly with the dimension d of the input, and logarithmically with the size of Ω.
4

---

Published as a conference paper at ICLR 2023
Algorithm RFF with Distinct Sampling
Require: VQC model f. and M data points (2y bEMM)
Ensure: Approximate function f
1: Diagonalize the Hamiltonians of the VQC's encoding gates.
2: Use their eigenvalues to obtain all frequencies w E S2 as in [
3: Sample D frequencies (Wi,'* ,wD) from ?
[oosww x)) sintwy x)) kE(11
4: Construct the approximated kernel k(zz, y) o(y) (zx) with o(x) = to
5: Solve the LRR problem (Appendix C. and obtain a weight vector w.
6: Obtain the approximated function f(x) = w o(x)
3.2 RFF WITH TREE SAMPLING
The abovementioned method requires constructing explicitly S2, which can become exponentially large the dimension d of the data points is high (see Appendix(B.2. The size Q also increased if the encoding Hamiltonians have many eigenvalues (like many-body Hamiltonians) or if many encoding gates are used. A large S2 is indeed the main interest of VQCs in the first place, promising large expressivity.
In some cases, and particular for VQC using many Pauli encoding gates, a lot of redundancy occurs in the final frequencies. Indeed, if many eigenvalues are equal, the tree leaves will become redundant. Very small eigenvalues can also create groups of frequencies extremely close to each other, which in some use cases, when tuning their coefficients a and bus can be considered as redundancy. In our numerical experiments (see Figure 7 we observe an interesting phenomenon: on average, the frequencies with the more redundancy tend to obtain larger coefficients. Conversely, isolated frequency are very likely to have small coefficients in comparison, making them "ghost" frequencies of ft. For VQC with solely Pauli encoding gates, we observe that the coefficients of high frequencies are almost stuck to zero during training. Therefore, one can argue that the Distinct Sampling described above can reach even more frequencies than the corresponding VQC. However, if one wants to closely approximate given VQC with RFF, one would not want to sample such isolated frequencies from Ω but instead draw with more probability the redundant frequencies.
Algorithm 2 RFF with Tree Sampling
Require: a VQC model f, and A data points (
Ensure: Approximate function f
Diagonalize the Hamiltonians of the VQC's encoding gates.
2: Sample D paths from the tree shown in Figure 2 obtain D frequencies (wi,". (w)) from Ω
3:
Follow steps 4-6 of Algorithm
This is what we try achieve with Tree Sampling. Knowing the eigenvalue decomposition of each encoding's 's Hamiltonian, we propose to directly sample from the tree shown in Figure [ The first advantage of this method is that it does require computing the whole set Ω, but only draw D positive frequencies, with
paths through the tree (which can be used generate up (2) potential redundancy). Secondly, it naturally tends to sample more frequencies that are redundant, and therefore more key approximate the VQC's function. Overall, could speed up the running time and require fewer samples.
3.3
RFF WITH GRID SAMPLING
The two above methods suffer from a common caveat: if one or more of the encoding Hamiltonians hard to diagonalize, sampling the VQC's frequencies is not possible as it prevents from building some of the branches of the tree shown in Figure 2
Even in this case, propose method to approximate the VQC. If the frequencies unknown, but one can guess an upper bound or their maximum value, we propose the following strategy: We create a grid of frequencies regularly disposed between zero and the upper bound Wmaxs each
5

---

Published as a conference paper at ICLR 2023
dimension. In practice, if unknown the value of Wmax can simply be the largest frequency learnable by the Shannon criterion (see Section hence half the number of training points. Letting s >> 0 be the step on this grid, the number of frequencies dimensions, there are [[waxx/)]] frequency vectors. Therefore, instead of sampling from actual frequencies in S2 one could sample blindly from this grid, hence the name Grid Sampling. At first sight, it might seem ineffective, since none of the frequencies actually in 52 may be represented in the grid. But we show in the Appendix E.2 (Theorem 4 that the error between the VQC's model and the approximation f coming from the grid can be bounded by s. When s is small enough, the number D of samples to reach an error e > 0 grows like 1/e2log(1/s) which is surprisingly efficient. However, the trade-off comes from the fact that small s means very large grid, in particular in high dimension.
single dimension is given by Wmax ss. Over all
Algorithm RFF with Grid Sampling
Require: Assumption on the highest frequency Wmax. a step >> and M data points {æy (aM]s
Ensure: Approximate function f
I: Create a regular grid in [0, Wmax] 1dt with step 8.
2: Sample D frequencies (W), (D) from the grid.
3: Follow steps 4-6 of Algorithm [
3.4 NUMBER OF SAMPLES AND APPROXIMATION ERROR
As introduced in Section 2 (and detailed Theorem 3 the quality of the approximation of RFF to certain error > 0 depends on p(w), its variance, and the number D of frequency samples taken from it. In our case, the continuous distribution p(w) will be replaced by the actual set of frequencies Ω such that p(w)= 1
8w where & represents the Dirac distribution w. As result, can WER
[2]
write the discretized variance as op
Σ p(w))"" w. From this, we want to know the link between WESt
the number D of necessary samples and the size of ft or even the number L of encoding gates per dimension. In the general case, we consider that o, is the average value of w w, that is to say the trace of the multidimensional variance. The more the frequencies are spread, the higher on will be, but the number of frequencies in itself doesn't 't seem to play the key role here.
We provide here a bound on the minimum of samples required to achieve certain error between the RFF model and the complete model in the case of Pauli encoding in the distinct sampling strategy. The proof and details for this theorem is shown in Appendix Section E.I
Theorem 1. Let X be compact set of Rd, and e >> O. We consider a training set {(z,, 9:) M Let f be a VQC model with I, encoding Pauli gates on each of the d dimensions, and full freedom on the associated frequency coefficients, trained with a regularization X. Let o2 = - EM v² and | the diameter of X. Let f be the RFF model with D samples in the distinct sampling strategy trained on the same datasel and the same regularization. Then we can guarantee (f(x)) - -x() S with probability 1 - ō for a number D of samples given by:
(d 1)3
[og(dl?(22) + log C2(A+1)
D= 2
-logō]
X+22
ex²
with C1 and C₂ being constants depending on ag 1x). We recall that in E the notation Ω stands for the computational complexity "Big-S?" notation.
We can conclude that the number D of samples grows linearly with the dimension d, and logarith- mically with the size of Ω. It means that even though the number of frequencies in the spectrum of the quantum circuit is high, only few of them are useful in the model. This fact limits the quantum advantage of such circuits. However, the scaling in c and X, respectively in (21/c²) and ((1/x*) is not favorable, and can limit in practice the use of the RFF method.
An important clarification has to be made over the interpretation of this result. One may think at first sight that the RFF method would be efficient approximate the outputs of any VQC, or find

---

Published as a conference paper at ICLR 2023
"classical surrogate" (Schreiber al. (2022)) Instead, the bound that is provided is the error between a VQC trained on an independent data source and a RFF model trained on the same data. If the dataset fails to correctly represent the data distribution, then the VQC will fail to correctly model it, and the theorem provides the minimal number of samples to perform "as badly", and this number recall that
could be low. This was tested in the numerical simulations in Section + However,
these are bounds that we cannot reach in practice with the current classical and quantum computing resources. They give an intuition on the asymptotic scaling as quantum circuits become larger. Note that this proof changes if we take into account the redundancy of each frequency when sampling from Q2 This will be the case in the Tree Sampling strategy. In that case, the variance becomes even smaller since some frequencies are more weighted than others, in particular for Pauli encoding.
In Appendix F.2 we provide similar theorem for the Grid sampling strategy and general encoding Hamiltonians, summarized in Theorem
4 EXPERIMENTS AND NUMERICS
In this Section, we aim to assess the accuracy and efficiency of our classical methods to approximate VQCs in practice. Each VQC was analyzed using ideal simulators of quantum computers, on a classical computer, without taking the noise into account. Important complementary experiments are provided in Appendix G In particular, we show scaling simulations in Appendix G.5
4.1
USING RFF TO MIMIC RANDOM VQC
VQC encoding structure
Theoretical Spectrum vs. Fourler Transform
RFF Accuracy and number of frequencies sampled
coulfiiints
1500
Theonetical frequence
Empiiial frecuencies
Thee sampling
Distinct sampling
Pauli Encoding
Grid sampling s=0.1
5000
0.075
0.050
200
2500
Tram
0.025
Redundancy: 200 out
0
20
Trequencies
100
0.000
0.0
Number sampled frequencie (fraction of (60
0.2
0.4
0.6
0.8
1.0
Complex Encodling
quhhts Hamiltonian
Fourner coefficients
1250
1000
Empirical frequencies
Theoretical frequencies
Train loss value (MSE)
0.15
Hazz XX,X, + 1X,%
+0 11X, 1N,X,
0.30
Distinct sampling sampling
+N H M,Y, +gll, 7,7e)
500
sampling sm0.1
0.05
Pauli factors
250
(26.3344224000
0.00
Redundancy: 545 ost K792
40
Prequeencies
80
100
sampled frequencies
0.6
Fourrier confficients
Empirical frequencies Theoretical frequencies
Distictt sampinng
Exponential Pauli Encoding
130
Thee sampling
0.300
Grid sampling -m00.1
0.075
0.050
[R] - 122
.50
0.025
Redundancy:
0.000
0.0
1.0
Number of sampled mequencies (fraction of [D))
Figure 3: Approximating random VQCs with three RFF methods. For each type of encoding (basic Pauli, many-body Hamiltonian, scaled Pauli) we have: (Left) averaged the VQC's model and compared its empirical Fourier Transform (blue lines) to the expected Spectrum l2 (red lines), and (Right) measured how many frequency samples were necessary to reproduce the same model classically with our three RFF methods.
In first stage, we focus approximating random VQCs (i.e. with random parameter initialization) using Random Fourier features. All results are gathered in Figure 3 To this end, we fix the quantum spectrum S by making certain choice about the structure of the encoding gates. We then observe and evaluate the performance of our three RFF strategies (Distinct, Tree, and Grid sampling to
approximate the quantum model. For completeness, we have tested our methods on several types of VQCs some with basic Pauli encoding in dimension, in higher dimension (Figure 8 with
non-trivial encoding Hamiltonians, and with scaled Pauli encoding as in Shin et al. 2022) For each
7

---

Published as a conference paper at ICLR 2023
type, have also observed the actual Fourier Transform of the random VQCs model on average, to understand which frequencies appear more frequently in their spectrum. We recommend reading Appendix G.2 for details on methodology and interpretation.
With these experiments, we conclude a few important properties. We observe that when some fre- quencies in the spectrum ? have much redundancy (e.g. Pauli encoding), these frequencies empirically the ones with higher coefficients. In such case, the Tree sampling strategy is able to approximate the VQC's model with fewer samples than the other methods as expected. With more complex Hamiltonians (see Appendix G.2.2 for details), concentrated packets of frequencies ap- pear, and even without much redundancy, both Tree and Distinct sampling require fewer frequency samples to cover these packets. According to these experiments, the worst case scenario for the RFF is uniform probability distribution where all the three sampling techniques will be equivalent. Nonetheless, the theoretical bounds prove that the number of Fourier Features will scale linearly with respect to the spectrum size that scales itself exponentially.
4.2 COMPARING VQC AND RFF ON ARTIFICIAL TARGET FUNCTIONS
A more practical comparison to measure the efficiency of both VQC and RFF on a common target function. We want to when RFF can obtain similar or better results than the VQC on the same task, trained separately. We have seen that for VQCs with Pauli encoding, the Fourier coefficients are rapidly decreasing, cutting out frequencies higher than Weffective from the empirical spectrum. For this reason, we have chosen a particular synthetic target function: we create a sparse Fourier series as a target function s(x) and a VQC with L 200 Pauli encoding gates as the quantum model. In Figure 4 we clearly see that the VQC as well as RFF with Tree sampling cannot learn the frequency 60 Weffective (their train loss reach high limit) while the RFF models based on Distinct and Grid sampling can effectively learn the target function with enough frequency samples. This result shows that even when a VQC with Pauli encoding is trained, it cannot reach all of its theoretical spectrum, thus questioning the expressivity of such quantum model, whereas its classical RFF approximator succeeds in learning the function question. course, when we chose an artificial function for which all frequencies are below Weffective the VQC and all RFF manage to fit it.
Thain lass value (MSE)
Distinct sampling
sampling
og
Grid sampling -=1..1
VCC final loes
-2-
TRFFF 80%
EVOC
[target
0.0
0.4
0.6
0.8
8.0
0.6 Number sampled frequencies es ('raction jop
(a) Predictions of the target function s(x) with the quantum model and corresponding RFF approxima- tor using Distinct sampling on 80% frequencies.
(b) RFF learning curves for sparse target fitting based on the VQC description. Distinct and Grid sampling are able outperform the VQC.
Figure& 4: Fitting target function s(x) Ewe (4,10,60) cos(wa) sin(wx) with VQC architec- ture of L 200 Pauli gates.
4.3 COMPARING VQC AND REF ON REAL DATASETS
Here again, we train separately a VQC and the equivalent RFF model on real-world data to compare their learning performances We choose the Rashion-MNIST dataset (Xiao et al. (2017)), where we consider a binary image classification task. We also use the California Housing dataset for a regres- sion task. We chose to solve the two problems by training VQCs with Pauli encoding (L = 5 for each dimension). According to Eq II the number of distinct positive frequency in f2 is 80526. In Figure 5, we observe that, with very few frequencies sampled, the RFF model with Tree sampling succeeded in learning the distribution of the input datasets as well closely approximating the trained quantum model with a radically lower number of frequencies (0.002 x | ~ 160). This re- sult could indicate that the underlying distributions to learn were simple enough, such that the VQC
8

---

Published as a conference paper at ICLR 2023
had excessive expressivity but could also point to the regularization power of VQC potentially emerging from redundancies (Peters & Schuld 2022).
RFF train MSE
0.9
1.2
RFF test MSE
Accuracy
0.8
VUC train Mat:
0.7
RFF train accuracy
MSE
1.0
VOC test MSE
test accuracy
0.8
0.6
VQC train accuracy
VQC accurary
0.6
0.5
0.000
0.001
0,002
0.003
0.004
0,005
0.000
0,001
0,032
0.003
0.004
0,005
Number of sampled frequencies (fraction of (Q))
Number sampled frequencies (fraction [a]]
(a) Fashion-MNin MNNIST dataset (classification)
(b) California Housing dataset (regression)
Figure 5: Prediction results of RFF (Tree Sampling) on 5-dimensional real datasets.
4.4 NUMERICAL EXPERIMENTS DISCUSSION
The simulations confirm that the spectrum of VQCs are predictable from their encoding gates. We observe however that the actual set of frequencies that emerge with non-zero coefficients does not cover the whole spectrum, questioning the effective expressivity of VQCs in practice. It also con- firms the intuition that frequencies that appear with high redundancy in the spectrum tend to have larger coefficients. The three RFF alternatives we propose to approximate VQCs on several tasks revealed to be efficient. The number D of samples (seen as a fraction of the spectrum size) grows favorably and allows for good approximation. With a highly redundant spectrum our Tree Sampling method, which is the most computationally efficient, was able to approximate VQCs with fewer frequency samples. Tree Sampling inherits the same drawbacks as VQCs and are sometimes not capable of learning less redundant frequencies in the VQCs spectrum, whereas Distinct and Grid sampling can outperform the VQCs in such cases. Even if these experiments are encouraging and match our expectations, of D. the number of samples, becomes even more favorable when the input dimension d increases, or more generally when the spectrum has exponential size. We expect to get closer to the theo- retical bounds and see the number of samples becoming an even smaller fraction of the size of the spectrum. This was partially confirmed in small scale simulations up to d 7. In that regime the theoretical bounds blow up because of the factor in 1/A* so they are not relevant. We have seen that, in order to match the VQCs, some RFF required using 80% of the frequencies, other only 0.001 %. We could go further by training VQCs on actual quantum computers and compare them to classical RFF methods.
are far from the maximal efficiency of RFF methods. Indeed, the scaling
5 CONCLUSION
In this work, we have studied the potential expressivity advantage of Variational Quantum Circuits (VQCs) for machine learning tasks, by providing novel classical methods to approximate VQC'. Our three methods use the fact that sampling few random frequencies from a large dimensional ker- nel (exponentially large in the case of VQCs) can be enough to provide good approximation. This can be done given only the description of the VQCs and does not require running it on quantum computer. We studied in depth the number of samples and its dependence on key aspects of the VQCs (input dimension, encoding Hamiltonians, circuit depth, VQC spectrum, number of training points). On the theoretical side, we conclude that our classical sampling method can approximate VQCs for machine learning tasks on Hamiltonian encoding of classical data, with number of sam- ples that scales favorably but with potentially large constant overheads. Experimentally, we have tested our classical approximators on several use cases, using both artificial and real datasets, and our classical methods were able to match or exceed VQC results. By providing new way of com- paring classical and quantum models, these results may help to understand where the true power of VQCs comes from, and define more rigorously quantum advantage in this context. In particular, it opens up questions about alternative encoding schemes, harnessing the effective expressivity of VQCs, and the link between full expressivity and trainability.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENT
This work was supported by the Engineering and Physical Sciences Research Council (grants EP/T001062/1) and the H2020-FETOPEN Grant PHOQUSING (GA no.: 899544).
REPRODUCIBILITY STATEMENT
We hereby state that the results this paper are reproducible. Theory-wiss the shift-invariance of the quantum kernel is proved in Appendix(B.3 the approximation results for Random Fourier Features are presented and proven in Appendix D and the approximations results for Random Fourier Features in the context of Variational Quantum Circuits presented in the Appendix E For numerical simulations, methods to generate random VQCs are detailed in Appendix (.2 The
code used available the supplementary materials. The anonymous link is also provided here https://osf 1o/ http//yc///22/ /ttp://www...oooo---o8ooaaaaa1a1
REFERENCES
Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, Tobias Haug, Sumner Alperin-Lea, Abhinav Anand, Matthias Degroote, Hermanni Heimonen, Jakob S Kottmann, Tim Menke, et al. Noisy intermediate-scale quantum (nisq) algorithms. arXiv preprint arXiv:2101.0444 2021.
Christopher M Bishop and Nasser M Nasrabadi. Pattern recognition and machine learning, vol- ume 4. Springer, 2006.
Matthias C. Caro, Elies Gil-Fuster, Johannes Jakob Meyer, Jens Eisert, and Ryan Sweke. Encoding- dependent generalization bounds for parametrized quantum circuits. Quanium, 5:582, November 2021. ISSN 2521-327X. doi: 1022333//--02111111-7755 URL https:://od htttp:://doi.zgeee otg/l..........oo
17-
Matthias C Caro, Hsin-Yuna Huang, Marco Cerezo, Kunal Sharma, Andrew Sornborger, Lukasz Cincio, and Patrick J Coles. Generalization in quantum machine learning from few training data. Nature communications, 13(1):1-11, 2022.
Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fu- jii, Jarrod McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, al. Variational quantum algorithms. Nature Reviews Physics, (99:6625644, 2021.
Iris Cong, Soonwon Choi, and Mikhail D Lukin. Quantum convolutional neural networks. Nature Physics, 15112)117331228, 2011.
Casper Gyurik and Vedran Dunjko. On establishing learning separations between classical and quantum machine learning with classical data. arXiv preprini wwXiv:2208.06333 2022.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. The Annals of Statistics, 50(2):949 986, 2022.
Louis-Paul Henry, Slimane Thabet, Constantin Dalyae, and Loic Henriet. Quantum evolution kernel: Machine learning on graphs with programmable arrays of qubits. Physical Review A, 104(3): 032416, 2021.
Martin Hilbert and Priscila López. The world's technological capacity to store, communicate, and compute information. Science, 332(6025))60-63 2011. doi: 10.1 1661s2e//ce 1ttp://ccienn....070000 URL https: wwwp///wwwwww///m//////////.// www.sciiicccc..c org doi
1126/11266// wtt.://ccenceeee 1200970
Hsin-Yuan Huang, Michael Broughton, Masoud Mohseni, Ryan Babbush, Sergio Boixo, Hartmut Neven, and Jarrod R McClean. Power of data in quantum machine learning. Nature communica- tions, 12(1):1-9, 2021.
Iordanis Kerenidis, Jonas Landman, and Natansh Mathur. Classical and quantum algorithms for orthogonal neural networks. arXiv preprint arXiv: arXiv:2106.0777 106.07798, 2021.
10

---

Published as a conference paper at ICLR 2023
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Oleksandr Kyriienko, Annie E Paine, and Vincent E Elfving. Solving nonlinear differential equa- tions with differentiable quantum cireuits. Physical Review A, 10365):05241,, 2021.
Oleksandr Kyriienko, Annie E Paine, and Vincent Elfving. Protocols for trainable and differen- tiable quantum generative modelling. arXiv preprint arXiv:2202.082555 2022.
Martin Larocca, Nathan Ju. Diego Gareía-Martin, Patrick Coles, and Marco Cerezo. Theory of overparametrization quantum neural networks. arXiv preprint arXiv:2109. 2021.
Zhu Li, Jean-Francois Ton, Dino Oglic, and Dino Sejdinovic. Towards a unified analysis of random fourier features. In International conference on machine learning, pp. 3905-3914, PMLR, 2019.
Jin-Guo Liu and Lei Wang. Differentiable learning of quantum circuit born machines. Physical
Review A, 98(6):062324, 2018.
Kouhei Nakaji, Hiroyuki Tezuka, and Naoki Yamamoto. Deterministic and random features for large-scale quantum kernel machine. arXiv preprint arXiv:2209.0195. 2022.
Evan Peters and Maria Schuld. Generalization despite overfitting in quantum machine learning models. arXiv preprint arXiv:2209.05523, 2022.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in Neural Information Processing Systems 20 Proceedings of the 2007 Conference, pp. 1-10, 2009.
Walter Rudin. Fourier analysis on groups. Courier Dover Publications, 2017.
Franz J Schreiber, Jens Eisert, and Johannes Jakob Meyer. Classical surrogates for quantum learning models. arXiv preprint rrXiv:2266.17744 2022.
Maria Schuld. Supervised quantum machine learning models are kernel methods. arXiv preprint arXiv:2101.11020 2021.
Maria Schuld, Ryan Sweke, and Johannes Jakob Meyer. Effect of data encoding on the expressive power of variational
models. Physical Review A, 103(3):1-16, 2021. ISSN 24699934. doi: 10. 101./PhyssReeA..00....4..
Shin, YS Teo, and H Jeong. Exponential data encoding for quantum supervised learning. arXiv preprint arXiv:2206.122 12105, 2022.
Danica Sutherland and Jeff Schneider. On the error of random fourier features. arXiv preprint 106.07150. 2015.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmark- ing machine learning algorithms. arXiv preprint urXiv:/708.077 2017.
Hayata Yamasaki, Sathyawagecswar Subramanian, Sho Sonoda, and Masato Koashi. Learning with optimized random features: Exponential speedup by quantum machine learning without spar- sity and low-rank assumptions. Advances in Neural Information Processing Systems, 33:13674 13687, 2020.
Christa Zoufal, Aurélien Lucchi, and Stefan Woerner. Variational quantum boltzmann machines. Quantum Machine Intelligence, 3(1):1-15, 2021.
11

---

Published as a conference paper at ICLR 2023
CODE AVAILABILITY
All the code that was used in this project available following the anonymous link https:// osf wtt.bo/k///////// ?view wttp://0000000000000000047111111
A RELATED WORK
recent work Schreiber et (022)) independently proposed a similar approach where classical surrogate methods approximate VQCs. The difference with this work is the necessity of having access all 2 the totality of the frequencies of the VQC considered, without sampling from them.
Indeed, if Ω is known, the coefficients aw and bw of the VQC function (see Eq(IO) can be easily fitted by solving the classical least square problem. Namely, one determines w such that
M
w arg min
Σ
Ww T ((x;)))))))))))))))))) - yil2 + Au A||
(2)
M
cos (war)
where (xx)
and An is the regularisation parameter. As explained in the previous WER
sin(wuz)
Section, with a dataset of M points, this can be solved exactly using matrix inversion in O(M [2]2++ + (021") operations if M 2 2/52/. If the inequality is not fulfilled or if [S) is too big, one would use stochastic gradient descent instead of matrix inversion.
However, this method assumes that Q and is not too large, which will usually be the case as we shown in section B.2 One should also be able to enumerate all individual frequencies Q. Moreover, as we will show the redundancy of some frequencies in Q has key importance, which is not captured by such a method.
For completeness, we note from the seminal work Schuld 2021 that the author briefly mentions the idea of approximating kernels with RFF. Similarly, in the recent work Peters & Schuld (2022), the authors mention RFF sampling strategy VQCs with shift invariant kernels, without further details. In Gyurik & Dunjko (2022). the authors mention briefly that VQCs with polynomially large Fourier series can be learned from polynomial number of training points, but this method remain unclear for exponentially large Fourier series.
We also note that other works (Yamasaki et al. (020): Nakaji al. (2022) make use of random features, for or from quantum circuits, but are less related to our approach.
B PRELIMINARIES ON VARIATIONAL. QUANTUM CIRCUIT FOR MACHINE LEARNING
B.1 DEFINITIONS
We provide here a definition of VQCs that is used in this work. Many more models in the quantum machine learning litterature such as quantum circuit born machines (Liu & Wang 2018). variational imaginary time evolution (Zoufal et al. 2021), differentiable quantum circuits (Kyrienno et al., 2021), quantum evolution kernel (Henry et al. (02T), quantum orthogonal neural networks (Kereni- dis et al. 2021), to cite only few, are also variational but we don't 't consider them here. It is an open question to extend our findings to such models.
We consider a standard MI task where function f. named model, must be optimized to map data points to their target values. The data used the training is made M points = (.I,..., x.)) in X' = dd along with their target values y in y R. We define a quantum model as the family of parametrized functions f (X, θ) - y, such that
f(x; 0) (z) O)U
where U(x; 0) is unitary that represents the parametrized quantum circuits, 0 represents the train- able parameters from space O and O is observable. The parameterized quantum circuit is
12

---

Published as a conference paper at ICLR 2023
composed of layers of alternating embedding and trainable unitaries. Embedding unitaries depend on input data values whereas trainable unitaries depend on internal parameters that are optimized during training. A typical instance of VQC is illustrated in Figure Note that actual layer structure not mandatory. since any circuit can be sliced into alternating sequences of encoding and training blocks (even if containing single gate).
Any quantum unitary implements the evolution of a quantum system under a Hamiltonian. Thus, choose write the 8th encoding gates as exp(-ix; Hy), where æ; is one of the d components of v, and H2 is a Hamiltonian matrix of size 2 if p is the number of qubits this gates acts on. We will note the number of encoding gates for each dimension of (the same for each dimension, for notation simplicity).
In this framework, the aim is to find the optimal mapping between data points and their target values. This is done by optimizing the parameters 0 to find the best guess f" such that
M Σ
f = arg min M
().
where 1 is a cost function adapted to the task. For standard regression tasks, we can choose ((z, y) 1z 2/²
B.2 QUANTUM MODELS ARE LARGE FOURIER SERIES
We know since Schuld et al. (2021) that the family of quantum models defined in Eq.3) can be rewritten as a Fourier series:
[a;;
Σ Cue
(5)
WEB
where the spectrum Ω of frequencies is determined by the ensemble of eigenvalues of the encoding Hamiltonians and the coefficients cu depend on the parametrized ansatz, as pictured in Figure
In order to familiarize the reader with the structure of the spectrum, we explicitly build in the case of a one dimensional data input (X' IR) and with variational circuit containing only L encoding gates. The accessible frequency spectrum It is the ensemble of the differences between all possible sums of the eigenvalues of the encoding gates as shown in Figure 2
We note X the 1:th eigenvalue of the gth encoding Hamiltonian Hy. We use the multi-index i (i....., iz) indicating which eigenvalue is taken from each encoding Hamiltonian. We define A, as
A;
Finally, we can express the set of frequencies as:
= As - A,,2,J A, [N70]
Proof. We consider g(t++) (=)))) as described in B. where ( are N-dimensional unitaries dependant on the trainable parameters 0 and 8()) are N-dimensional encoding unitaries of the form 5(t) diag(e iin) ,..., iimxf" where Ais are eigenvalues of the underlying encoding Hamiltonian H, (without loss of generality).
circuit unitary of the following form U(x;
We start by applying the first layer on the (0) computational basis state and we iterate through the remaining layers to obtain [ı; 0)) U( 0) 10).
13

---

Published as a conference paper at ICLR 2023
N Σ
(1)
w
e e lí1)
jil
==
NV Σ
(ass (2))
Σ
W (2) e -to( -2/2) li2)
fzn 111
w(l-1) II (0 (z)
Σ
E
Wii
(L+1))
kiz
...W( -izdy [K)
k=1jE|M
The full quantum model will consequently have the form of a truncated Fourier series: (2; 0)
(x; O)T 0)
N Σ ΣEΣΣ
Σ
(w Was.
-itlAy ...W!) (11) (W(l++)) ... ...( j
... 211
W W= W k=
Σ
Cj.iie - (gg))
Σ WEE
oue wwe-in -izw izw
In this proof, we considered encoding unitaries of size N = 2n with n the number of qubits. However, we note that, without loss of generality, we can use encoding gates applied only on subsets of the n qubits and consider the eigenvalues of the global resulting hamiltonian which are no different than the ones of the local hamiltonian with some redundancies.
The simplest case is called Pauli encoding, when all encoding Hamiltonians are in fact Pauli matrices (e.g. encoding gates Rz = e e-$202) ) as Schuld et al. (2021); Caro et al. 2021 }. In this case, all the eigenvalues are +1 12, and therefore, the Ag are integers (or half-integers, [-L/2, L/2], It follows that the set of distinct values in f2 is simply the set of integers in [-L, L1- Indeed, in this case, there are many redundant frequencies, due to the fact that all Pauli cigenvalues the same. As shown in Figure 2 various eigenvalues would create more distinct frequencies in the end. In the rest of the paper, 12 will denote the set of unique frequencies, without redundancy.
odd) in
Note that in Section 4 we observe unexpected phenomenon: it seems that redundant frequencies are likely to have high coefficients (for both random and trained VQCs). Unique frequencies might often have in contrast small coefficients, reducing the potential expressivity of the VQC. We that the redundancy might therefore play an important role in the expressivity of VQCs, and leave theoretical proof for future work. In fact, the impact of the frequencies redundancy on the quantum model has been recently highlighted in PPtees & Schuld (2022) where an analytical correspondence between frequency redundancy and its Fourier coefficient has been proven for simplified class of parameterized quantum models.
These arguments give some intuition on why one should use encoding gates from Hamiltonians with rich and various eigenvalues, by taking complex interactions over many qubits. A global Hamilto- nian over n qubits, hard to implement, could potentially have 2n distinct eigenvalues, thus enlarging Ω and avoid redundancy. Another approach from Kyrüenko et al. (2022); (Shin et al. (2022) consists in adding scaling factors in the Pauli encoding gate to modify their cigenvalues and avoid redun- dancy. It results in exponential number of integer frequencies, with respect L, with many very high frequencies.
We can now generalize, if we now suppose that X' Rd, such that encode a vector (z)..... 22) in our quantum model, then becomes the following d didimensional Cartesian prod- uct Ω = 2 Ω2 x x Oa where each Ω, is defined as in Eq on its own set of Hamiltonians.
14

---

Published as a conference paper at ICLR 2023
vectors in R and there d different trees to build Ω (see Figure 2). Note that for notation simplicity, we assumed that L gates were applied on each input's component, but it can be generalized to any number of gates per dimension.
In this context, note that the frequencies
We therefore see that the size of the spectrum [S2] can potentially grow exponentially with the number of encoding gates and the dimension of the input data. For instance, consider d-dimensional vector x and L Pauli-encoding gates for each dimension in such a way that there are Ld encoding gates in the VQC. The size of the spectrum Ω would scale as O(L)), which becomes quickly intractable as d increases.
As example, the spectrum associated VQC with 20 encoding gates and d 16 would require more than one hundred times the world's storage data capacity available in 2007 to be stored (Hilbert & López (201T)). We therefore wonder if it is possible to build classical approximator e such that Ω is of tractable size and supzex [[(()) f(x) S.
f(x)
WE
B.3 QUANTUM MODELS ARE SHIFT-INVARINT KERNEL METHODS
As the quantum model is a real-valued function, follows that w E Q implies -w S2 and Cw c_ We express the Fourier series of the quantum model as a sum of trigonometric functions by defining for every w E Q::
a C C-w E
1
bw = (ew C-w) E
(9)
such that
f(r;0)
E
wwee c-we twz
WER
(10)
Σ WEn
au cos(wrr) + bo sin(wa)
where Ω2 contains only half of the frequencies from f2. Considering only Pauli matrices, if d 1, we simply have Ω =2=10 -- L] and Ω2 = [[0, ZJ. In dimension d, we have Ω = I-I, L] and Ω2 is built by keeping half of the frequencies (after removing those of opposite sign), plus the null vector. In the end, we have
12 (2L 1)a
(11)
2
With more general encoding scheme, there a different number of distinct positive frequencies per dimension, the formula is different but is built similarly.
In the following parts, we will focus solely on Q4 and conveniently drop the + subscript.
Given this formulation of the quantum model, we define the feature map of the quantum model as
f(: 8) (a; ())0 0)) w(f)" o(x)
(12)
where (xx) is the feature vector, the mapping of the initial input into a larger feature space, where the new distribution of the data is supposed to make the classification (or regression) solvable with only a linear model. This linear model is in fact the inner product between o(x) and a trainable weight vector In the case of VQCs, we explicitly express them
cos(wTx) x)) sin (an(wF))
a
1
b
(xx)=
w(0)
(13)
Vi
WEl
WED
15

---

Published as a conference paper at ICLR 2023
If the spectrum Ω is known and accessible, efficients awy by associated to each frequency w. This can be done by using general linear ridge regression techniques. Interestingly, there exists dual formulation of the linear ridge regression that depends entirely on the kernel function associated to the model (Bishop & Nasrabadi (2006). The related kemee function is defined by:
fit the quantum model by retrieving the
b(z,x') (0(x), o(x'))
1
cos(war) cos(war') + sin(wa) sin (inw"'')
(14)
cos(w( x²))
which is shift-invariant kernel, meaning that k<x,, 2") k( - x').
is known that quantum models from VQCs are equivalent to kernel methods (Schuld (2021) ),
which means that it is equally possible to fit the quantum model by approximating the related kernel function. These kernels are high dimensional (since the frequencies in S2 can be numerous) which makes it hard to simulate classically in practice. But due their shift-invariance, we propose to study their classical approximation using Random Fourier Features (RFF), a seminal method known to be powerful approximator of high-dimensional kernels (Rahimi & Recht 2009)).
C DEFINITIONS OF LINEAR RIDGE REGRESSION (LRR) AND KERNEL RIDGE REGRESSION (KRR)
We present in this Section the Linear Ridge Regression (LRR) and Kernel Ridge Regression (KRR) problem (Bishop & Nasrabadi (2006). The problem of regression is predict continuous label values from feature vectors. We are given a dataset (I yi), E [1, M MI E IE E R), and each data point x associated feature vector (xx) RP. The goal of LRR is construct parameterized model f such that f(x) = y. The model is parameterized by weight vector w of size p such that (x; w ó(x). Training the model consists of finding the vector ws that minimizes the loss function
w arg argmin min
w (b(a)))) 2112 + \\|w||/
(15)
M
w
arg min
[ww - y/l² + A1/
(16)
M
(17)
where is a matrix of size M p with each row i corresponds o(x;)² and y is the vector of all the labels The first term of the loss is the Mean Square Error (MSE) and corresponds to the difference between the prediction and the ground truth. The second term is the ridge regularization, and prevents the weights from exploding. The magnitude of the regularization is controlled by the hyperparameter 0.
When p < M, an analytic solution to this problem is given by w (Φ + + -AI,)-
make the LRR possible and have single solution, the number of training points must be larger than the number of features in the feature space (o(x)). Otherwise, one can perform a gradient descent.
As a consequence,
The dual formulation of this problem is given by expressing w linear combination of the data points = T a. The minimization on w become a minimization on a and can be expressed as
x = arg min
+ T a u112 + Xa T a M
(18)
(19)
The solution of this problem is ( -MTM))
16

---

Published as a conference paper at ICLR 2023
Note that the dual solution only depends the matrix of scalar products between feature vectors Φ One can then replace this matrix by a kernel matrix K and the obtained model is a Kernel Ridge Regression.
D APPROXIMATION RESULTS FOR RANDOM FOURIER FEATURES
We give here two useful results about the bounds of the error of the RFF method. RFFs are supposed approximate a certain kernel by using fewer features. Intuitively, not enough features would lead to imprecise solutions. The following theorems (Rahimi & Recht (2009); [Sutherland & Schneider 20155) bounds the error obtained when comparing the kernel 2(r, y) by the RFF approximator (x)) ((V) using D samples.
We recall that the condition on the kernel is for be expressed as
(0)) / p(w)e i dw
(20)
Jwex
where p(w) is the distribution of the frequencies w.
Theorem 2. Let X' be a compact set of and > 0.
P( sup [k(z - y) =(x) ((()) 2 5
a.yEN
(21)
ppl Peopl- x 4(d
De2
66(
with o2 = =EplwF ) the variance of the frequencies' distribution, and |X| = max mx the diameter of X.
r'l)
The following theorem (Sutherland & Schneider (005)) bounds the actual prediction error when using RFF compared the KRR estimate. The formula in the original reference contains sign error and we correct it here.
ofR, Theorem 3. Let X be compact set of Rd, and O. We consider training set {(rss y. Let I be the KRR model obtained with the true kernel k and regularization = M Ao for Do > 0, and f the KRR model obtained with the approximate kernel and the same regularization. Then we can guarantee [f(x) f(x)) S with probability 1 - 5 for number D of samples given by:
D D= 2 a( (Ao 1)o 1)0
)
(No + +1)oo, A
logō
+ log
(22)
ABC
with o
Mi E v/ and op, |x| being defined in theorem
2
We recall that 22 the notation
Ω stands for the computational complexity "Big-Q2" notation.
E APPROXIMATION RESULTS FOR RFF IN THE CONTEXT OF VQCs
E. DISTINCT SAMPLING IN THE PAULI ENCODING CASE
In the case of Pauli encoding only, we know that Ω [-L. d (considered here be the full spectrum, not Ω defined in Section B.3 which would have been equivalent). In one dimension, we simply have o D/- L....." =O(?)) dimension d, a frequency w given by its values on each dimension (jr, .J)) with ja - L, L1]. We similarly have
op (2L + 1)d dis
Σ , + + -
(23)
Note that En + ... j is d(2L + 1)d-1
times the sum of all squares,
d(2L + 1
L
d 2L(L + 1)(21 +1)
Op (2L 1Id
2L +1
(24)
ビ=- I
O(dL3) =((1))=0(())))///
17

---

Published as a conference paper at ICLR 2023
The expression is then obtained by replacing the value of op in theorem
We note that we can generalize this results to scaled Pauli encoding, as done in Kyrüenko et al. 2022;; ; Shin et al. 22022), by replacing L by term growing as c where is constant. D would grow linearly in L and not logarithmically anymore.
E.2 GRID SAMPLING WITH A GENERAL HAMILTONIAN
We provide here bound on the minimum of samples required to achieve certain error between the RFF model and the complete model in the case a general encoding in the gird sampling strategy. The proof and details for this theorem is shown in Appendix Section F.2
Theorem 4. Let X be a compact set of RR, and >> O. We consider a training set {( yi) Wi) Let be VQC model with any hamiltonian encoding, with maximum individual frequency wmax and full freedom on the associated frequency coefficients, trained with a regularization X. Let of = M Ei= vi and [X] the diameter of X. Let I be the RFF model with D samples the grid strategy trained on the same dataset and the same regularization. Let C = |fl co [X] and the sampling rate
defined in the grid sampling strategy. Then can guarantee (f f(z)) S cfor < <s< <
with probability 1 - 5 for a number D of samples given by:
dC1
C2
D= Ω 1+(c-scy' [og( + log (Cc-CC)
logg
(25)
with C₁ and C2 being constants depending on By d(X). We recall that in 25 the notation Ω stands for the computational complexity "Big-S?" notation.
Proof. The following theorem bounds the approximation between function defined by its Fourier series and another function with frequencies distant by at most a constant s of the original frequen- cies.
Let X a compact set of Rd with diameter | and Ω a finite subset of X. Let f(x) Σ cos(ssw" 2) + bwsin(w" z). Let O' subset of X and such that Va e Ω Ee WEN
P2 IW -wll S.
Let Fay = Σ
cos(ww x)) + busin(wfar) x.), aw bw E R
WESV'
Theorem 5, It exists f' E Far such that
sup #ex
(f'(z) - f(x)] S sO
(26)
with C = |X
Proof. For each w E Ω let b(w) E 92 be such that - -(ww) S 8. Such element exists by definition
but is not necessarily unique. Let ['(x) Σ (bwl)) x)) + b (in()(((
x:) The b(w)s are
WER
not necessarily different therefore there might be less frequencies in f than in f.
(w b(w)) x))
-()))f((x)) = Σ
sin
(27)
2
wEn
sisin (w + blw))
(w + b(w)) x)
4) - cos(
(28)
2
2
(w b(w)))
2
| +lawll
(29)
2
WER
< 5|/0|
|bwl + lawl
(30)
WER
< s) s|
(31)
18

---

Published as a conference paper at ICLR 2023
We shall here extend the proof where we sample from the grid described above. Let us note fa the RFF model with the whole grid and f the RFF model with D samples from the grid below. For all X we have
(f(z) - [(x) s 1f(x) - f - s(a)
(32)
CC
(33)
Then
-(1(())f((z) 2 d) = P()(()) falc-
(34)
for 8 < E/C.
In this case [92| (Wmnx//8) /8) Using the expression of Section E.1 f(x) S with probability 6 6 if
we can guarantee that [f(x))
D = d
(" (E- =0}3 [cp3
log(wmax/s) + log-- 5C
logò
(35)
F LIMITATIONS OF RFF FOR APPROXIMATING VQCS
In Section we have seen the theoretical power of Random Fourier Features and three different adaptations to approximate VQCs in practice. Since many parameters are to be taken into account (size and structure of Ωt number of qubits, circuit depth, number training points, input dimen- sion, encoding Hamiltonians, etc.), it is natural to ask ourselves in which of the three strategy is recommended given a use case, and are there any use cases for which none of them work.
As seen in Section 3.4, know the lower bound on the number of samples to draw in RFF, to reach a specific error. This bound grows linearly with the input dimension d, and logarithmically with could very
L Nonetheless, in practice, large spectrum to be harder to approximate, simply because would require much more samples. This scaling will be judged once such VQCs will be actually implemented large enough quantum computers (with enough qubits and/or long coherence).
the size of 52 (itself depending exponentially
Ω increases well when the encoding Hamiltonians have distinct eigenvalues and are acting on many qubits. Therefore, quantum computers allowing for many qubits and various high locality Hamiltonians would be a plus for enlarging the spectrum.
As the Hamiltonians become larger we could reach a limit where it becomes impossible to diago- nalize them. In such a case, without sampling access to Ω, the Distinct and Tree sampling strategies would be unavailable. The Grid sampling scheme would suffice until suffering from the high di- mensionality or other factors detailed above.
Finally, having small dataset would limit the trainability of our classical RFF methods. Note that this would probably constrain the training of the VQC as well.
Overall, some limits for our classical methods can be guessed and observed already, but the main ones remain to be measured on real and larger scale quantum computers. We leave this research for future work. On another hand, one could want to understand better the relation between the available frequencies and their amplitude in practice, to find potential singularities that could help, or not, the VQCs.
Finally, we want to insist on the fact that the assumptions on VQCs are crucial on the whole con- struction that we propose, and that some of them could be questioned, especially concerning the encoding. For instance, when encoding vectors x = (#1. Ia). not having encoding gates ex- pressed as exp(-x,,H) could potentially change the expression of fx; 0) (Eq and therefore could change the fact that the associated kernel would be casily expressed as a Fourier series, with shift- invariance. For instance, in Kyriienko et al. (002), the authors exp( arcsin(x;) H) to encode
19

---

Published as a conference paper at ICLR 2023
data, resulting in f being expressed in the Chebyshev basis instead of the Fourier one. More gener- ally, understanding what happens with encodings the form exp((g(z;)))) and whether we can still use classical approximation methods, remain open question. Similar questions arise if we use simultaneous components encoding exp( (pp(-1,1,. H), or other alternative schemes.
G NUMERICAL SIMULATIONS: ADDITIONAL DETAILS
G.1 METHODS AND DEFINITIONS
As shown in Figure 6 a typical random VQC instance is built from a list of general encoding Hamiltonians 1 H& applied to randomly selected qubits according to their locality. The number qubits fixed to 5 in all the experiments (Note that the number qubits has no impact on the expressivity priori).
U1
U/
U/
PF (1))
Figure 6: Random instance of VQC. In this example, three encoding Hamiltonians (H, H2, H3) randomly assigned over four qubits, and load I-dimensional vector Following each encoding gate H;, an ansatz with trainable parameters and a ladder of CNOTs is applied, 4, times in row.
G.2 RFFS APPROXIMATION ON OTHER TYPES RANDOM VQCs
We introduce this Section by adding some details on the experimental framework described in Sec- tion 4.1, The random VQCs follow the structure shown Figure The training dataset we is {X grid, (grid), with X grid being set of d-dimensional data points spaced uniformly on the interval IT_ [m,zz and Y grrid the evaluation of the quantum circuit on the input dataset X Xgrid-
We note that the number of data points in X Xyrid needed to efficiently learn the quantum function
N > [[ Zioas (mmoz This choice is basically related the Shannon criterion for effective sampling in order to reconstruct the full function covering all of its frequencies. Moreover, it is better for the solution be unique and hence for the least square problem introduced in Eq to be well defined, we choose N to be bigger than the number of features in the regression problem (these two criteria coincide in the case Pauli encoding).
Sf
G.2.1 PAULI ENCODING
We first consider a quantum model with Pauli encoding gates per feature resulting in an integer- frequency spectrum (half of II| L L]]d). In this case, the corresponding quantum model is periodic function of period T (2x)d and thus, we choose Xmaz = 2T for Xgrid construction.
In Figure 7 we implement VQCs with I-=200 Pauli encoding gates, for 1-dimensional input. We observe that our classical approximation methods are indeed able to reproduce such VQCs. average, the RFF training eπror for Distinct and Grid sampling is a linear function of the number D of samples taken from Ω2 On the other hand, the error using Tree sampling exhibits a faster decreasing trend, reaching relatively low errors with only 20% of the spectrum size. Indeed, the redundancy of Pauli encoding is extremely high, since with = 200 gates, Ω can potentially have 220 frequency, but only have 200 distinct ones, concentrated in the lower part.
We conjecture that the efficiency of Tree sampling is closely related to the redundancy in the discrete frequency distribution over Ω. In fact, shown in Figure Fourier coefficients of the VQC are,
20

---

Published as a conference paper at ICLR 2023
average, correlated to the frequency redundancy in the empirical quantum spectrum. Frequencies above certain threshold Wettective are merely redundant for this particular encoding scheme, and we observe that they are cut from the quantum model empirical spectrum. The effective spectrum of the VQC is therefore smaller than what the theory predicts. Consequently, the fast decreasing trend of the Tree sampling stems from the fact that sample accordingly the redundancy, therefore quiring less frequency samples. We see that 0.2 x [2] samples are sufficient to sample approximately all frequencies in [[O, weffectivel.
Fourier conficients
1500
Theoretical frequencies
Empirical frequencies
Train loss value (MSC)
0.125
Distinct sampling
sampling
1000
Redundancy
0.100
Grid sampling 5=0.1
5000
0.075
2500
0.050
0.025
50
100
0.000
20
40
60
80
100
0.3
0.2
0.4 0.6
0.8 1.0
Frequencies
Number of sampled frequencies (fraction of [R])
(a) Average Fourier Transform of the VQC's quan- tum models. The frequencies with high coefficients are the ones with high redundancy in 12 (seen in the inner red histogram). Frequencies over 100 have negligible coefficients and redundancy, and there- fore are not shown.
(b) Evolution of RFF train loss function of the relative number of frequencies sampled. The Tree sampling strategy takes advantage of the high redun- dancy to sample less frequencies to reach good ap- proximation.
Figure 7: Random 1d VQCs with l.=200 Pauli encoding gates, averaged over 10 different random initialization.
In Figure we show similar simulations with d-dimensional input (d 4) and L. 5 Pauli gates per dimension. According to Eq. (T). the theoretical number of distinct positive frequencies is 7321. In this case in the tree sampling procedure, without removing one of them. Therefore the scheme is a bit less performant than in dimension 1.
sample both frequency and its opposite
Train loss value (MSE)
0.15
Distinct sampling
Tree sampling
Grid sampling 5-0.11
0.10
0.05-
0.00
0.0
0.2
0.4
0.6
0.8
1.0
Number of samples (fraction of (Q])
Figure 8: RFF performance for L. 5, d 4, to approximate random VQCs with Pauli encoding.
G.2.2 MORE COMPLEX HAMILTONIAN ENCODINGS
For Pauli encoding, we have seen that Tree sampling is highly effective for approximating the quan- tum model. Consequently, we designed VQCs with different spectrum distributions to study the RFF approximation performance in these cases.
As explained in Section we consider encoding gates of the form exp(-iz;H) for each dimen- sion i. One way to alter the spectrum distribution is the use of more general Hamiltonians H. To obtain exotic Hamiltonians while maintaining their physical feasibility (involving only two-bodies interactions), we use the generic expression
HXYZ =
Σ (1.)
ogj oayxX X,X, + B,y + 2, + Σ 6
(36)
with the first term describing the interactions: (i. indicates a pair of connected particles and the second term describing single particle's 's energy (P; (X,, Y, 7:)).
21

---

Published as a conference paper at ICLR 2023
1250
Fourrier coefficients
Theoretical frequencies
Train loss value (MSE)
1000
Empirical frequencies
Distinct sampling
750
Tree sampling
500
Grid sampling s=0.1
0.C5
0
0.00
20
80
100
0.0
0.2
0.4
0.6
0.8
1.0
Frequencies
Number of sampled Tequencess (fraction of (a]]
(a) Fourier transform averaged over different dom initialization of the VQC. The intensity the vertical red lines indicates concentration the theoretical frequencies in f2.
(b) RFF train loss with different sampling methods the random VQCs. The Distinet sampling benefit
from the concentration of frequencies packets to approximate with less samples.
Figure 9: Random 1d VQCs with 4 scaled Paulis and and 3-qubits Hxyz Hamiltonian
In Figure we construct VQCs mixing both such Hamiltoniang] and scaled Paul 2 as encoding gates, on T-dimensional inputs. In these cases, the corresponding quantum model is no longer 2x-periodic, thus we have to find empirically a good value for Imaa (by increasing it until the performance reaches limit).
With such complex encoding, we witness a different behavior for the Distinet sampling method, in comparison the previous basic Pauli encoding scenario. Essentially, Distinct sampling has a faster than linear scaling, showing a clear and unexpected efficiency of RFFs in this case. We also notice that the Tree sampling method that, with the chosen encoding strategies, the frequencies in the spectrum S are concentrated in many packets or groups. This behavior displayed with the concentrated red lines in Figure (545 distinct frequencies out of 8 8192). Therefore, sampling just one of the many frequencies in narrow packet enough for the RFF to approximate all. put differently, we can consider that there is Retfeetive where each packet can be replaced by its main frequency, and the RFF manage to approximate it with fewer samples than the actual size of Q2 To conclude, many distinct frequencies not a guarantee of high expressivity.
similar scaling. This observation points the fact
As for Grid sampling, the choice seemed too high for this solution to work in this case, in line with the theoretical bounds for this sampling method given in Theorem I
G.2.3 EXPONENTIAL PAULI ENCODING
In order to obtain VQCs with large number of frequencies, but low redundancy and concen- trated packets, we exploit the exponential encoding scheme proposed in Shhn et al.] (2022), resulting in non degenerate quantum spectrum with 3Ld distinct frequencies which is the maximal number of distinct frequencies we can get with two eigenvalues of opposing sign for each encoding Hamil- tonian and thus an approximately uniform probability distribution over integers. In this encoding strategy, encoding Pauli gates are enhanced with scaling coefficient S&r for the 1 Pauli rotation gate encoding the component Ty. This gives These frequencies can be all distinct with the particular choice of 3. = 3'-1, resulting in an expo- nentially large and uniform 12. Note however that is analytically known and contain only integer frequency, mostly very high frequencies for which the usefulness in practice remain to be studied.
total of 3Ld positive and negative frequencies.
We have tested our classical RFF approximation, shown in Figure 10 and obtain again the confir- mation that RFF can approximate such exponential feature space with a fraction of [?]. This fraction might however be too large in practice. We also observe as expected that all three strategies have a linear scaling, in line with the absence of redundancy and frequency packets.
'n Figure 9 we used 3-qubits Hamiltonian defined by: HxYz = 7X,X, + 7X,X, +0.11X,,2 0.1 X2 Xo + 8TT.s Y2 - Y2Yi + Zo 22 + Za 7n) "Scaling factors (26.4309, 34.4309, 22.4309. 0.4309)
22

---

Published as a conference paper at ICLR 2023
Fourrier coefiicients
Empirical frequencies
Distinct sampling
Theoretical frequencies
0.125
Tree sampling
0 030
sampling sm0.1
100
Train loss
030
50
0.025
20
40
60
100
120
0.0
0.8
Freq Jencies
Number of sampled frequencies (fraction of IaD
(a) Fourier transform averaged over different ran- dom initializations of the exponential encoding VQC with I. 5.
(b) RFF approximation performance of ponential encoding VQC with
ex-
Figure 10: Random VQCs with exponentially large Spectrum, using L. scaled Pauli encoding as in Shin et al. (022) resulting in Wmar 121.
G.3 ARTIFICIAL TARGET FUNCTION
We add here the training curve obtained during the training of the VQC with T, 200 Pauli encoding gates, on the artificial function sax) (4,(4,10.00) cos(wrx) + sin(wx). Despite the potential large number of frequencies available in S2, have observed that the effective maximal frequency of the VQC was lower than 60, making it impossible for it to fit the high frequency of the target function.
TiX)
0-
{RFF_80%
VQC
target
0.0
0.2
0.4
0.6
0.8
1.0
Figure 11:
Predictions of the target function s(x) Ewe(t (0,10000 10,603 cos(wa) + sin(wx) with the quantum model and its corresponding RFF classical approximator using Distinct sampling.
G.4 REAL DATASETS
For the binary classification task, we used the PyTorch Fashion MNIST dataset with the classes coat and dress (3 and 4). We divided the 12000 input data points into train and test datasets with Ntrain = 9600 and Ntest = 2400. For the pre-processing, we downscaled the input dataset by first rescaling the flattened input images between 0 and I and subtracting the mean then performing a d = 5 PCA transformation fitted on the train data and applied on the test data. Finally, the 5- dimensional input vectors are rescaled between - and æ. The final VQC predictions after 60 epochs using Adam optimizer with learning rate = 0.01. For Tree sampling RFF training, for each fixed number of sampled frequencies p. we perform the regression on the corresponding fourier features using PyTorch logistic regression model (linear layer + sigmoid layer, loss binary cross entropy with logits, metric accuracy) trained for 2000 epochs with early stopping using Adam optimizer with learning rate 0.05. The final accuracy for the fixed number of samples is the average score over 10 different such trained models with different random seeds for frequency sampling.
obtained
For the regression task, we used the Scikir-learn California housing dataset and kept only the first 5 features. We chose Ntrain 5000 and Niest 1000 and we scaled the 5-dimensional dataset between -π and æ. The final VQC predictions are obtained after 100 epochs using Adam optimizer with learning rate 0.01. For Tree sampling RFF training, the same steps as in the case of the Fash-
23

---

Published as a conference paper at ICLR 2023
ion MNIST dataset performed with PyTorch regression model (linear layer, loss and metric: mean squared error).
G.5 NUMBER OF SAMPLES AND SIZE OF Q
30.50
10'
Number of samples
36.00
d-4
20
d:6
22.50
d-7
10f
d-10
25.00
d-20
10'
10
10
10
28.55
(0g
(a) Experimental bounds for different values L, (b) Theoretical bound for different values L,,
Figure 12: Evolution of D as a function of input dimension d and of L encoding gates per di- mension, and theoretical bounds. In agreement with the theoretical bound, the number of samples D given fraction of [2] decreases with the growth of the data input dimension and the number of encoding gates.
In this Section, [0, L.Il. a Fourier series model trained on a specific dataset, the theorem bounds the necessary number of samples for RFF model to approximate the original model with error. This is an approximation to the Pauli encoding VQCs where the spectrum is l = [-L, LI For fixed values of d, and a spectrum f [0, LJ we implement the following protocol test this bound:
the theoretical bound provided by the theorem Given spectrum Ω
Generate dataset of 10s points sampled uniformly from [0, 1]d and labels coming from Fourier series Ω with coefficients chosen uniformly from [0, 1/V[D]] Split in train set and a test set with respective fractions .9 and .1.
For each value D in {1, k Ω /10 for l E [1. 10]}. sample D frequencies from with- out replacement, and train linear ridge regression with À 10 the train set. We performed the training with a Adam optimizer, a learning rate _001, and between 50 and 200 epochs depending teh size of the dataset. Compute the output the test set.
Compute the mean absolute frequencies and the output of all other model. Select the model with the lowest number of samples that has error below
between the output of the trained model with all the
The results of the application of this protocol are shown Figure 12 For the values of [ between 10 and 106, one can see a significant reduction to the number of samples needed to approximate the whole model. For .05, one can expect to need only half of the spectrum, whereas for .5. one only need about 10% of the spectrum. The trend does not continue above |S 10?.
There are several limitations to this experiment. The main one is the limited training of the models. For the biggest values of [S2] we limit ourselves to 50 epochs, which may be not enough to reach the optimal parameters, and thus blur the interpretation. Furthermore although the theorem is valid for every number data points, the overparameterized regime where there are much more parameters than data points is known exhibit unusual effects in linear regression (Hastie et al. 2022).
Given the choices of and c, the theoretical bounds are very high for the regimes we experimentally tested, so they not relevant. The effect that is quantified by the theory appears from [ 10 e.g one need approximately D = 1030 samples to approximate 10 frequency spectrum. That is still unfeasible on classical computer, only standard benchmarks will state the usefulness of the RFF methods.
24


Reviews:
[{"review_id": "GkdEZaxA7e", "reviewer": "Reviewer_tPCQ", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper provides a classical method of approximating VQCs by sampling random frequencies from the VQC as a Fourier series. By showing that VQCs can be efficiently approximated using less than the order of exponential samplings, the work points out the potential problems with quantum advantages of VQCs. ", "summary_of_the_review": "A good study on approximating VQCs is presented with clear numerical evidence. The results are very interesting, pointing to potential flaws of VQCs which should be further studied in future works. ", "strength_and_weaknesses": "Very good theoretical derivations and experimental results. The results are well presented and extensive, covering both artificial and real datasets. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "9gJMbXoYeLa", "reviewer": "Reviewer_WzGu", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Variational quantum circuits constitute a main class of quantum algorithm on current noisy, intermediate scale quantum devices (NISQ). This paper studies approximating the result of VQCs by classical algorithms. Specifically, for VQCs with Hamiltonian encoding, this paper demonstrates how to use random Fourier features (RFF) to sample a few frequencies, build an equivalent low-dimensional kernel, and then solve by linear ridge regression (LRR) and kernel ridge regression (KRR).", "summary_of_the_review": "In summary, I think the topic of this paper on classical simulation of near-term quantum computing is interesting, and the authors are also able to provide some theoretical and experimental results to justify their result. Nevertheless, from my perspective, there is notable issue with the efficiency of the proposed classical algorithm, technical contribution compared to prior arts, and the paper has space to improve in overall presentations and writings.", "strength_and_weaknesses": "From my perspective, the topic of simulating quantum computing by classical computing is in general interesting. In particular, considering that quantum computing devices will stay at the status of NISQ for a while, research about whether they can be simulated by classical devices are in general interesting. This submission to ICLR 2023 falls into this category, and it provides both theoretical and experimental results. In addition, the codes are open-source with an anonymous package provided.\n\nNevertheless, after reading through the paper, I have concerns from a few aspects:\n\n1. First and foremost, I’m not sure if this paper provides enough evidence for simulating VQCs on classical computers efficiently in general. In particular, I’m worried about both Algorithm 1 and Algorithm 2, RFF with distinct sampling and RFF with tree sampling. They both diagonalize the Hamiltonians of the VQC’s encoding gates, but I don’t think it is doable in general – the Hamiltonian matrix scales exponentially with the number of qubits, i.e., a VQC on 50 qubits will in general have Hamiltonians of dimension 2^50 * 2^50. Diagonalization of such matrices is simply intractable on classical computers. In addition, the algorithms run LRR or KRR, but regression can also be slow in general. In all, I feel that the authors should give significantly more explanation about why their proposed algorithms are actually efficient on classical computers. In theory, Theorem 1 in Section 3.4 is a sample complexity result and does not investigate time complexity. In practice, the experiments are only conducted for Hamiltonians with 3 qubits or so. Either more evidence from theory or practice that the proposed algorithms have good time cost will be very helpful.\n\n2. The technical novelty of this work needs to be better explained. On the one hand, this paper follows the paper Schuld (2021) heavily, which had proposed the idea of applying kernel methods to machine learning problems. The authors may want to further explain how this work departs from Schuld (2021). It seems that using random Fourier features is a main consideration different from Schuld (2021), but this goes to my concern on the other hand: it omits very important results on quantum-inspired classical algorithms based on random Fourier features, namely Yamasaki et al. https://proceedings.neurips.cc/paper/2020/hash/9ddb9dd5d8aee9a76bf217a2a3c54833-Abstract.html at NeurIPS 2020 and Yamasaki and Sonoda https://arxiv.org/pdf/2106.09028.pdf. These two papers have studied the ideas of using classical sampling-based methods under random features to solving quantum machine learning problems. A very detailed comparison is very necessary from my perspective.\n\n3. Minor suggestions and typos in the paper:\n\n- Introduction:\n- - At many places, the references shall be listed with brackets, for instance in Page 1, Abbas et al. (2021); Cong et al. (2019); Huang et al. (2021) -> (Abbas et al. 2021; Cong et al. 2019; Huang et al. 2021). This should be applied in general for references as descriptions and not being the subject/object in a sentence.\n\n- - There’s a sentence: “When it comes to trainability, it has been shown that these exponential spaces are in fact drawbacks McClean et al. (2018)”. This is the famous barren plateau paper. I personally found this a bit inappropriate because the main of having barren plateau is not having exponential-size space, but more like the stochasticity in many ansatzes for parametrized quantum circuits has variance decrease exponentially in the number of qubits. I guess the reasoning here needs to be more careful.\n\n- Page 2, bottom: The other gates are called trainable -> Other gates are trainable.\nfigure 2 -> Figure 2 (and many other similar places)\n\n- Page 3, Eq.11 -> Eq. (11)\n\n- Page 3, A scaled version of Pauli encoding exist, where the Pauli are -> A scaled version of the encoding exists, where the Paulis are\n\n- Page 6: It would be helpful to explain the intuition of Theorem 1, especially how this is proved.\n\n- Page 13: How do we get Eq. (6) and (7), i.e., the eigenvalues have those forms? More discussions about the linear algebra behind will be preferred.\n\n- Page 18: There is a broken link at Appendix F. Also a few other typos: section 3.4 -> Section 3.4, (Eq.5) -> Eq. (5).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "4ts3-JYbkd", "reviewer": "Reviewer_neuE", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper questions the benefits of variational quantum circuits (VQC) for machine learning by demonstrating simple classical algorithms for approximating them. Specifically, VQC can be thought of as a multidimensional fourier series and so makes it a natural target for approximation via Random Fourier Features (RFF). The paper details three sampling strategies to sample frequencies for constructing random features to approximate a given VQC, as well as providing theoretical bounds on the approximation error. Under some assumptions RFF can efficiently approximate VQC as commonly implemented. The methods are tested on both synthetic and real datasets to demonstrate their effectiveness. The theoretical results also leave open the possibility of how VQC could still be beneficial for machine learning.", "summary_of_the_review": "Based on the importance of finding when or if quantum accelerators can achieve quantum advantage for ML, I believe this paper should be accepted. The paper clearly lays out the logic and theoretical analysis for attacking the current methods for quantum acceleration of ML, while also pointing the path forward. It is only my lack of expertise in this field that makes me a tad hesitant and thus my low confidence score.", "strength_and_weaknesses": "Strengths:\n* Clearly introducing the main concepts of VQC for ML, as well as RFF, making the paper accessible to a broad audience.\n* Very convincing arguments for the limitations of current VQC approaches, while outlining where future effort should be focused. Quantum advantage is a topic of high interest, and specifically quantum advantage for ML. Any work that helps shed light on when quantum-based approaches can and cannot help is of great significance.\n\nWeaknesses:\n* From a practical perspective, it is difficult to tell (for a non-expert in the field) how representative the experiments are. Could it be that there are factors of scale that are limited due to availability of current quantum accelerators that might change the empirical results -- not unlike the case of neural networks showing their true potential once sufficient data and compute became available? How dependent is the analysis and empirical results on current hardware and the regime tested?\n* The last two experiments are a bit confusing. Are you fitting the RFF to match the training data or to approximate the given VQC? If the former, then what do we learn from these experiments as opposed to any other classical ML technique? If the latter, then how come the test loss is better for RFF when it is trained to match the VQC?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster