一种基于最小距离的量子k-means算法

Quantum K-means Algorithm Based on the Minimum Distance

k-means算法以其简单和快速的特点而被广泛地应用,但其计算复杂度随着数据维数呈指数级增长.通过采用量子比特来表示空间中的点,提出一个高效的基于距离最小化原则的量子k-means算法,相比经典k-means算法,该算法能够带来指数级加速.为了计算待分类点与聚类中心之间距离,通过增加一个辅助粒子构造聚类中心与待分类点的纠缠态,并对辅助粒子进行投影测量,进而依据测量结果计算出两点之间距离.算法的目的是将待分类的点按距离最小原则分到相应的聚类中.算法中,需随机选择k个点作为初始聚类中心,在接下来的迭代过程中,不断地更新聚类中心,直到聚类中心不再变化或小于指定的阈值,则迭代结束.

The k-means algorithm is widely used because of its rapidity and the simplicity, but its computational complexity grows exponentially with the dimension of the data. Taking quantum bits （ i. e. , qubits ） to represent a data point in space, a novel and efficient algorithm, called Quantum k-means algorithm, based on the principle of distance minimization is proposed. Compared with classical k- means algorithm, the proposed algorithm can bring the exponential speed-up. In order to evaluate the distance between the points to be classified and the centroids of clusters： First to construct the entanglement state of the centroid of cluster and the point to be classified, an auxiliary particle is adjoined. Second, a projective measurement is performed on the auxiliary particle alone. And then the distance between two points based on the result of measurement will be calculated. The goal of the algorithm is to classify the points to be classified to the corresponding clustering according to the minimum distance. In algorithm, k points as the initial cluster centers are selected. In the following iteration, the cluster centers are constantly updated until they are not changed or less than the specified threshold. Then the iteration is over.