Quantum advantage for learning shallow neural networks with natural data distributions

Domain: physics
Published: 2025-12-31
Editorial outcome: minor_revision

Abstract
Without large quantum computers to empirically evaluate performance, theoretical frameworks such as the quantum statistical query (QSQ) are a primary tool to study quantum algorithms for learning classical functions and search for quantum advantage in machine learning tasks. However, we only understand quantum advantage in this model at two extremes: either exponential advantages for uniform input distributions or no advantage for arbitrary distributions. Our work helps close the gap between these two regimes by designing an efficient quantum algorithm for learning periodic neurons in the QSQ model over a variety of non-uniform distributions and the first explicit treatment of real-valued functions. We prove that this problem is hard not only for classical gradient-based algorithms, which are the workhorses of machine learning, but also for a more general class of SQ algorithms, establishing an exponential quantum advantage.

Introduction
Machine learning (ML) is currently experiencing explosive success, made possible by an overwhelming growth of compute power, data availability, and improved models1–4. In parallel, quantum technology is also witnessing remarkable progress, including breakthroughs in quantum error correction5–19 and demonstrations of computations beyond the known limits of classical computers6,20–26. Given that our universe is inherently quantum, it is natural to consider leveraging powerful quantum computers for ML tasks, in hopes of new scientific advancements24,27–41. However, modern classical ML is mainly driven by empirical success, extending far beyond our theoretical understanding. In contrast, quantum technologies are still in their infancy, where we cannot yet accurately train and test large quantum ML models. Thus, we must rely on the rigorous frameworks of learning theory to characterize the performance of quantum learning algorithms and their potential advantage over classical learners.

One possible avenue for quantum advantage is to use quantum algorithms to learn classical objects, e.g., classical functions42–57 or distributions58–60. Such results commonly consider the quantum counterparts of frameworks, such as probably approximately correct (PAC)61 and statistical query (SQ) learning62, appropriately called quantum PAC42 and quantum SQ (QSQ)44, respectively. In particular, some exciting results show that there exist function classes for which quantum PAC/QSQ algorithms can provide exponential sample complexity advantages over classical learners when the input data distribution is uniform42,44–49,52,53. This is in stark contrast to the seminal result proving there is no quantum advantage for arbitrary distributions55,63–65. The void between exponential advantages on idealized uniform distributions and no advantage on potentially adversarial distributions leaves a large gap in our understanding of quantum learning advantages. These results also highlight the challenges in analyzing quantum advantage for empirical data distributions and mirror results in classical ML, where there exists problems that are NP-complete for arbitrary distributions but easy for the distribution-specific case66–69. Moreover, to our knowledge, all results in quantum learning theory to date focus on Boolean or discrete functions, while the majority of large-scale ML focuses on real-valued functions. Together, these two points raise our central question: Are there classes of real-valued functions and non-uniform distributions for which quantum data is advantageous?

These are also stated as two open questions in ref. 70. Here, by quantum data, we mean classical functions over distributions encoded into so-called quantum example states, as in quantum PAC and QSQ learning. We provide a new perspective on when these states might arise naturally later in the work.

While some results consider learning Boolean functions over c-bounded product distributions50,51, proving quantum advantages for more general non-uniform distributions still remains open. Moreover, for other forms of quantum data, such as expectation values of ground states, quantum advantages for learning over non-uniform distributions have been explored71. However, this is incomparable to the present work, where we focus on classical functions encoded in quantum example states.

In this work, we provide a positive answer to our central question by efficiently learning real-valued functions that are a composition of a periodic function and a linear function in the QSQ model over a broad range of non-uniform distributions, which includes Gaussian, generalized Gaussian72, and logistic distributions. These distributions are practically relevant with generalized Gaussian and logistic distributions finding applications in, e.g., image processing73–75 and population growth76–79, respectively. Moreover, note that success in the QSQ model automatically implies success in the quantum PAC model, as the QSQ model is strictly weaker because it does not allow entangled measurements80.

We highlight that the function class we consider is well-studied in the classical ML literature81–84. There, such functions—called cosine neurons or, more generally, periodic neurons — are commonly analyzed, as they form the basic structure of neural networks with periodic activation functions85–90 and can be seen as an extension of generalized linear models91,92. In particular, ref. 82 proves that any gradient-based classical algorithm cannot learn periodic neurons when the input data distribution has a sufficiently sparse Fourier transform, which is satisfied by many natural distributions, e.g., Gaussians, mixtures of Gaussians, Schwartz functions93, etc. We strengthen their proof to apply to our specific parameter choices that focus on the regime of quantum advantage. Furthermore, although gradient methods are perhaps the most popular in classical ML, there is strong evidence for classical hardness beyond gradient methods. In fact, we extend the classical hardness to hold for a more general class of algorithms performing correlational SQs94,95. Additionally, ref. 83 shows an exponential lower bound for any classical SQ algorithm learning this function class with respect to any log-concave distribution. Ref. 84 extends the hardness to any polynomial time classical algorithm learning under small amounts of noise and over Gaussian distributions, assuming the hardness of solving worst-case lattice problems96,97. These results83,84 do not directly apply to our setting due to a difference between the parameter regimes needed for quantum advantage versus classical hardness, but we expect classical hardness to still hold in this regime and leave this generalization open to future work.

Our algorithm uses a polynomial number of QSQs and iterations of gradient descent, resulting in a quantum advantage over any classical gradient-based algorithm for sufficiently Fourier-sparse input distributions82. Here, the classical algorithms considered are any algorithms that utilize approximate gradients of an average loss function, which includes, e.g., neural networks. Concretely, we obtain an exponential quantum advantage against classical gradient methods for Gaussian, generalized Gaussian, and logistic distributions. For Gaussian distributions, we additionally strengthen classical hardness to hold against a natural restriction of SQ algorithms (namely, correlational SQ algorithms94,95), which includes gradient methods, dimension reduction, and moment-based methods. To our knowledge, this is the first result in quantum learning of classical functions that explicitly considers real-valued functions. Figure 1 illustrates a schematic overview of our work. Then, we detail our quantum algorithm that solves this problem efficiently, exhibiting an exponential quantum advantage.

Results
In this section, we introduce the task of learning periodic neurons and show that it is classically hard for a broad class of powerful algorithms.

Problem definition
In this section, we define common access models in (quantum) learning theory and describe our learning problem more formally. We refer to Supplementary Note 1A and Supplementary Note 2 for further details.

We aim to learn a collection of functions C = {c: X -> Y} called the concept class, where X, Y are the input/output spaces, respectively. In particular, given some form of access to an unknown concept c* in C, we want to learn an approximation of c* with high probability. Typically in learning theory, one considers Boolean functions with X={0,1}^d, Y={0,1}. Importantly, in this work, we instead consider X=R^d, Y=R.

In the classical PAC model61, the learning algorithm is given labeled random examples {(x_i, c*(x_i))}_{i=1}^N, where the x_i are sampled from a distribution D over X and c* in C is an unknown target function. The SQ model62 is weaker than PAC, where, instead of direct access to the examples, the learning algorithm can only obtain noisy expectation values of functions of the data. This was originally proposed to model learning given noisy examples, and commonly used algorithms, such as stochastic gradient descent98, Markov chain Monte Carlo methods99,100, and simulated annealing101,102 can be implemented in this model.

