Search

Traditional k-means algorithm measures the Euclidean distance between any two data points, but it is not applicable in many scenarios, such as the path information between two cities, or when there are some obstacles between two data points. To solve the problems, we propose a quantum k-means algorithm based on Manhattan distance (QKMM). The main two steps of the QKMM algorithm are calculating the distance between each training vector and k cluster centroids, and choosing the closest cluster centroid. The quantum circuit is designed, and the time complexity is O (log (N d) + 2 n + k) , where N is number of training vectors, d is number of features for each training vector, n is number of bits for each feature, and k is the number of clustering classes. Different from other quantum k-means algorithms, our algorithm has wide applications and reduces the complexity. Compared with classical k-means algorithm, our algorithm reaches quadratic speedup. [ABSTRACT FROM AUTHOR]

With the rapid growth of video and image technology, the binary classification of matrices has attracted much attention. In 2017, Duan et al. proposed a quantum algorithm for support matrix machines (QSMM) that efficiently addresses image classification problems. The QSMM consists of two core subroutines: an HHL algorithm and a quantum singularity threshold (QSVT) algorithm with complexities of O κ 3 ϵ - 3 log (N m n) and O log (m n) , respectively, where κ is the condition number of the corresponding matrix of the HHL algorithm, ϵ is the expected accuracy of the output state, N is the number of samples in the training set and mn is the size of the feature space. The QSMM achieves an exponential increase in speed over classical counterparts. However, we find that Duan's QSMM can be improved by applying an improved quantum matrix inversion (QMI) algorithm instead of the HHL algorithm. Compared with that of Duan's QSMM, the dependence on precision of our improved QSMM (IQSMM) is exponentially improved, and the complexity of our first subroutine is as low as O [ κ 2 log 1.5 (κ / ϵ) log (N m n) ] . [ABSTRACT FROM AUTHOR]

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 D i s t C a l c circuit and a Grover circuit. The time complexity is reduced to O (log (N 2) + 6 N + N) , whereas that of the traditional algorithm is O (N 2) . The space complexity is also decreased from O (N · ⌈ log N ⌉) to O (⌈ log N ⌉) . [ABSTRACT FROM AUTHOR]