1（Jiangsu Key Laboratory of Meteorological Observation and Information Processing，Nanjing University of Information Science and Technology，Nanjing 210044，China)2（Jiangsu Technology and Engineering Center of Meteorological Sensor Network，Nanjing University of Information Science and Technology，Nanjing 210044，China)3（School of Computer and Software，Nanjing University of Information Science & Technology，Nanjing 210044，China)
Abstract：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.
2017, Vol. 38 