We also consider the correlational SQ model94,95. This is a restriction of general SQs in which queries are only allowed to act on the input space X, not the labeled output space. We define this more precisely in Supplementary Note 1A. Correlational SQs include gradient methods, dimension reduction, and moment-based methods as special cases. In the case of Boolean functions, correlational SQs and general SQs are in fact equivalent94, but there exist separations between them for real functions103–105.

The quantum PAC and QSQ models are natural generalizations of these settings. In the quantum PAC model42, the learning algorithm is given copies of the quantum example state
|c*> = sum_{x in X} sqrt{D(x)} |x> |c*(x)> , (1)
where D is again some probability distribution. We note that there are some restrictions on the distributions D for which one can efficiently prepare this state and discuss this later. Also notice that upon measuring a quantum example state, one obtains (x, c*(x)) for x sampled from the distribution D, hence recovering the classical PAC examples. For QSQ access44, the learner queries an observable O and receives an approximation of the expectation value <c*|O|c*>. This is weaker than the quantum PAC model due to the inability to take entangled measurements across multiple copies of |c*>80. Notice also that because X is a continuous space in our setting, these definitions require discretization/truncation, which we discuss further in the Methods and Supplementary Note 1A. In all aforementioned cases, the goal is to learn the unknown function c* approximately with high probability using as few examples/queries as possible.

We are interested in learning a concept class consisting of functions that are a composition of a periodic function and a linear function. In other words, these are functions that can be represented as a single-layer neural network with a periodic activation function, hence dubbed periodic neurons. This ansatz is quite powerful and in some cases is able to achieve universal function approximation106–108. Moreover, the periodic neuron has known relationships to important complexity theoretic problems84,109.

Explicitly, let d >= 1 denote the input dimension and let S^{d-1} denote the (d-1)-dimensional unit sphere. Then, our concept class is defined as
C = {g_w*: R^d -> [-1, 1] : g_w*(x) = g~(x^T w*), w* in R^d, w* in S^{d-1}}, (2)
where g~: R -> [-1, 1] can be written as
g~(y) = sum_{j=1}^D beta*_j cos(2*pi*j*y), ||beta*||_1 = 1 (3)
for some constant D > 0 and unknown parameters beta*_j in R. In other words, our target functions g_w* are defined as follows. First, consider an unknown vector w* of norm R_w, and consider the linear function x^T w* defined by this coefficient vector. Then, compose this linear function with a linear combination of cosines, where the weights beta* are unknown. In our analysis, we have additional constraints on the vector w*, e.g., restricted to the positive orthant and bounded away from 0, but for simplicity of presentation, we omit this detail in the main text. We direct the reader to Supplementary Note 2 for more details.

To learn a target concept g_w* with respect to a distribution D, we want to find a good predictor f_theta(x) which minimizes the objective function
L_w*(theta) = E_{x ~ D} [(f_theta(x) - g_w*(x))^2], (4)
where theta are some tunable parameters. Namely, for a given epsilon > 0, we want an algorithm to find the parameters theta^ such that L_w*(theta^) <= epsilon. Our quantum algorithm additionally has QSQ access to the (discretized/truncated) example state |g_w*>. Here, discretization is necessary to encode the continuous outputs of the target function into a discrete quantum state, and we similarly require truncation to ensure that the superposition is not over an infinite space.

While gradient access is more restrictive than general classical SQ algorithms, SQ algorithms include gradient methods as a special case98. Gradient-based algorithms are also the most widely used methods to train neural networks in practice. Moreover, for Gaussian distributions, we extend classical hardness to hold against correlational SQ algorithms. These are more restrictive than general SQ algorithms103–105, but we nevertheless view this as an important step toward proving SQ hardness. As discussed above, there is also strong evidence that the problem remains hard for general SQ algorithms and even all efficient classical algorithms83,84. In fact, the techniques for proving hardness against gradient methods82 are similar to those for existing SQ hardness results62,110.

Classical hardness
Previous work from the classical literature81,82 shows that learning periodic neurons as described in the previous section is hard for classical gradient methods, which includes powerful algorithms, such as classical neural networks. This result holds for any input distribution that is sufficiently sparse in Fourier space, defined by the notion of epsilon(r)-Fourier-concentration. Intuitively, epsilon(r) is a function which characterizes how quickly the Fourier transform of the density function decays. We define Fourier concentration formally in Definition 3 in Supplementary Note 3. In Supplementary Note 3A, we strengthen the proof from 82 to show that classical hardness still holds for our additional constraints on the vector w*.

Theorem 1. (A variant of Theorem 4 in ref. 82; Informal) Let g_w*: R^d -> [-1, 1] in C be a uniformly sampled target function, where the unknown vector w* in R^d has norm R_w. Consider an input distribution whose density phi^2 can be written as a square of a function phi and is epsilon(r)-Fourier-concentrated. Then, any classical gradient-based algorithm requires at least p = epsilon_0 gradient samples with epsilon_0 precision to learn g_w* with probability 1-p over the choice of g_w*.

Note that there are similar classical hardness results which hold for any 1-Lipschitz loss function81, rather than the squared loss L_w* from (4). This theorem tells us that if the function epsilon(r) decays rapidly with r, then unless the number of gradient samples is extremely large or the noise in the problem is unrealistically small, a classical gradient-based algorithm cannot learn the concept class C from (2). We note that we only obtain a meaningful lower bound when epsilon(r) decays sufficiently quickly such that the infinite sum in the expression for epsilon_0 converges. This is guaranteed when the Fourier transform of the input distribution has sharply decreasing tails. For instance, for Gaussian distributions, the number of samples must scale as exp(Omega(min(d, R_w^2))). Here, the classical hardness stems from the gradient of the loss function concentrating around a fixed value, which, in turn, is due to the Fourier sparsity of the input distribution and target functions.

Furthermore, for the case of Gaussian distributions, we strengthen the classical hardness to hold against any classical algorithm which has access to correlational SQs94,111. This model is more general than gradient methods but is still a restriction of general SQs. We view our proof of classical hardness against such algorithms as an important step towards general SQ hardness.

Additionally, it is interesting to observe that only one type of query made by our quantum algorithm is not a correlational QSQ, i.e., observables of the form O tensor I, where the identity acts on the output register. Thus, one might argue that considering only correlational SQs for classical hardness is not a significantly unfair comparison. We prove the following theorem.

Theorem 2. (Correlational SQ Hardness; Informal) Consider a Gaussian distribution with a sufficiently large variance. Then, any classical algorithm using correlational SQs to C with respect to this distribution requires at least 2^{Omega(d)} queries to learn C to error epsilon.

The full theorem is stated in Theorem 2 in Supplementary Note 3B. Importantly, we highlight that the condition on the variance of the Gaussian distribution is satisfied by our quantum algorithm presented in the next section. Thus, classical hardness holds in the same regime as our efficient quantum algorithm. We also remark that, previously, classical learning theorists have shown similar correlational SQ lower bounds for learning single-layer neural networks112,113. However, these works consider different activation functions, so their results are not immediately applicable. We prove Theorem 2 by lower bounding the statistical dimension95,110,114 of C, which captures the difficulty of learning a concept class, similarly to the more commonly known VC dimension. The proof is provided in Supplementary Note 3B.

