Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Sublinear quantum algorithms for training linear and kernel-based classifiers
Authors: Tongyang Li, Shouvanik Chakrabarti, Xiaodi Wu
ICML 2019 | Venue PDF | 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 <EMAIL>, Xiaodi Wu <EMAIL>. |
| 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. |