改进版的 q-means 量子算法和 dequantized 算法，分别以 O ((k^2)/(ε^2)(√k*d + log (Nd))) 和 O ((k^2)/(ε^2)(kd + log (Nd))) 的时间复杂度在近似 k-means 聚类中取得优化，其中 k 代表簇数量，ε 代表误差率，N 代表向量数量，d 代表向量维度。

Aug, 2023

我们给出了在 QRAM 模型中，对于经典 k - 均值聚类问题的量子逼近方案（即对于每个 ε>0，具有（1+ε）- 逼近），其运行时间只有数据点数量的对数多项式依赖。具体而言，对于存储在 QRAM 数据结构中的包含 N 个在 R^d 中的点的数据集 V，我们的量子算法以时间 Γ(O)((2^(Γ(O)(k/ε)))η^2d) 运行，并且以高概率输出一个包含 k 个中心的集合 C，其中 cost (V, C) ≤ (1+ε)・cost (V, C_OPT)。这是第一个具有对 k - 均值问题具有（1+ε）可证逼近保证且具有多项式对数运行时间的量子算法。此外，与先前的无监督学习方法不同，我们的量子算法不需要量子线性代数子程序，并且其运行时间与出现在这些过程中的参数（例如条件数）无关。

Aug, 2023

本文提出了适用于聚类分配和聚类查找的有监督和无监督的量子机器学习算法，利用量子计算能够处理高维向量的优势，实现了对于大量向量的分类问题的指数级加速。

Jul, 2013

本文通过基于 k-means 算法的量子聚类算法，提出了一种基于量子 EM 算法的高斯混合模型算法，证明了该算法的鲁棒性和量子加速优势以及 GMM 在非平凡聚类数据中的优势。

Aug, 2019

本文提出一种量子支持向量机分类器模型，实现有监督分类并取得了明显的量子加速，要求仅具备经典数据访问能力。在构造的数据集中，基于普遍认为的离散对数问题的困难性假设，该量子分类器实现的分类效果均优于无法逆多项式地超越瞎猜的经典学习器。这个模型可以通过一个容错的量子计算机来估算内积核函数，并且将数据映射为一个量子特征空间。此外，该分类器对由有限采样误差产生的内积核函数的加性误差具有一定的鲁棒性。

Oct, 2020

利用量子计算机和贝叶斯优化方法加速解决无监督学习中的聚类问题，并展示出在噪声环境下稳健的表现和经典优化方法的适用性。

Dec, 2017

通过引入 QUACK 算法，我们提出了一个时间复杂度线性缩放的量子内核算法，能够在训练过程中表现与经典内核方法相似的性能，并且可以处理高维数据集。

May, 2024

本文介绍了几种量子算法，用于执行最近邻学习，核心是计算距离度量，如内积和欧氏距离。证明量子算法比对应的经典算法具有多项式降低的查询复杂度。在某些情况下，证明具有指数甚至超指数降低。研究了这些算法在几个二元分类任务上的性能，并发现分类准确性与经典方法具有竞争力。

Jan, 2014

我们提出了首个适用于 AQC 的聚类问题形式，该方法在当前量子计算机代际已经可解，并通过使用整数规划求解器与现有的基于优化的方法相比具有竞争力。

Sep, 2023

该研究在量子计算的框架下，提出了一种在时空复杂度上具有优势的 k - 聚类问题的量子算法，并在算法的基础上得到了一个核心集。

Jun, 2023