Laura Lewis
@laura-lewis.bsky.social
Quantum Information
PhD Student at UC Berkeley
Previous Marshall Scholar (CS ‘25 at Edinburgh, Math ‘24 at Cambridge)
Previously Math + CS Undergrad at Caltech ‘23
PhD Student at UC Berkeley
Previous Marshall Scholar (CS ‘25 at Edinburgh, Math ‘24 at Cambridge)
Previously Math + CS Undergrad at Caltech ‘23
Thus, we prove an exponential quantum advantage over classical gradient methods for this problem.
Many challenges arise from discretization (which can destroy the structure of our functions) and non-uniformity, so check out the paper!
Many challenges arise from discretization (which can destroy the structure of our functions) and non-uniformity, so check out the paper!
March 28, 2025 at 9:14 PM
Thus, we prove an exponential quantum advantage over classical gradient methods for this problem.
Many challenges arise from discretization (which can destroy the structure of our functions) and non-uniformity, so check out the paper!
Many challenges arise from discretization (which can destroy the structure of our functions) and non-uniformity, so check out the paper!
Classically, this is proven to be exponentially hard for any classical algorithm using gradient info, which are the workhorse algos for ML 💪
There are also hardness results in other regimes for SQ algorithms and even general classical algos learning under small noise.
There are also hardness results in other regimes for SQ algorithms and even general classical algos learning under small noise.
March 28, 2025 at 9:14 PM
Classically, this is proven to be exponentially hard for any classical algorithm using gradient info, which are the workhorse algos for ML 💪
There are also hardness results in other regimes for SQ algorithms and even general classical algos learning under small noise.
There are also hardness results in other regimes for SQ algorithms and even general classical algos learning under small noise.
We address this gap by designing an efficient quantum algorithm for learning periodic neurons (composition of periodic and linear function) over a broad class of non-uniform distributions.
This is also the first result for in quantum learning of classical real-valued functions.
This is also the first result for in quantum learning of classical real-valued functions.
March 28, 2025 at 9:14 PM
We address this gap by designing an efficient quantum algorithm for learning periodic neurons (composition of periodic and linear function) over a broad class of non-uniform distributions.
This is also the first result for in quantum learning of classical real-valued functions.
This is also the first result for in quantum learning of classical real-valued functions.
Previous works proved exponential sample complexity advantages for other function classes when given uniformly distributed data. 🙂
In contrast, for adversarial distributions, there is no advantage in general. 😕
What about for non-uniform distributions 📊?
In contrast, for adversarial distributions, there is no advantage in general. 😕
What about for non-uniform distributions 📊?
March 28, 2025 at 9:14 PM
Previous works proved exponential sample complexity advantages for other function classes when given uniformly distributed data. 🙂
In contrast, for adversarial distributions, there is no advantage in general. 😕
What about for non-uniform distributions 📊?
In contrast, for adversarial distributions, there is no advantage in general. 😕
What about for non-uniform distributions 📊?