Fast Quantum Algorithms for Learning Linear Threshold Functions

Aleksandrs Krivcenko, Tuyen Nguyen, Ronald de Wolf

Linear threshold functions are $f_{w,\theta }(x)=\text{sign}(⟨x,w⟩-\theta )$, where the weight vector $w\in {\mathbb{R}}^n$ is a unit vector, $\theta \in \mathbb{R}$ is a threshold, and ty…