 |
ML Newsnew | past | best | rss | submit | about |
| Quantum advantage for learning shallow NNs with natural data distributions (arxiv.org) | |
| 1 point by westurner on Mar 31, 2025 | hide | past | pdf | 2 comments on HN | |
|
In plain words: A quantum algorithm learns periodic neurons—the wavy building blocks of shallow neural networks—from real-valued data spread across non-uniform, natural-looking inputs. It needs exponentially fewer questions about the data than classical gradient training and other classical query methods, which are proven stuck on this task. Abstract · Quantum advantage for learning shallow neural networks with natural data distributionsWithout 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. | |
| add comment on HN |
|
NewsArticle: "Google Researchers Say Quantum Theory Suggests a Shortcut for Learning Certain Neural Networks" (2025) https://thequantuminsider.com/2025/03/31/google-researchers-... :
> Using this model, [Quantum Statistical Query (QSQ) learning,] the authors design a two-part algorithm. First, the quantum algorithm finds the hidden period in the function using a modified form of quantum Fourier transform — a core capability of quantum computers. This step identifies the unknown weight vector that defines the periodic neuron. In the second part, it applies classical gradient descent to learn the remaining parameters of the cosine combination. The algorithm is shown to require only a polynomial number of steps, compared to the exponential cost for classical learners. [...]
> The researchers carefully address several technical challenges. For one, real-valued data must be discretized into digital form to use in a quantum computer.
Quantum embedding:
> Another way to put this: real-world numbers must be converted into digital chunks so a quantum computer can process them. But naive discretization can lose the periodic structure, making it impossible to detect the right signal. The authors solve this by designing a pseudoperiodic discretization. This approximates the period well enough for quantum algorithms to detect it.
> They also adapt an algorithm from quantum number theory called Hallgren’s algorithm to detect non-integer periods in the data. While Hallgren’s method originally worked only for uniform distributions, the authors generalize it to work with “sufficiently flat” non-uniform distributions like Gaussians and logistics, as long as the variance is large enough.