This quantum algorithm leverages unique quantum properties, primarily related to quantum period finding, to efficiently learn periodic functions over a broad range of non-uniform distributions. The algorithm achieves an exponential quantum advantage over classical gradient-based algorithms, which are standard in machine learning, for learning these functions with Fourier-sparse input distributions such as Gaussian, generalized Gaussian, and logistic distributions.

Here's how the quantum algorithm leverages unique quantum properties:

• Quantum Statistical Queries (QSQs) for Accessing Function Information: The algorithm operates in the QSQ model, which provides access to the target function $g_{w^\star}$ through queries that return approximations of expectation values involving a quantum example state $|g_{w^\star}\rangle$. This quantum access model is crucial for implementing quantum algorithms for learning.

• Quantum Fourier Transform (QFT) for Period Finding: A key step in the algorithm is to perform period finding to learn the unknown vector $w^\star$ that defines the linear component within the periodic function $g_{w^\star}(x) = g(x^\top w^\star)$. The algorithm encodes the QFT into QSQs to estimate the frequencies present in the function, which are directly related to the inverse of the periods. This ability to efficiently analyze the frequency components is a hallmark of quantum algorithms like Shor's algorithm and its generalizations.

• Handling Non-Integer and Real Periods with Hallgren's Algorithm: Unlike standard period finding algorithms that typically require integer periods, the periods $1/|w_j^\star|$ are not necessarily integers. The algorithm adapts Hallgren's algorithm for finding the period of pseudoperiodic functions, which can handle potentially irrational periods. This is a significant advantage over classical methods that might struggle with non-commensurate frequencies. The algorithm also generalizes Hallgren's approach to work with non-uniform distributions.

• Pseudoperiodicity for Discretization of Real-Valued Functions: Since the target functions are real-valued, they need to be discretized to be represented in a quantum state. The algorithm carefully chooses a discretization that satisfies pseudoperiodicity, a weaker condition than strict periodicity, which ensures that the discretized function still retains information about the period of the original continuous function. This addresses a challenge where naive discretization could eliminate crucial information about the period.

• New Period Finding Algorithm for Non-Uniform Distributions: Hallgren's algorithm is originally designed for uniform superpositions. The presented work develops a new period finding algorithm that is specifically tailored to work with sufficiently flat non-uniform input distributions, including Gaussians, generalized Gaussians, and logistic distributions. This is crucial because many real-world datasets follow non-uniform distributions, and achieving quantum advantage in such settings is a key open question in quantum learning theory. The "sufficiently flat" condition allows the algorithm to generalize beyond the idealized uniform distribution case.

• Quantum Advantage over Gradient-Based Classical Algorithms: The classical hardness results show that any gradient-based classical algorithm requires an exponential number of iterations (gradient samples) in the dimension of the problem and the norm of $w^\star$ to learn these periodic neurons, especially when the input data distribution has a sufficiently sparse Fourier transform. The quantum algorithm, by leveraging the QFT for efficient frequency estimation, achieves the same task with a polynomial number of QSQs and gradient descent iterations, thus demonstrating an exponential quantum advantage. The classical difficulty stems from the objective function being sparse in Fourier space, leading to barren plateaus that hinder gradient-based optimization.