Near-Optimal Quantum Coreset Construction Algorithms for Clustering
Authors: Yecheng Xue, Xiaoyu Chen, Tongyang Li, Shaofeng H.-C. Jiang
ICML 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We give quantum algorithms that find coresets for kclustering in Rd with O(nkd3/2) query complexity. Our coreset reduces the input size from n to poly(kε 1d), so that existing α-approximation algorithms for clustering can run on top of it and yield (1 + ε)α-approximation. This eventually yields a quadratic speedup for various kclustering approximation algorithms. We complement our algorithm with a nearly matching lower bound, that any quantum algorithm must make Ω(nk) queries in order to achieve even O(1)-approximation for k-clustering. |
| Researcher Affiliation | Academia | 1Center on Frontiers of Computing Studies, Peking University, Beijing, China 2School of Electronics Engineering and Computer Science, Peking University, Beijing, China. |
| Pseudocode | Yes | Algorithm 1 Bicriteria Approximation, Algorithm 2 Coreset Construction, Algorithm 3 Multidimensional Quantum Counting |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code or provide links to a code repository for the described methodology. |
| Open Datasets | No | The paper is theoretical, describing algorithms and proving lower bounds for k-clustering in Rd, and does not mention specific datasets used for training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not describe empirical experiments involving dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe empirical experiments, thus there are no hardware specifications for running experiments. |
| Software Dependencies | No | The paper is theoretical and focuses on algorithm design and proofs, and therefore does not list specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe empirical experiments, therefore it does not provide details about an experimental setup, hyperparameters, or training configurations. |