Timezone: »

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

Thu Jun 13 06:30 PM -- 09:00 PM (PDT) @ Pacific Ballroom #171
in Posters Thu »
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.
Keywords: Clustering · Kernel Methods · Others · Supervised Learning

Author Information

Tongyang Li (University of Maryland)

Dr. Tongyang Li is currently an assistant professor at the Center on Frontiers of Computing Studies, Peking University. Previously he was a postdoctoral associate at the Center for Theoretical Physics, Massachusetts Institute of Technology during 2020-2021. He received Ph.D. degree from the Department of Computer Science, University of Maryland in 2020, and received Bachelor of Engineering from the Institute for Interdisciplinary Information Sciences, Tsinghua University and Bachelor of Science from the Department of Mathematical Sciences, Tsinghua University, both in 2015. Dr. Tongyang Li's research focuses on designing quantum algorithms for machine learning and optimization. In general, he is interested in better understanding about the power of quantum algorithms, including topics such as quantum query complexity, quantum simulation, and quantum walks. He was a recipient of the IBM Ph.D. Fellowship, the NSF QISE-NET Triplet Award, and the Lanczos Fellowship.

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

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

More from the Same Authors