Quantum algorithm
In contrast, the complexity of our quantum algorithm scales only polynomially in d and polylogarithmically in R_w, since quantum algorithms can overcome and in fact leverage this Fourier sparsity via the quantum Fourier transform. We state our guarantees first for the uniform distribution. We highlight that while classical hardness for gradient methods holds on average over a uniform choice of g_w* from the concept class, the guarantee for our quantum algorithm applies in the stronger worst-case setting, i.e., it holds for any fixed g_w*. Our correlational SQ hardness result holds in the worst-case setting as well.

Theorem 3. (Uniform distribution; Informal Version of Theorem 4 in Supplementary Note 4) Let epsilon > 0, and let phi^2 be the uniform distribution. Let g_w*: R^d -> [-1, 1] in C be a target function for an unknown vector w* in R^d with norm R_w. Then, there exists a quantum algorithm with QSQ access to a suitably discretized quantum example state |g_w*> that learns g_w* to error epsilon with high probability using
N = O(d D polylog(d, D, R_w, 1/epsilon)) (5)
QSQs and t = Theta(log(D/epsilon)) iterations of gradient descent.

The detailed theorem statement is given in Theorem 4 in Supplementary Note 4. There, we also specify the QSQ noise tolerance needed explicitly. We highlight that it is only required to scale inverse polynomially in all parameters. We are also able to achieve a similar complexity for learning with respect to “sufficiently flat” non-uniform distributions. The precise technical conditions needed are stated in Supplementary Note 5. In particular, we show in Supplementary Note 5 that these conditions are satisfied for three practically-relevant classes of distributions: Gaussians, generalized Gaussians72, and logistic distributions. The wide applicability of Gaussian distributions is clear, and generalized Gaussians and logistic distributions have applications in image processing73–75 and population growth76–79, respectively.

The flatness property we require is typically satisfied by taking a distribution’s scale parameter large enough. Nevertheless, the condition still permits distributions that deviate significantly from uniform. For example, for Gaussian distributions, we need that the variance sigma is large enough such that e^{-x^2/sigma^2} is point-wise close to 1, e.g., |e^{-x^2/sigma^2} - 1| <= 1/10 over our truncated space, and that the derivative of the density function is not too large. These conditions are satisfied by d-dimensional Gaussians with covariance Sigma = 4*pi*R_w^2 I, where R_w is the size of the truncated space. This still leads to a density that decays exponentially with d away from the mean, in contrast to uniform distributions. There are also some conditions regarding the shape of the distribution, which are detailed in Supplementary Note 5.

With this, we obtain the following theorem. The detailed statement is given in Theorem 8 in Supplementary Note 5.

Theorem 4. (Non-uniform distributions; Informal Version of Theorem 8 in Supplementary Note 5) Let epsilon > 0, and let phi^2 be a sufficiently flat distribution. Let g_w*: R^d -> [-1, 1] in C be a target function for an unknown vector w* in R^d with norm R_w. Then, there exists a quantum algorithm with QSQ access to a suitably discretized quantum example state |g_w*> that learns g_w* to error epsilon with high probability using
N = O(d D polylog(d, D, R_w, 1/epsilon)) (6)
QSQs and t = Theta(log(D/epsilon)) iterations of gradient descent.

As a special case, we obtain the same guarantee for the natural distributions of Gaussians, generalized Gaussians, and logistic distributions. We prove that these distributions are also Fourier-concentrated and hence give us significant quantum advantages, specified in the following corollary.

Corollary 1. (Informal) The guarantee of Theorem 4 holds taking phi^2 as Gaussian, generalized Gaussian, or logistic distributions with large enough scale parameters. Meanwhile, any classical gradient-based algorithm requires
- exp(Omega(min(d, R_w^2))) samples for Gaussian distributions.
- Omega(min(exp(d), superpoly(R_w))) samples for generalized Gaussian distributions.
- exp(Omega(d R_w)) samples for logistic distributions.

This is a direct implication of the previous theorem combined with Propositions 2 and 3 and Corollary 9 in Supplementary Note 5. Thus, we see that for Gaussian, generalized Gaussian, and logistic distributions, we obtain an exponential quantum advantage over classical gradient methods. For Gaussian distributions, we retain this exponential advantage over correlational SQ algorithms.

Our key observation is that the classical hardness of 82 stems from the objective function L_w* being sparse in Fourier space. This implies that the objective function is difficult to optimize using gradient-based methods. On the other hand, quantum algorithms can typically take advantage of Fourier-sparsity by leveraging the quantum Fourier transform (QFT). In fact, we notice that the target functions g_w* are periodic in each coordinate with period 1/w*_j:
g_w*(x + 1/w*_j e_j) = g~( (x + 1/w*_j e_j)^T w* ) = g~(x^T w* + 1) = g~(x^T w*) = g_w*(x) (7)
where we use that g~ has period 1 and use e_j to denote the unit vector for coordinate j in [d]. Thus, information about the unknown vector w* is contained in the period of g_w*. This observation yields a simple quantum algorithm: (1) Perform period finding by encoding the QFT into QSQs to learn the vector w* one component at a time, (2) Learn the unknown parameters beta*_j defining the periodic activation function (3) using classical gradient methods. Note that once we have an approximation of w* from Step (1), Step (2) is effectively a regression problem, allowing it to be solved via gradient methods.

Despite the initial simplicity of this algorithm, there are several nontrivial issues that arise, particularly in Step (1). First, recall that the quantum example state (1) must be suitably discretized because our target function is real. However, there exist pathological examples in which discretization eliminates any information about the period of the original function (see, e.g., Section 10 of ref. 115). Thus, it is important to choose the correct discretizations such that the period is sufficiently preserved. Another problem is that the standard period finding algorithm does not apply because the period 1/w*_j is not necessarily an integer. Additionally, standard period finding is only analyzed for uniform superpositions, whereas we are primarily interested in non-uniform superpositions.

To resolve these problems, we carefully discretize the target function such that it satisfies pseudoperiodicity116 with a period proportional to 1/w*_j in each coordinate. For a period S, instead of requiring that h(k) = h(k + lS) for an integer l, pseudoperiodicity dictates that h(k) = h(k + [lS]), where [lS] denotes rounding lS either up or down. Then, for uniform distributions, we can use Hallgren’s algorithm116, which finds the (potentially irrational) period of pseudoperiodic functions. It is still nontrivial to apply Hallgren’s algorithm, as it crucially assumes the existence of an efficient verification subroutine to check if a given guess is close to the period of a pseudoperiodic function. Unlike for periodic functions, such verification is not straightforward for pseudoperiodic functions. We design a suitable verification procedure which uses D QSQs in Theorems 6 and 10 in Supplementary Notes 4A2 and 5A2, respectively.

Moreover, Hallgren’s algorithm does not apply for non-uniform distributions. To this end, we design a new period finding algorithm that works for sufficiently flat non-uniform distributions, which could be of independent interest. The sufficiently flat condition on the distributions stems from our generalization of Hallgren’s algorithm as well as several integral bounds needed for Step (2) of the algorithm. We expand on these ideas in the Methods and Supplementary Notes 4 and 5.

Methods
Classical hardness
In this section, we give an overview of the proofs of Theorems 1 and 2. First, to prove Theorems 1, we adapt the proof of Theorem 4 from 82 to hold for our concept class C, which imposes additional constraints on the vector w*. Namely, for our setting, w* is restricted to the positive orthant and bounded away from 0; meanwhile, in ref. 82, w* can be any d-dimensional vector with norm R_w. We must argue that these restrictions do not make the problem easier for classical algorithms.

