Quantum Density Peak Clustering Algorithm

Zhihao Wu; Tingting Song; Yanbing Zhang

doi:10.3390/e24020237

Quantum Density Peak Clustering Algorithm

Entropy (Basel). 2022 Feb 3;24(2):237. doi: 10.3390/e24020237.

Authors

Zhihao Wu¹, Tingting Song^{2

3}, Yanbing Zhang²

Affiliations

¹ College of Cyber Security, Jinan University, Guangzhou 510632, China.
² College of Information Science and Technology, Jinan University, Guangzhou 510632, China.
³ Guangxi Key Laboratory of Cryptography and Information Security, Guilin 541004, China.

Abstract

A widely used clustering algorithm, density peak clustering (DPC), assigns different attribute values to data points through the distance between data points, and then determines the number and range of clustering by attribute values. However, DPC is inefficient when dealing with scenes with a large amount of data, and the range of parameters is not easy to determine. To fix these problems, we propose a quantum DPC (QDPC) algorithm based on a quantum DistCalc circuit and a Grover circuit. The time complexity is reduced to O(log(N2)+6N+N), whereas that of the traditional algorithm is O(N2). The space complexity is also decreased from O(N·⌈logN&rceil;) to O(⌈logN&rceil;).

Keywords: quantum algorithm; quantum computation; quantum information.

Abstract

Grants and funding