Fast Quantum Algorithms for Learning Linear Threshold Functions

Abstract:Linear threshold functions are $f_{w,\theta}(x)=\text{sign}(\langle x,w \rangle -\theta)$, where the weight vector $w\in\mathbb{R}^n$ is a unit vector, $\theta\in\mathbb R$ is a threshold, and typically $x\in\mathbb{R}^n$ or $x\in\{-1,1\}^n$. When $\theta=0$, the LTF is called homogeneous, and we write $f_w:=f_{w,0}$. Such functions are among the most important objects in machine learning, since they serve to linearly discriminate positive and negative examples. We give three positive results about learning LTFs: 1. Suppose we can make real-domain queries, meaning we can compute $f_{w,\theta}(x)$ at any $x\in\mathbb{R}^n$ of our choice. We give a quantum algorithm that learns $f_{w,\theta}$ up to Euclidean error~$\epsilon$ using $O(\log(n/\epsilon))$ membership queries and $\widetilde{O}(n)$ other gates. Then we have also learned $f_{w,\theta}$ up to error $O(\epsilon)$ when $x$ is Gaussian. Classical algorithms need $\Omega(n\log(1/\epsilon))$ queries. 2. A homogeneous LTF $f_w$ on domain $\{-1,1\}^n$ where $w$ has only $k$ nonzero entries of the same value, is the Majority function on the support of $w$. Belovs gave a bounded-error quantum algorithm that identifies the hidden support exactly (and hence learns $f_w$) using $O(k^{1/4})$ queries. We give an exponential improvement, using $O(\log k)$ queries. 3. Suppose we have a unitary $U$ that can produce (discretized) \emph{quantum examples} under Gaussian measure, corresponding to $\int_x \sqrt{\gamma_n(x)}|x\rangle |f_w(x)\rangle dx$. This is a weaker access model than membership queries. We give a quantum algorithm based on the efficient \emph{Hermite transform} of Jain et al.\ to learn homogeneous LTFs~$f_w$ with error~$\epsilon$ under the Gaussian distribution, using $O(n^{1/4}/\sqrt{\epsilon})$ applications of $U$ and $U^\dagger$ and $\widetilde{O}(n^2/\epsilon^4)$ other gates.

arXiv:2609.40331 [quant-ph]

(or arXiv:2609.40331v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2609.40331 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.