Sublinear quantum algorithms for training linear and kernel-based classifiers
Tongyang Li · Shouvanik Chakrabarti · Xiaodi Wu

Thu Jun 13th 04:25 -- 04:30 PM @ Room 102

We investigate quantum algorithms for classification, a fundamental problem in machine learning, with provable guarantees. Given $n$ $d$-dimensional data points, the state-of-the-art (and optimal) classical algorithm for training classifiers with constant margin by Clarkson et al. runs in $\tilde{O}(n +d)$, which is also optimal in its input/output model. We design sublinear quantum algorithms for the same task running in $\tilde{O}(\sqrt{n} +\sqrt{d})$, a quadratic improvement in both $n$ and $d$. Moreover, our algorithms use the standard quantization of the classical input and generate the same classical output, suggesting minimal overheads when used as subroutines for end-to-end applications. We also demonstrate a tight lower bound (up to poly-log factors) and discuss the possibility of implementation on near-term quantum machines.

Author Information

Tongyang Li (University of Maryland)

Tongyang Li is a Ph.D. candidate at the Department of Computer Science, University of Maryland. He received B.E. from Institute for Interdisciplinary Information Sciences, Tsinghua University and B.S. from Department of Mathematical Sciences, Tsinghua University, both in 2015; he also received a Master degree from Department of Computer Science, University of Maryland in 2018. He is a recipient of the IBM Ph.D. Fellowship and the NSF QISE-NET Triplet Award.

Shouvanik Chakrabarti (University of Maryland College Park)
Xiaodi Wu (University of Maryland)

Related Events (a corresponding poster, oral, or spotlight)