{"id":"arxiv/2609.40331","url":"https://arxiv.org/abs/2609.40331","tags":["quant-ph"],"score":0,"title":"Fast Quantum Algorithms for Learning Linear Threshold Functions","domain":"quant-ph","source":"arxiv","authors":["Aleksandrs Krivcenko","Tuyen Nguyen","Ronald de Wolf"],"reviews":0,"subject":"quant-ph","summary":"Linear threshold functions are $f_{w,θ}(x)=\\text{sign}(\\langle x,w \\rangle -θ)$, where the weight vector $w\\in\\mathbb{R}^n$ is a unit vector, $θ\\in\\mathbb R$ is a threshold, and typically $x\\in\\mathbb{R}^n$ or $x\\in\\{-1,1\\}^n$. When $θ=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,θ}(x)$ at any…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-30","reactions":{}}