Fast Quantum Algorithms for Learning Linear Threshold Functions
Abstract
Linear threshold functions are fw,θ(x)=sign(⟨ x,w ⟩ −θ), where the weight vector w∈ℝn is a unit vector, θ∈ℝ is a threshold, and typically x∈ℝn or x∈{−1,1}n. When θ=0, the LTF is called homogeneous, and we write fw:=fw,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 fw,θ(x) at any x∈ℝn of our choice. We give a quantum algorithm that learns fw,θ up to Euclidean error ε using O(log(n/ε)) membership queries and Õ(n) other gates. Then we have also learned fw,θ up to error O(ε) when x is Gaussian. Classical algorithms need Ω(nlog(1/ε)) queries. 2. A homogeneous LTF fw 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 fw) using O(k1/4) queries. We give an exponential improvement, using O(log k) queries. 3. Suppose we have a unitary U that can produce (discretized) quantum examples under Gaussian measure, corresponding to ∫x √(γn(x))|x⟩ |fw(x)⟩ dx. This is a weaker access model than membership queries. We give a quantum algorithm based on the efficient Hermite transform of Jain et al. to learn homogeneous LTFs fw with error ε under the Gaussian distribution, using O(n1/4/√ε) applications of U and U† and Õ(n2/ε4) other gates.
Related
- A Sharp Noise Threshold for Shor's Quantum Factoring and Discrete Log Algorithms
- Quantum Algorithms for Molecular Response Functions: Resolvent Kernels, Time-Domain Sampling, Query Lower Bounds with Matched Single-Point Calibers, and a Six-Route Comparison
- Quantum algorithms for optimal control: large-scale finite-horizon linear-quadratic regulation
- Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithms
- The Quartic Gap Between Quantum and Dequantized Algorithms for Linear Algebra Is Tight
BibTeX
@misc{krivcenko2026fast,
title = {{Fast Quantum Algorithms for Learning Linear Threshold Functions}},
author = {Aleksandrs Krivcenko and Tuyen Nguyen and Ronald de Wolf},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.40331},
eprint = {2609.40331},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.40331},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Fast Quantum Algorithms for Learning Linear Threshold Functions
AU - Aleksandrs Krivcenko
AU - Tuyen Nguyen
AU - Ronald de Wolf
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2609.40331
UR - https://arxiv.org/abs/2609.40331
AB - Linear threshold functions are f_w,θ(x)=sign(⟨ x,w ⟩ −θ), where the weight vector w∈ℝ^n is a unit vector, θ∈ℝ is a threshold, and typically x∈ℝ^n or x∈{−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 x∈ℝ^n of our choice. We give a quantum algorithm that learns f_w,θ up to Euclidean error ε using O(log(n/ε)) membership queries and Õ(n) other gates. Then we have also learned f_w,θ up to error O(ε) when x is Gaussian. Classical algorithms need Ω(nlog(1/ε)) 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) quantum examples under Gaussian measure, corresponding to ∫_x √(γ_n(x))|x⟩ |f_w(x)⟩ dx. This is a weaker access model than membership queries. We give a quantum algorithm based on the efficient Hermite transform of Jain et al. to learn homogeneous LTFs f_w with error ε under the Gaussian distribution, using O(n^1/4/√ε) applications of U and U^† and Õ(n^2/ε^4) other gates.
ER -