The crux of the argument of 82 shows that for any function h, for a random choice of w*, the Fourier transform of the target function g_w* does not correlate well with h (see Lemma 1 in Supplementary Note 3A). Thus, no matter what our hypothesis function is, obtaining information about w* is difficult. However, their proof crucially uses that w* is chosen randomly from an exponentially large set of nearly orthogonal vectors, and their construction of this set does not adhere to our requirements for w*. Our main technical contribution for this proof is showing the existence of a large set S~_w of nearly orthogonal vectors which lie in the positive orthant and are bounded away from zero. We do so by leveraging tools from high-dimensional geometry131.

In Theorem 2, we strengthen the classical hardness to hold against any algorithms using correlational SQs when learning with respect to Gaussian distributions. A standard method for proving correlational SQ lower bounds is via the statistical dimension95,110,114, which captures the difficulty of learning a concept class, similarly to the more commonly known VC dimension. Informally, the statistical dimension quantifies the size of the largest subset of the concept class whose elements have “low correlation” (see Definition 4 in Supplementary Note 3B for a formal definition). Intuitively, functions in this low correlation subset should be hard to distinguish and thus hard to learn. Several works114,132,133 have formalized this relationship, proving, roughly, that lower bounds on the statistical dimension imply correlational SQ lower bounds (see Theorem 3 in Supplementary Note 3B). Our key contribution is proving an exponential lower bound on the statistical dimension of our concept class C, where we utilize properties of Gaussian integrals and the construction of the set S~_w from the proof of Theorem 1 described above. Thus, this results in an exponential lower bound for correlational SQ algorithms.

Quantum algorithm
In this section, we describe the ideas behind the proofs of Theorems 3 and 4. As discussed above, our key observation is that the target function g_w* is periodic in each coordinate with period 1/w*_j. This informs our quantum algorithm, which is as follows: (1) Perform period finding by encoding the QFT into QSQs to learn the vector w* one component at a time; (2) Learn the unknown parameters beta*_j defining the periodic activation function (3) using classical gradient methods. Thus, the proofs are separated into two main parts, each analyzing the sample complexities for these two algorithmic steps. The proofs for the uniform distribution are in Supplementary Note 4, and those for the non-uniform distributions are in Supplementary Note 5. In particular, Step (1) is analyzed in detail in Supplementary Notes 4A and 5A, and Step (2) is examined in Supplementary Notes 4B and 5B. In the following, we give an overview of the proofs.

Learning the linear function. We want to apply period finding to our target function g_w*: R^d -> [-1, 1] to approximate the unknown vector w* that defines the inner linear function. First, because g_w* has real inputs and outputs, we need to discretize it so that it can be represented by a (discrete) quantum example state (1). We require that the chosen discretization is pseudoperiodic, a condition which is weaker than periodicity but still ensures that the discretized function retains information about the period of g_w*. Specifically, for d=1, a function h: Z -> R is pseudoperiodic with period S in R if h(k) = h(k + [lS]) for any integer l, where [lS] denotes rounding lS either up or down to the nearest integer. One should compare this to periodicity, where the necessary condition is instead h(k) = h(k + lS). We choose the following discretization, considering d=1 for simplicity. We generalize to arbitrary d >= 1 in the discussion surrounding Supplementary Equation (254).

Lemma 1. (Discretization; Informal) Let M_1, M_2 be suitably chosen discretization parameters with M_1 > M_2. Consider the discretized function h_{M_1, M_2}: Z -> 1/M_2 Z defined by
h_{M_1, M_2}(k) = g_w*( [k/M_1] ), (8)
where [.] denotes rounding down to the nearest multiple of 1/M_1. Then, h_{M_1, M_2} is pseudoperiodic with period M_1/w* for a large proportion of inputs. Requiring M_1 > M_2 at an appropriate ratio makes the discretization more coarse on the outputs than the inputs, ensuring that pseudoperiodicity is satisfied. In our proof, we choose M_1, M_2 to scale polynomially in the problem parameters, i.e., poly(epsilon, D, d, R_w), where epsilon is the desired error, D is the number of cosine terms in the periodic activation function (3), d is the input dimension, and R_w the norm of w*.

Recall that g_w* has period 1/w*_j in the jth coordinate. Thus, learning the period of h_{M_1, M_2} also allows us to approximate the period of g_w*. However, straightforwardly applying standard period finding algorithms to h_{M_1, M_2} fails because h_{M_1, M_2} is only pseudoperiodic rather than periodic and its period M_1/w* is not necessarily an integer. Instead, we turn to Hallgren’s algorithm116, which determines the period of pseudoperiodic functions and applies to real periods. Note that Hallgren’s algorithm only applies for the uniform distribution, so we consider this case for now. At a high level, Hallgren’s algorithm first quantum Fourier samples twice and computes the continued fraction expansion of the quotient of the results. Then, it constructs a guess for the period for each convergent of the expansion and iterates through each guess, checking which one approximates the period. Ref. 116 shows that one guess is guaranteed to be close to the period. We discuss Hallgren’s algorithm in more detail in Supplementary Note 1B.

Notice that a crucial subroutine necessary for Hallgren’s algorithm is a verification procedure to check if a given guess is close to the period of a pseudoperiodic function. Unlike for periodic functions, where such verification is straightforward, this is nontrivial for pseudoperiodic functions. In fact, ref. 116 leaves this as an assumption to be instantiated upon applying the guarantee of Hallgren’s algorithm. We design a suitable verification procedure which uses D QSQs (see Theorems 6 and 10 in Supplementary Notes 4A2 and 5A2, respectively). The main idea is to compute the inner product between h_{M_1, M_2} and h_{M_1, M_2}(k+T), where T is a guess for the period. Intuitively, this inner product should be large for a guess that approximates the period well. We define an observable that allows us to compute this inner product using QSQs. Then, we identify a suitable threshold which the inner product surpasses if and only if the guess is indeed close to the period. The majority of the technical work for the verification procedure lies in finding such a threshold. With this, the only remaining quantum part of Hallgren’s algorithm is quantum Fourier sampling, which can be accomplished using QSQs by encoding the QFT into the queried observable. Because we need to repeat this algorithm for each entry in the vector w* in R^d, we use O~(dD) QSQs, where the polylogarithmic factors come from amplifying the success probability of Hallgren’s algorithm.

Thus far, we discussed how to utilize Hallgren’s algorithm for our problem, which only applies for uniform distributions. We generalize these ideas to perform period finding for non-uniform input distributions. This algorithm can be found explicitly in the appendices in Algorithm 3 in Supplementary Note 5B2, and the verification procedure is presented in Algorithm 4 in Supplementary Note 5B2. Our algorithm follows the same structure as Hallgren’s algorithm but requires a new analysis due to the different input distribution. Here, we crucially use that the non-uniform distributions we consider are sufficiently flat, e.g., they are pointwise-close to uniform. As discussed previously, our flatness condition only requires the univariate (unnormalized) marginals to be close to uniform, but the overall density can decay exponentially in d.

Learning the periodic activation function. In the previous section, we showed how to obtain an approximation w^ of the unknown vector w* using quantum period finding. Using this approximation, we can learn the unknown parameters beta*_j, which determines the periodic activation function g~ given in (3). This step of the algorithm is purely classical.

