Sublinear quantum algorithms for training linear and kernel-based classifiers
Authors: Tongyang Li, Shouvanik Chakrabarti, Xiaodi Wu
ICML 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 (Clarkson et al., 2012) runs in O(n + d)1. We design sublinear quantum algorithms for the same task running in O(pn + 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. |
| Researcher Affiliation | Academia | Tongyang Li 1 Shouvanik Chakrabarti 1 Xiaodi Wu 1 1Department of Computer Science, UMIACS, and Joint Center for Quantum Information and Computer Science, University of Maryland. Correspondence to: Tongyang Li <tongyang@cs.umd.edu>, Xiaodi Wu <xwu@cs.umd.edu>. |
| Pseudocode | Yes | Algorithm 1: Quantum linear classification algorithm. Algorithm 2: Quantum kernel-based classification. |
| Open Source Code | No | The paper focuses on theoretical algorithm design and complexity analysis. It does not provide or link to any open-source code for the described methodology. |
| Open Datasets | No | The paper focuses on theoretical algorithm design for 'n d-dimensional data points' without specifying or providing access to any public datasets for empirical training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not report on empirical experiments with dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and discusses algorithms without reporting on specific hardware used for running experiments. It mentions 'near-term quantum machines' as a future possibility but does not specify hardware for its current work. |
| Software Dependencies | No | The paper is theoretical and does not mention specific software dependencies with version numbers required to replicate the work. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and complexity analysis. It does not describe any experimental setups, hyperparameters, or system-level training settings. |