arXiv:2609.40331
Fast Quantum Algorithms for Learning Linear Threshold Functions
Aleksandrs Krivcenko, Tuyen Nguyen, Ronald de Wolf
Abstract
Linear threshold functions (LTFs) are $\{-1,1\}$-valued functions $f_{w,θ}(x)=\text{sgn}(\langle w,x\rangle-θ)$, where $w\in\mathbb R^n$ has unit norm, $θ\in\mathbb R$, and $x\in\mathbb R^n$ or $\{-1,1\}^n$. If $θ=0$, the LTF is homogeneous, denoted $f_w=f_{w,0}$. LTFs are fundamental linear classifiers. We give three results: one for general LTFs and two for homogeneous LTFs. (1) With real-domain membership queries evaluating $f_{w,θ}(x)$ at any chosen $x\in\mathbb R^n$, we learn an LTF with classification error at most $\varepsilon$ under the standard Gaussian distribution using $O(\log(n/\varepsilon))$ queries and $\widetilde{O}(n)$ other gates. Classically, $Ω(n\log(1/\varepsilon))$ queries are required, giving an exponential quantum query speedup. (2) A homogeneous LTF $f_w$ over $\{-1,1\}^n$ whose $k$ nonzero weights are equal and positive is Majority on the support of $w$. We identify this hidden support exactly using $O(\log k)$ queries, exponentially improving Belovs' $O(k^{1/4})$ upper bound. Our algorithm uses $O(n\log n\log k)$ gates and has $O(\log n\log k)$ non-oracle depth. Classical algorithms require $Ω(k\log(n/k))$ queries. (3) Suppose a unitary $U$ prepares discretized Gaussian quantum examples, corresponding to $\int_x\sqrt{γ_n(x)}|x\rangle|f_w(x)\rangle\,dx$. This is weaker than membership queries. Using the efficient quantum Hermite transform circuit, we learn homogeneous LTFs with classification error at most $\varepsilon$ under the Gaussian distribution using $O(n^{1/4}/\sqrt{\varepsilon})$ applications of $U$ and $U^\dagger$ and $\widetilde{O}\!(\frac{n^{5/4}}{\sqrt{\varepsilon}}+\frac{n}{\varepsilon^2})$ other gates. Classically, $Ω(n/\varepsilon)$ examples are needed, giving a quartic quantum speedup in $n$. We show that the quantum query complexities in all three cases are optimal by proving matching lower bounds.
AI Summary
The paper studies quantum learning of linear threshold functions $f_{w,\theta}(x)=\operatorname{sgn}(\langle w,x\rangle-\theta)$ in three oracle models, giving algorithms and matching quantum query lower bounds. With coherent membership queries at real inputs, general halfspaces can be learned to Gaussian classification error $\varepsilon$ using $\Theta(\log(n/\varepsilon))$ queries and $\widetilde O(n)$ non-oracle gates, versus a classical lower bound of $\Omega(n\log(1/\varepsilon))$. The algorithm implements an affine boundary-height function by coherent binary search, then recovers its gradient using Jordan’s algorithm. The lower bound uses a continuous-parameter multiplicative adversary argument. For Boolean membership queries to a Majority function on an unknown support of size at most $k$, exact support recovery takes $\Theta(\log k)$ queries, improving the previous $O(k^{1/4})$ upper bound. The construction uses explicit dual-adversary solutions expressed through Krawtchouk polynomials and a transducer implementation requiring $O(n\log n\log k)$ gates and $O(\log n\log k)$ non-oracle depth. For support size exactly $k$, the matching lower bound assumes $n\geq2k$. For homogeneous halfspaces, access to a discretized Gaussian quantum-example preparation unitary and its inverse gives optimal query complexity $\Theta(n^{1/4}/\sqrt\varepsilon)$, compared with $\Theta(n/\varepsilon)$ classical examples. A quantum Hermite transform isolates high-degree components encoding many copies of the weight state; amplitude amplification and tomography recover the direction. Gate complexity is $\widetilde O(n^{5/4}/\sqrt\varepsilon+n/\varepsilon^2)$. The lower bound combines hypercube testing with a quantum hybrid argument. This model requires inverse access, not merely example-state copies. Extensions to nonzero thresholds in the example model, other symmetric juntas, and polynomial threshold functions remain open.
Finally, GPT-6-Astra and Claude Fable 5.1 were used for help with proofreading.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- v2: In section 3, new optimal lower bound. Small improvements in the presentation v3: Added new optimal lower bounds in Section 3 and 5, added gate complexity upper bound in Section 4, and improved the presentation in several places