With the approximation w^, we can consider predictors f_beta defined by
f_beta(x) = sum_{j=1}^D beta_j cos(2*pi*j*x^T w^), (9)
where beta in R^d is a vector of trainable parameters. These predictors have the same form as the target function g_w* but replace w* and beta*_j with w^ and beta_j, respectively. Thus, the loss function from (4) can be written more explicitly as
L_w*(beta) = E_{x ~ phi^2} [ (sum_{j=1}^D beta*_j cos(2*pi*j*x^T w*) - sum_{j=1}^D beta_j cos(2*pi*j*x^T w^))^2 ] (10)
We use (approximate) gradient access to this loss function to learn parameters beta^ such that L_w*(beta^) <= epsilon. We acknowledge there may be other approaches to solve for the parameters, but we believe gradient descent is the most straightforward. First, we show that the gradients are informative, i.e., the derivative of the objective function partial L_w*/partial beta_k indeed reflects how far beta_k is from the true parameter beta*_k. With this, we can simply apply gradient descent (see, e.g., ref. 134), where we show that the iterates converge to the true parameters within t = Theta(log(D/epsilon)) steps. Most of the work in this step goes into carefully choosing the hyperparameters (e.g., the number of iterations to run gradient descent, how accurate the approximation w^ is required to be, etc.) to guarantee that the value of the loss function is small. In this step, the proofs for uniform and non-uniform distributions are very similar. The full proofs are provided in Supplementary Note 4B for the uniform case and Supplementary Note 5B for the non-uniform case.

