Abstract: A quantum K-means algorithm without quantum random access memory (QRAM) is proposed by combining K-means algorithm and angle encoding technology. This algorithm makes use of parallel quantum operations and can complete data loading with only logarithmic time complexity. And by preprocessing the input data, the parameter threshold of the data components is determined, so the problem of different characteristic scales of samples can be solved according to the algorithm. The main body of the algorithm consists of four main steps: coding data, similarity measurement, quantum minimum search and centroid iterative update. The operators and circuit construction involved in these steps are described in detail. Numerical experiments based on the proposed circuit show that the results of the proposed algorithm are consistent with the classical prediction results, verifying the reliability of the quantum Kmeans algorithm combined with parameters. In addition, theoretical analysis shows that the proposed algorithm has square acceleration in running time compared with the classical algorithms.

Key words: quantum optics, quantum K-means algorithm, angle encoding, quantum phase estimation; multi-qubits swap-test