Aug, 2023

k-Means 的量子逼近方案

PDF
TL;DR我们给出了在 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+ε）可证逼近保证且具有多项式对数运行时间的量子算法。此外，与先前的无监督学习方法不同，我们的量子算法不需要量子线性代数子程序，并且其运行时间与出现在这些过程中的参数（例如条件数）无关。
发现论文，激发创造
  • q-means：一种用于无监督机器学习的量子算法

    本研究介绍了 q-means 算法，一种用于聚类的新型量子算法，该算法具有与 $k$-means 类似的收敛性和精度保证，并且输出 $k$ 个集群中心的好近似值。此算法的运行时间呈多项式级别，优于经典算法，尤其适用于大型数据集。

    Dec, 2018

  • 你知道什么是 q-means 吗？

    改进版的 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

  • 针对聚类问题的近优量子核心集构建算法

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

    Jun, 2023

  • 欧几里得 k - 均值问题的近似难度

    本研究采用图谱分析的方法，证明了欧几里得 k-means 问题的近似难度对于所有的 k 和 d 都是 NP 难的，同时发现当前最佳难度结果可以被推广到三角免费图中。

    Feb, 2015

  • 一种基于量子启发式思想的经典推荐系统算法

    通过使用简单例程来操纵 $\ell^2$ -norm 抽样分布，并提供一个给定数据结构的算法来生成从矩阵秩 - $k$ 近似值的 $\ell^2$ -norm 样本，本研究为 Kerenidis 和 Prakash 的量子推荐系统提供了古典类比，进一步证明此算法并未超越经典算法；此外，尽管假定输入数据重程度较大，但我们的经典推荐系统与先前线性 m 和 n 时间运行的经典系统相比能够在指数上更快地产生推荐。

    Jul, 2018

  • 局部搜索在双倍指标下为 k-Means 提供 PTAS

    使用局部搜索启发式策略，本文证明了在任何固定维度的欧几里得空间中，k-means 问题均可提供 PTAS。

    Mar, 2016

  • 量子变分和量子启发式聚类

    本研究提出了一种基于变分量子电路的量子算法，用于对数据进行聚类；该算法可以将数据分类为多个聚类，并且可以在少量量子比特的嘈杂中间量子计算设备上轻松实现。

    Jun, 2022

  • 离散几何空间中鲁棒聚类的参数化逼近

    本文介绍了 Robust k-z 聚类和其在度量空间、算法公平性、欧几里得空间和 FPT 近似等领域的应用，提出了相应的算法，其中在特殊的欧几里得空间中得到了较好的近似结果。

    May, 2023

  • 用于训练线性和基于内核分类器的次线性量子算法

    我们设计了基于量子算法的子线性算法，用于分类问题和矩阵零和游戏问题的求解，其复杂度都是量级上界的平方根，相较现有技术有瓶颈的常数。我们的算法生成与传统算法完全相同的结果，推荐用于端到端应用，同时探讨了实现方式以及机器可达到的限制。

    Apr, 2019

  • 近线性时间内对倍增度量聚类的近似算法

    针对度量空间中的经典设施定位、$k$- 中位数和 $k$- 均值问题，我们提供了近线性时间的逼近方案，并展示了针对各种变型问题的技术扩展。

    Dec, 2018