Peer review rounds
[{"round": 1, "reviewer_comments": {"reviewer_1": "The ultimate goal of Quantum Machine Learning (QML) is to achieve practical quantum advantages in data analysis —\nwhich is by no mean a trivial feat. Due to the lack of good quality large-scale quantum hardware, theoretical studies are\nneeded to guide the path, in particular rigorous demonstration of a quantum advantage in a more analytically manageable\n(despite not reflecting the real world problem) setting.\nThe work makes a novel contribution by attempting to show the advantage in the Quantum Statistical Query (QSQ)\nframework for learning periodic neurons (i.e., a linear combination of cosine functions which take an output from a single\nlayer of neural networks as an argument) over non-uniform input distributions. In particular, there are two key improvements\nupon prior results in the QSQ framework with a quantum example state: (1). The target functions are real-valued together\nwith input data (instead of, Boolean and bit-string, respectively, commonly used in this framework), which means the authors\nare required to come up with an appropriate choice of discretization for a quantum example state in Eq. (II.1) for the QSQ\nframework, and (2). The input data distributions do not need to be uniform as long as they are “sufficiently flat” — with some\nprovided examples including (generalized) Gaussian and logistic distributions. The developed QSQ-based algorithm\nconsists of two main steps: (1). Period finding which employs the variant of the Quantum Fourier Transform to find relevant\nperiods of the target functions using the quantum example state, and (2). Solving regression with gradient descents which\nclassically determines the coefficients associated with individual cosine functions.\nI did enjoy reading the work and think the improved version would significantly contribute to the field of QML. However, I\ncannot yet make a recommendation for publication without the following comments/concerns being addressed.\n(1). My biggest concern is that to properly claim the quantum advantage, it is necessary to prove the classical hardness of\nlearning periodic neurons beyond gradient descent methods. I appreciate I may not be asking for an easy task, but given that\ntraining the loss function suffers from a classical version of barren plateau there might be the way to extend the current proof\nof the classical hardness with the gradient-based methods.\n(2). The notion of Fourier concentration should be elaborated more in the main text, since it plays a central role on the\nclassical (gradient-based) hardness. For example, the infinite sum of ε(n Rω/4) over n in Theorem 1 should be explained\nthat it does not diverge.\n(3). The hardness statements of Theorem 1 and Corollary 1 are not stated in a consistent manner e.g., in Corollary 1, it is\nstated in terms of exponential sample scaling (which is more preferable personally, but happy with any version as long as it\nis consistent).\n(4). Regarding Corollary 1, if we choose Rω \\in O(1) since d scales at most polynomially with the number of qubits, the lower\nbounds on the sample complexity seem to be too loose for (generalized) Gaussian distributions to claim the classical\nhardness. Do we need an additional assumption on Rω for this ?\n(5). It should be noted that barren plateaus which are the root of classical hardness here are the classical version and\nfundamentally differ from the quantum version.\n(6). The condition on the “sufficiently flat” distribution needs to be explained in more details in the main text. In particular, this\ncondition does not appear on the sample complexity of the current Theorem 3. Additionally, this part of the sentence “[…] yet\nnot so large that the distribution is effectively indistinguishable from uniform.” may need to be revisited — what does it mean\nto be “effectively indistinguishable from uniform” here ? More minor comment is that the notion of truncated space seems\nappear a bit out of no where.\n(7). The proof of the quantum learnability relies sufficiently on the sufficient flatness condition, which is stronger than the\nFourier concentrated condition (as explained in Appendix). Maybe it is worth stating what those additional assumptions play\na role in the proof — elaborating on this also enhances the closing sentence in the hope of extending the advantage result\nmore generally with only the Fourier concentration.\n(8). The current title is a bit misleading with “natural data distribution” ? — Though, it’s true that these non-uniform\ndistributions particularly Gaussian appear frequent in nature. However, I am not sure if I agree that these distributions\nrepresent the nature of how real-world data are distributed ? Furthermore, the notion of “periodicity” which is crucial to both\nquantum learnability and classical hardness is also missing in the title.\n(9).", "reviewer_interest": "I tend to agree with the authors on this, which is why I feel like this aspect should be\nelaborated. With such a feat and important key aspect of the algorithm, the technical details are a bit underrepresented. For\nexample, maybe it is worth to include this developed period finding algorithm explicitly ?\n(10). Regarding the", "reviewer_descents": "art, the analysis/proof does not seem to take into account\nthe finite sample effect of training data. In particular, Eq (V3) averages over all the input space with respect to the considered\ninput distribution. What happens to the results when we have instead finite training samples drawn from such input\ndistribution (— the situation which may be more practical) ?\n(11). Following from (10), it also occurs to me that these coefficients could be estimated with other optimization approaches.\nFor example, if we have the training dataset of size N such that N > D, these coefficients could be obtained with simply\nsolving linear system of equations ?\n(12). The discussion on the new aspect of having the known target function and creating the\nquantum example state for learning a more compact representation of the function is insightful. While it is true that some periodic structure appears\nrelevant in practice for data analysis (— this together with the previous sentence giving more justification of the quantum\nexample from a different angle), I do not think this specific setting considered in this work is practically relevant and honestly\nI think this is fine.\n(13). “Are there classes of real-valued functions and non-uniform distributions for which quantum data is advantageous?” —\nwhile it is true that this work is the first to positively answer this with the quantum example state, Molteni et al\n[arXiv:2405.02027 (2024)] has shown this also in the setting which can be considered to be under the QSQ framework", "reviewer_without": "he quantum example state. In that work, the input data distribution is", "reviewer_large": "reviewer_2\": \"Summary:\nThe submission “Quantum advantage for learning shallow neural networks with natural data distributions” investigates the\nquery complexity of learning functions that are a composition of a periodic function and a linear functon(aka periodic\nneurons) in the distribution specific setting, given access to a quantum statistical query (QSQ) oracle that can output noisy\nexpectation values of the quantum example state. The loss function considered is the expectation of the error between the\npredictor and the true concept. The main result of the paper is an exponential separation in the query complexity of learning\nunder sufficiently flat distributions with queries from the QSQ oracle and the samples required during any classical gradient-\nbased algorithm.\nEvaluation:\nThere has been a lot of attention from the quantum learning theory community to separations between learning classes of\nBoolean functions from random examples classically and using the quantum example state (or qsamples) quantumly. This\nwork seems a natural extension of prior work in considering possible separations between learning real-valued functions\nusing a classical gradient based algorithm using samples versus a quantum algorithm using a QSQ oracle.\nFrom a technical perspective:\n- Appropriate assumptions: Regarding the quantum example state, choices were made in the discretization of the real-\nvalued function being encoded to ensure information regarding the periodicity was retained, which the authors call\npseudoperiodicity.\n- Hallgren’s algorithm: In order to apply Hallgren’s algorithm for finding the period of the function, the authors have to\nimplement a verification protocol that makes few queries to the QSQ oracle to test if a given guess is close to the period.\n- Difficulty for classical-gradient algorithms: The authors design lower bounds for the learning task for classical-gradient\nalgorithms by building on Ref. [80].\nComments regarding the paper:\n- At the end of section II “Problem Definition”, it is remarked that having access to the derivative is more restrictive than\ngeneral classical SQ algorithms. Why are classical gradient algorithms then best suited for this task and the best classical\nbaseline for the quantum learner?\n- Could the authors also discuss why the SQ setting is a natural generalization of the gradient access model in a bit more\ndetail? This does not seem substantiated currently.\n- I found the sections of “Introduction” and “Problem Definition” well-written even for an audience outside of this subarea.\n- In lines 57-60, the authors remark that Ref. [80] mention that periodic neurons cannot be learned efficiently under\ndistributions with sparse Fourier transform. At first glance, I would have thought that sparsity of the Fourier spectrum would\nhelp. Could you please provide some intuition why this is not the case?\n- In lines 87-88, the authors remark that the quantum example state (II.1) is not known to be efficiently preparable for all\ndistributions but I could not find a discussion regarding this later except for in lines 1783-1784 but only for d=1. What about\nhigher values of d that this paper seems to mainly care about?\n- From looking at Corollary 10, it appears to me that you also have an exponential separation in D (and not just d) as long as\nthe first term of (E.7) is appropriately bounded. Perhaps, this should be mentioned as part of Corollary 1 to indicate that there\nis an advantage even for d=1 for certain regimes. (I might be mistaken here. I did not go through the proof of Corollary 10\ncompletely.)"}, "author_response": "We thank the reviewer for their accurate summary and close reading of our work. We have endeavored to address all comments below and made corresponding changes in the manuscript.\n1/7\n(1). My biggest concern is that to properly claim the quantum advantage, it is necessary to prove\nthe classical hardness of learning periodic neurons beyond gradient descent methods. I appreciate I\nmay not be asking for an easy task, but given that training the loss function suffers from a classical\nversion of barren plateau there might be the way to extend the current proof of the classical hardness\nwith the gradient-based methods.\nAuthor response: We thank the reviewer for their comment and agree that stronger classical\nhardness would enhance our claim of quantum advantage, and believe we have now strengthened\nour result. Nevertheless, we emphasize that gradient methods are definitively the most common\nalgorithm used in practice to learn functions of this form. Moreover, because the classical hardness\nstemsfromFouriersparsity, wedonotexpectanyclassicalalgorithmtoovercomethisbarrier. Thus,\nour current proof already provides strong evidence of general classical intractability. Additionally,\nwe again emphasize that results in the classical literature provide strong evidence for more general\nhardness, see Refs. [84, 85].\nHowever, we acknowledge the reviewer’s perspective and have strengthened the classical hardness\nto hold against correlational statistical queries (SQs). This class is more general than gradient\nmethods, as correlational SQs also include dimension reduction and moment-based methods\n(albeit they are still restricted compared to general classical SQs, which would be the most equal\ncomparison to our quantum access model). We state this new result in Theorem 2 in the revised\nmain text, and the proof is given in Appendix C.2. To prove it, we take a different approach\nfrom our gradient hardness result. Instead, we prove an exponential lower bound the statistical\ndimension (the analogue of VC dimension for SQ algorithms) of our concept class, which imposes\na fundamental barrier against efficient learners. We have also edited the main text to discuss the\nresult further. Given the length of the current paper and the short review period, we leave further\nextensions of the classical hardness to future work.\n(2). The notion of Fourier concentration should be elaborated more in the main text, since it plays\na central role on the classical (gradient-based) hardness. For example, the infinite sum of ϵ(nR /4)\nw\nover n in Theorem 1 should be explained that it does not diverge.\nAuthor response: We thank the reviewer for pointing this out. We note that if the infinite\nsum indeed diverges, then the sample complexity lower bound is vacuous. Thus, one can view it\nas imposing a condition on the input distribution (e.g., being Fourier concentrated with at least\nsuper-polynomially decaying tails) to obtain a meaningful lower bound. We have clarified this in\nthe text below the theorem statement.\n(3). The hardness statements of Theorem 1 and Corollary 1 are not stated in a consistent manner\ne.g., in Corollary 1, it is stated in terms of exponential sample scaling (which is more preferable\npersonally, but happy with any version as long as it is consistent).\nAuthor response: We appreciate this feedback and have edited the statement to be more\nconsistent with Corollary 1. However, we clarify that Theorem 1 is more general than Corollary 1\nand will only imply specific query complexity lower bounds for particular choices of distributions.\nWe state it as such for consistency with the classical literature and to emphasize that classical\nhardness holds for more general distributions than the examples we give.\n(4). Regarding Corollary 1, if we choose R ∈ O(1) since d scales at most polynomially with the\nw\nnumber of qubits, the lower bounds on the sample complexity seem to be too loose for (generalized)\nGaussian distributions to claim the classical hardness. Do we need an additional assumption on\nR for this?\nw\nAuthor response: Thank you for the question. Both R and d should be considered as large\nw\n2/7\nparameters. This is the same setting as for gradient-based hardness (Ref. [80]).\n(5). It should be noted that barren plateaus which are the root of classical hardness here are the\nclassical version and fundamentally differ from the quantum version.\nAuthor response: We thank the reviewer for their comment and have explained how quantum\nalgorithms overcome the source of classical hardness in the text below Theorem 1. We also think\nthat the use of the term “barren plateau” may confuse readers due to its association with barren\nplateaus in variational QML (as suggested by the reviewer) and have removed it from the text.\nInstead, we describe the classical hardness as stemming from the gradient of the loss function being\nextremely concentrated, which is also more precise.\n(6). The condition on the “sufficiently flat” distribution needs to be explained in more details in\nthe main text. In particular, this condition does not appear on the sample complexity of the current\nTheorem 3. Additionally, this part of the sentence “[...] yet not so large that the distribution\nis effectively indistinguishable from uniform.” may need to be revisited — what does it mean to\nbe “effectively indistinguishable from uniform” here? More minor comment is that the notion of\ntruncated space seems appear a bit out of no where.\nAuthor response: We apologize for the lack of clarity. The sufficiently flat condition does\nnot need to appear in the sample complexity. Any parameters introduced by this condition are\nconstants and thus absorbed into the big-oh in the sample complexity, so they will not appear\nexplicitly. We also thank the reviewer for pointing out the previously un-introduced notion of a\ntruncated space and have added a description to the end of Section II.\nBy the informal phrase “effectively indistinguishable from uniform,” we meant to convey that\nour algorithm is able to tolerate significant deviations of the data distribution from uniform with\nrespect to, e.g., ℓ∞ distance. The ability to handle such deviations stems from the element-wise\nnature of our algorithm. We have changed the wording of this phrase in the manuscript.\n(7). The proof of the quantum learnability relies sufficiently on the sufficient flatness condition,\nwhich is stronger than the Fourier concentrated condition (as explained in Appendix). Maybe it is\nworth stating what those additional assumptions play a role in the proof — elaborating on this also\nenhances the closing sentence in the hope of extending the advantage result more generally with\nonly the Fourier concentration.\nAuthor response: We thank the reviewer for your suggestion. We previously explained the role\nof the sufficiently flat condition at the end of Section III and the end of Section V.A, namely that\nit is important for the analysis of our non-uniform period finding algorithm. As suggested, we have\nalso added a sentence about this in the discussion near the open question the reviewer mentions.\n(8). The current title is a bit misleading with “natural data distribution”? — Though, it’s true\nthat these non-uniform distributions particularly Gaussian appear frequent in nature. However,\nI am not sure if I agree that these distributions represent the nature of how real-world data are\ndistributed? Furthermore, the notion of “periodicity” which is crucial to both quantum learnability\nand classical hardness is also missing in the title.\nAuthor response: We thank the reviewer for your perspective on this, but, after much consid-\neration, we would prefer to keep our current title. We refer to the non-uniform distributions we\nconsider as “natural” due to the classical literature, e.g., Ref. [80]. Regarding periodicity, while\nour quantum algorithm indeed relies on this property, classical hardness holds for a variety of\ndifferent activation functions (see, e.g., Ref. [82]). We think that “shallow neural networks” in the\ntitle makes the work more accessible to a broad audience, rather than a more technical description\n3/7\nsuch as “periodic neurons.” This also emphasizes that the functions we consider form the basic\nstructure of neural networks with periodic activation functions, which are well-studied in classical\nML (see, e.g., Refs. [84-89]). Nevertheless, we mention periodicity in the abstract and throughout\nthe work.\n(9). “To this end, we design a new period finding algorithm that works for sufficiently flat non-\nuniform distributions, which could be of independent interest.” — I tend to agree with the authors on\nthis, which is why I feel like this aspect should be elaborated. With such a feat and important key aspect of the algorithm, the technical details are a bit underrepresented. For example, maybe it\nis worth to include this developed period finding algorithm explicitly?\nAuthor response: Thank you for your positive feedback. The ideas for the uniform case are\npresented in Section V.A, and the non-uniform case is quite similar but just requires additional\ntechnical effort (e.g., some of the bounds do not work out as nicely as the uniform case). We thus\nfind it more instructive to present the ideas of the algorithm. However, as suggested, we have\nadded a reference to the explicit algorithm in Section V.A.\n(10). Regarding the “solving regression with gradient descents” part, the analysis/proof does not\nseem to take into account the finite sample effect of training data. In particular, Eq (V3) averages\nover all the input space with respect to the considered input distribution. What happens to the\nresults when we have instead finite training samples drawn from such input distribution (— the\nsituation which may be more practical)?\nAuthor response: Thank you for your question. While the reviewer is correct that the average in\nEq. (V.3) is taken over the entire input space, our access model assumes that we are given access to\napproximate gradients of the loss function in Eq. (V.3). In particular, one could approximate such\ngradients using a finite amount of labeled training data, as in the case of PAC learning. We have\nedited the manuscript to make it clearer that we only need approximate access to the gradients.\nWe also note that this is a standard access model/loss function in the classical literature and is not\nspecific to our setting.\n(11). Following from (10), it also occurs to me that these coefficients could be estimated with other\noptimization approaches. For example, if we have the training dataset of size N such that N > D,\nthese coefficients could be obtained with simply solving linear system of equations?\nAuthor response: Thank you for your thoughtful comments. First, we clarify that having access\nto labeled training data like in classical PAC learning is a stronger access model than the gradient\naccess we consider. In particular, approximate gradient access is a special case of the statistical\nquery model, which is weaker than having access to PAC examples.\nEven if one allows direct access to labeled training data {(x,g (x))}, then it is not immediately\nw⋆\nclear if solving a system of linear equations would work. If we understand the reviewer’s suggestion\ncorrectly, one could imagine constructing a system of equations in the unknown parameters β⋆\nj\nusing the known form of g and the values g (x) from the training data. However, from the\nw⋆ w⋆\nperiod finding step of the algorithm, we only have approximate knowledge of w⋆, so this would only\ngive an approximate system of linear equations, which may be difficult to solve. Nevertheless, we\ncertainly acknowledge that other optimization methods could also be used to find the parameters,\nand we only use gradient descent since we find it the most straightforward. We have clarified this\nat the end of Section IV.B.\n(12). The discussion on the new aspect of having the known target function and creating the\nquantum example state for learning a more compact representation of the function is insightful.\nWhile it is true that some periodic structure appears relevant in practice for data analysis (—\n4/7\nthis together with the previous sentence giving more justification of the quantum example from a\ndifferent angle), I do not think this specific setting considered in this work is practically relevant\nand honestly I think this is fine.\nAuthor response: We agree with the reviewer in broad terms. In the discussion, we hope\nto provide a new perspective on some scenarios where one could imagine creating quantum\nexample states since this is generally overlooked in the literature. We agree that our setting is\nnot immediately practically relevant, though we hope these examples can help motivate empirical\nstudies in the future as in classical ML today and thank the reviewer for their positive assessment\nregardless.\n(13). “Are there classes of real-valued functions and non-uniform distributions for which quantum\ndata is advantageous?” — while it is true that this work is the first to positively answer this with\nthe quantum example state, Molteni et al [arXiv:2405.02027 (2024)] has shown this also in the\nsetting which can be considered to be under the QSQ framework “without” the quantum example\nstate. In that work, the input data distribution is “arbitrary” and the target function is real-valued.\nAuthor response: Thank you for this comment. We were aware of this work but did not classify\nit as addressing the same problem. Namely, we focus on learning functions from classical learning\ntheory encoded in quantum states (e.g., through quantum example states), which is the same\nsetting as the survey we cite for these open questions. In contrast, Molteni et al. considers more\nquantum-inspired functions arising from expectation values of quantum states. Following the\ncentral question, we clarify that “quantum data” refers specifically to the setting of quantum\nexample states considered in this work.\n(14). Font size in the Fig 1 diagram is unnecessarily too large.\nAuthor response: We have decreased the font size.\nReviewer #2 (Remarks to the Author):\nSummary: The submission “Quantum advantage for learning shallow neural networks with natural\ndata distributions” investigates the query complexity of learning functions that are a composition of\na periodic function and a linear functon(aka periodic neurons) in the distribution specific setting, given access to a quantum statistical query (QSQ) oracle that can output noisy expectation values\nof the quantum example state. The loss function considered is the expectation of the error between\nthe predictor and the true concept. The main result of the paper is an exponential separation in the\nquery complexity of learning under sufficiently flat distributions with queries from the QSQ oracle\nand the samples required during any classical gradient-based algorithm.\nEvaluation: There has been a lot of attention from the quantum learning theory community to\nseparations between learning classes of Boolean functions from random examples classically and\nusing the quantum example state (or qsamples) quantumly. This work seems a natural extension\nof prior work in considering possible separations between learning real-valued functions using a\nclassical gradient based algorithm using samples versus a quantum algorithm using a QSQ oracle.\nFrom a technical perspective: - Appropriate assumptions: Regarding the quantum example state,\nchoices were made in the discretization of the real-valued function being encoded to ensure informa-\ntion regarding the periodicity was retained, which the authors call pseudoperiodicity. - Hallgren’s\nalgorithm: In order to apply Hallgren’s algorithm for finding the period of the function, the authors\nhave to implement a verification protocol that makes few queries to the QSQ oracle to test if a\ngiven guess is close to the period. - Difficulty for classical-gradient algorithms: The authors design\n5/7\nlower bounds for the learning task for classical-gradient algorithms by building on Ref. [80].\nAuthor response: We thank the reviewer for their thorough and careful reading of our work.\nComments regarding the paper: - At the end of section II “Problem Definition”, it is remarked that\nhaving access to the derivative is more restrictive than general classical SQ algorithms. Why are\nclassical gradient algorithms then best suited for this task and the best classical baseline for the\nquantum learner?\nAuthor response: Thank you for your comment, we have accordingly further strengthened our\nhardness result. However, we do believe that gradient algorithms are the best baseline because they\nare indisputably the most common algorithm used in practice to learn and train neural networks.\nThus, the essence of our result is that our quantum algorithm provably outperforms the most\npractically-relevant class of classical methods used to tackle the problem. Moreover, the proof\nelucidates that this classical hardness stems from Fourier sparsity, which we do not expect more\npowerful classical algorithms to be able to overcome. We have added some explanation to the end\nof Section II.\nTo address this comment more fully, we have also added a new result which strengthens the classical\nhardness to hold beyond gradient methods. Namely, we prove that this problem is hard for any\nalgorithm using correlational SQs. These are a generalization of gradient methods. In particular,\ncorrelational SQs also include dimension reduction and moment-based methods as special cases.\nWe state this new result in Theorem 2 in the revised main text, and the proof is given in Appendix\nC.2. We have also edited the main text to discuss this result further.\n- Could the authors also discuss why the SQ setting is a natural generalization of the gradient access\nmodel in a bit more detail? This does not seem substantiated currently.\nAuthor response: Thank you for your valuable feedback. We have expanded on this at the end\nof Section II. In short, gradient methods are a special case of SQ algorithms (e.g., Ref. [95] which\nshows that stochastic gradient descent can be simulated using SQs), and the proof of classical\nhardness for gradient methods is intuitively similar to hardness results in the SQ literature.\n- I found the sections of “Introduction” and “Problem Definition” well-written even for an audience\noutside of this subarea.\nAuthor response: Thank you for your positive comments.\n- In lines 57-60, the authors remark that Ref. [80] mention that periodic neurons cannot be learned\nefficiently under distributions with sparse Fourier transform. At first glance, I would have thought\nthat sparsity of the Fourier spectrum would help. Could you please provide some intuition why this\nis not the case?\nAuthor response: Thank you for your question. The distribution being sparse in Fourier space\nimplies that the gradient of the loss function is extremely concentrated around a fixed value,\nindependent of what we want to learn (namely, the vector w⋆). This means that when one attempts\nto learn the target function by minimizing the loss function using classical gradient methods, then\nthe gradients will be very flat and thus not helpful in learning the function. This causes one to\niterate for a very long time in order to find the solution. Perhaps the reviewer is confused that\nsparsity in Fourier space should mean there is a smaller space of viable solutions to search through.\nHowever, classical algorithms generally cannot search through Fourier space efficiently to identify\nwhich elements in Fourier space are nonzero. This is also the source of canonical quantum speedups\nsuch as period finding.\n6/7\n- In lines 87-88, the authors remark that the quantum example state (II.1) is not known to be\nefficiently preparable for all distributions but I could not find a discussion regarding this later except\nfor in lines 1783-1784 but only for d = 1. What about higher values of d that this paper seems to\nmainly care about?\nAuthor response: We apologize for the confusion here. The techniques of Ref. [109] easily\ngeneralize to the case of larger d. We had meant that some other references in the lines mentioned\nonly focus on the d = 1 case or specific distributions. We have removed the phrase “particularly\nfor the d = 1 case” to avoid future confusion.\n- From looking at Corollary 10, it appears to me that you also have an exponential separation in D\n(and not just d) as long as the first term of (E.7) is appropriately bounded. Perhaps, this should be\nmentioned as part of Corollary 1 to indicate that there is an advantage even for d=1 for certain\nregimes. (I might be mistaken here. I did not go through the proof of Corollary 10\ncompletely.)\nAuthor response: Thank you for the comment. We are not quite clear what the reviewer is\nsuggesting. We clarify that the D parameter does not show up in the classical lower bound. Thus,\nalthough our quantum algorithm has only a linear scaling in D, it is difficult to compare to the\nclassical case. Nevertheless, one should really think of D as being a constant since the problem is\nclassically hard even for D = 1.\n7/7"}, {"round": 2, "reviewer_comments": {"reviewer_1": "I would like to thank the authors for the revised manuscript. The authors have addressed most of my previous comments. In particular, the newly added Theorem 2 strengthens the claim of quantum advantage by extending the analysis to a family of correlational SQs.\nThere are, however, a few remaining points that should be addressed before I can recommend the manuscript for publication.\n(1). Proof sketch of Theorem 2: A brief proof sketch of Theorem 2 should be added to the Methods section of the main text. The authors have used a distinct approach to establish this result, and I believe it would greatly benefit readers to include a concise overview of the underlying reasoning.\n(2). Figure 1 revision: Figure 1 should be revised to reflect the setting of Theorem 2. Specifically, incorporating elements related to momentum/etc should suffice.\n(3). Discussion of related literature: I strongly recommend that the authors broaden their discussion of the quantum machine learning literature to include other aspects and clarify how their work connects to prior studies. In particular, the following works should be addressed:\n(3.1). Regarding Molteni et al.", "reviewer_2": "Thank you for the detailed responses. I am happy with the edits made."}, "author_response": "We thank the reviewer for their detailed comments and support. We have addressed the remaining comments below.\n(1). Proof sketch of Theorem 2: A brief proof sketch of Theorem 2 should be added to the Methods\nsection of the main text. The authors have used a distinct approach to establish this result, and I\nbelieve it would greatly benefit readers to include a concise overview of the underlying reasoning.\nAuthor response: We have added a brief sketch of the proof in Section A of the methods. We\nalso sketch the original proof of classical hardness in this new section.\n(2). Figure 1 revision: Figure 1 should be revised to reflect the setting of Theorem 2. Specifically,\nincorporating elements related to momentum/etc should suffice.\nAuthor response: Thank you for the suggestion. In Figure 1(b), we have added that correlational\nstatistical queries also give rise to classical lower bounds.\n(3). Discussion of related literature: I strongly recommend that the authors broaden their discussion\nof the quantum machine learning literature to include other aspects and clarify how their work\nconnects to prior studies. In particular, the following works should be addressed:\n(3.1). Regarding Molteni et al."}]

Decision letter