It is getting harder to deal with the large data sets by the classical hierarchical clustering algorithm, so we propose an efficient quantum hierarchical clustering algorithm, in which the quantum bit (qubit) is used to represent the data point in the space.For quantum entanglement, the distance between two data points is calculated through adding an auxiliary particle to construct the entangled state.Then a projective measurement is performed on the auxiliary particle alone.The distance between two points is acquired by the projective measurement.We use the distance of the cluster centroids as a measure of similarity between clusters.Also, based on the principle of the minimum cluster centroids distance, the nearest two clusters are merged.We aim at improving time and space complexity and effect of the clustering of the hierarchical clustering algorithm.
It is getting harder to deal with the large data sets by the classical hierarchical clustering algorithm, so we propose an efficient quantum hierarchical clustering algorithm, in which the quantum bit (qubit) is used to represent the data point in the space.For quantum entanglement, the distance between two data points is calculated through adding an auxiliary particle to construct the entangled state.Then a projective measurement is performed on the auxiliary particle alone.The distance between two points is acquired by the projective measurement.We use the distance of the cluster centroids as a measure of similarity between clusters.Also, based on the principle of the minimum cluster centroids distance, the nearest two clusters are merged.We aim at improving time and space complexity and effect of the clustering of the hierarchical clustering algorithm.
Traditional clustering algorithms, such as k-means and DBSCAN, often face significant challenges when applied to big data. The computational complexity associated with distance calculations and nearest neighbor searches scales poorly with dataset size, limiting their effectiveness. This paper proposes a novel approach to clustering inspired by quantum measurement theory, specifically quantum-inspired nearest neighbor search. We leverage concepts from quantum mechanics, such as superposition and measurement, to design clustering algorithms that can efficiently identify clusters within high-dimensional datasets. The core idea is to treat the clustering problem as a measurement process, where candidate cluster centers are repeatedly measured against data points, and the most likely cluster centers are selected. The resulting algorithms aim to provide scalability improvements over conventional methods, particularly for datasets with a large number of features and data points. The effectiveness of the proposed algorithms is demonstrated through theoretical analysis and conceptual explanations, highlighting the potential benefits and future research directions.
Abstract Quantum state clustering provides a powerful tool for quantum information processing. This paper focuses on the classification of single-qubit pure and mixed states via clustering algorithms, and discovers that the classical K -means algorithm has two limitations in clustering quantum states: the Euclidean distance cannot accurately reflect the similarity between quantum states, and the centroid update based on the arithmetic mean frequently fails to yield valid quantum states. To address these issues, we propose two distance metrics for quantum states: the dynamic distance and the Bloch distance, and adopt the K -medoids method to update the centroid, ensuring that the cluster center always remains a valid quantum state, thereby designing a quantum-data-adaptive clustering algorithm. Experimental results show that the dynamic distance achieves a clustering accuracy as high as 91.4 % , but at the cost of higher computational complexity. In contrast, the Bloch distance significantly reduces computational complexity while maintaining clustering performance comparable to that of the dynamic distance, achieving a clustering accuracy of 87.4 % . This paper provides a practical method for achieving efficient and reliable clustering of single-qubit quantum states.
As an important branch of machine learning, clustering analysis is widely used in some fields, e.g., image pattern recognition, social network analysis, information security, and so on. In this paper, we consider the designing of clustering algorithm in quantum scenario, and propose a quantum hierarchical agglomerative clustering algorithm, which is based on one dimension discrete quantum walk with single-point phase defects. In the proposed algorithm, two nonclassical characters of this kind of quantum walk, localization and ballistic effects, are exploited. At first, each data point is viewed as a particle and performed this kind of quantum walk with a parameter, which is determined by its neighbors. After that, the particles are measured in a calculation basis. In terms of the measurement result, every attribute value of the corresponding data point is modified appropriately. In this way, each data point interacts with its neighbors and moves toward a certain center point. At last, this process is repeated several times until similar data points cluster together and form distinct classes. Simulation experiments on the synthetic and real world data demonstrate the effectiveness of the presented algorithm. Compared with some classical algorithms, the proposed algorithm achieves better clustering results. Moreover, combining quantum cluster assignment method, the presented algorithm can speed up the calculating velocity.
Quantum game is an analogy of classical game.Using the quantum entanglement,game players interact with each other implicitly,and the game will result in a different way.Quantum game was applied to clustering.A clustering algorithm based on quantum game and grid was proposed where data points are regarded as players.By embeding distance function into payoff matrix,similar data points can get more payoff,and clusters will be formed in that way.In addition,a rule about merging grid was designed to simplify the game.Simulations show the clustering quality of this algorithm is superior to K-means etc.At last,several parameters in this algorithm were discussed and some recommendations about parameters selection were provided.
Quantum machine learning, though in its initial stage, has demonstrated its potential to speed up some of the costly machine learning calculations when compared to the existing classical approaches. Among the challenging subroutines, computing distance between with the large and high-dimensional data sets by the classical k-medians clustering algorithm is one of them. To tackle this challenge, this paper proposes an efficient quantum k-medians clustering algorithm using the powerful quantum Euclidean estimator algorithm. The proposed quantum k-medians algorithm has provided an exponential speed up as compared to the classical version of it. If and only if we allow the input and the output vectors to be quantum states. The proposed algorithm implementation handled in python with the help of third-party module known as QISKit. The implemented quantum algorithm was executed on the IBM Quantum simulators through cloud. The results from the experiment and simulation suggest that quantum distance estimator algorithms could give benefits for other distance-based machine learning algorithms like k-nearest neighbor classification, support vector machine, hierarchical clustering and k-means clustering. This work sheds light on the bright future of the age of big data making use of exponential speed up provided by quantum theory.
This paper investigates the application of quantum algorithms to enhance clustering performance on big data. Traditional clustering algorithms often struggle with the computational complexity associated with large datasets and intricate data distributions. We propose and analyze the implementation of quantum k-means and quantum hierarchical clustering algorithms, leveraging quantum superposition and entanglement to potentially achieve significant speedups. The theoretical framework outlines the core concepts and mathematical formulations of these algorithms. We explore the potential for quantum algorithms to address the limitations of classical approaches, particularly in scenarios involving high-dimensional data and complex clusters. The research focuses on the algorithmic design, examining the key steps involved in transforming classical clustering problems into quantum computations. This work contributes to the emerging field of quantum data mining and provides a foundational understanding of how quantum computing can revolutionize data analysis tasks. The primary focus is on the theoretical aspects of quantum clustering and does not include experimental validation.