  We analyze the computational complexity of Quantum Sparse Support Vector
Machine, a linear classifier that minimizes the hinge loss and the $L_1$ norm
of the feature weights vector and relies on a quantum linear programming solver
instead of a classical solver. Sparse SVM leads to sparse models that use only
a small fraction of the input features in making decisions, and is especially
useful when the total number of features, $p$, approaches or exceeds the number
of training samples, $m$. We prove a $\Omega(m)$ worst-case lower bound for
computational complexity of any quantum training algorithm relying on black-box
access to training samples; quantum sparse SVM has at least linear worst-case
complexity. However, we prove that there are realistic scenarios in which a
sparse linear classifier is expected to have high accuracy, and can be trained
in sublinear time in terms of both the number of training samples and the
number of features.
