Title: Quantum Clustering with k-Means: a Hybrid Approach Show Chinese title

Title: 量子聚类与k-均值：一种混合方法

Abstract: Quantum computing is a promising paradigm based on quantum theory for performing fast computations. Quantum algorithms are expected to surpass their classical counterparts in terms of computational complexity for certain tasks, including machine learning. In this paper, we design, implement, and evaluate three hybrid quantum k-Means algorithms, exploiting different degree of parallelism. Indeed, each algorithm incrementally leverages quantum parallelism to reduce the complexity of the cluster assignment step up to a constant cost. In particular, we exploit quantum phenomena to speed up the computation of distances. The core idea is that the computation of distances between records and centroids can be executed simultaneously, thus saving time, especially for big datasets. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version, still obtaining comparable clustering results. Show Chinese abstract

Abstract: 量子计算是基于量子理论的一种有前景的范式，用于执行快速计算。 量子算法在某些任务上，包括机器学习，预计在计算复杂度方面将超越其经典对应方法。 在本文中，我们设计、实现并评估了三种混合量子k-Means算法，利用不同程度的并行性。 确实，每个算法逐步利用量子并行性，将聚类分配步骤的复杂度降低到常数成本。 特别是，我们利用量子现象来加速距离的计算。 核心思想是记录与质心之间的距离计算可以同时执行，从而节省时间，尤其是在大数据集的情况下。 我们表明，我们的混合量子k-Means算法比经典版本更高效，同时仍能获得可比较的聚类结果。