Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Computers, materials & continua/Computers, materials & continua (Print)

Quantum Hierarchical Agglomerative Clustering Based on One Dimension Discrete Quantum Walk with Single-Point Phase Defects

Gongde Guo, Kai Yu, Hui Wang, Song Lin, Yongzhen Xu, Xiaofeng Chen

Published Jan 1, 2020• 2 citations
Publisher

Abstract

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.

DOI
10.32604/cmc.2020.011399

Related papers

A study and analysis of a discrete quantum walk-based hybrid clustering approach using d-regular bipartite graph and 1D lattice

Sanjay Chakraborty, Soharab Hossain Shaikh, Sudhindu Bikash Mandal +2 more

Traditional machine learning shares several benefits with quantum information processing field. The study of machine learning with quantum mechanics is called quantum machine learning. Data clustering is an important tool for machine learning where quantum computing plays a vital role in its inherent speed up capability. In this paper, a hybrid quantum algorithm for data clustering (quantum walk-based hybrid clustering (QWBHC)) is introduced where one-dimensional discrete time quantum walks (DTQW) play the central role to update the positions of data points according to their probability distributions. A quantum oracle is also designed and it is mainly implemented on a finite [Formula: see text]-regular bipartite graph where data points are initially distributed as a predefined set of clusters. An overview of a quantum walk (QW) based clustering algorithm on 1D lattice structure is also introduced and described in this paper. In order to search the nearest neighbors, a unitary and reversible DTQW gives a quadratic speed up over the traditional classical random walk. This paper also demonstrates the comparisons of our proposed hybrid quantum clustering algorithm with some state-of-the-art clustering algorithms in terms of clustering accuracy and time complexity analysis. The proposed quantum oracle needs [Formula: see text] queries to mark the nearest data points among clusters and modify the existing clusters. Finally, the proposed QWBHC algorithm achieves [Formula: see text] performance.

International Journal of Quantum Information•Mar 1, 2019•5 citations

Quantum Hierarchical Clustering Algorithm Based on the Nearest Cluster Centroids Distance

Fengbo Kong, Hong Lai, Hailing Xiong

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.

International Journal of Machine Learning and Computing•Oct 1, 2017•2 citations

A Novel Clustering Algorithm Based on Quantum Random Walk

Qiang Li, Yan Li He, Jiang Jing-ping

The enormous successes have been made by quantum algorithms during the last decade. In this paper, we combine the quantum random walk (QRW) with the problem of data clustering, and develop two clustering algorithms based on the one dimensional QRW. Then, the probability distributions on the positions induced by QRW in these algorithms are investigated, which also indicates the possibility of obtaining better results. Consequently, the experimental results have demonstrated that data points in datasets are clustered reasonably and efficiently, and the clustering algorithms are of fast rates of convergence. Moreover, the comparison with other algorithms also provides an indication of the effectiveness of the proposed approach.

arXiv:0812.1357•Dec 7, 2008•0 citations

Quantum-Inspired Clustering Algorithms for Big Data

Jincheng Zhang

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.

•Aug 31, 2026•0 citations

Resonance transmission of one-dimensional quantum walk with phase defects

Wang Dan-Dan, Zhi-Jian Li

In this paper, the resonance transmission of discrete time quantum walk is studied when it walks on one-dimensional lattice in which two-phase defects or a piece of phase defects exists. The quasi energy of discrete time quantum walk has a unique dispersion relation with the momentum, from which we first discuss the wave velocity direction versus the values of momentum, and distinguish the incident wave and the reflected wave. The gap between two energy bands depends on the parameters of coincident operator, so the phase defects, which break down the translation invariance of quantum walk on uniform lattices, can be regarded as an analogue of quantum potential. Then we use the condition of energy conversion at the boundary points to obtain the transmission rate and discuss its variation with the incident momentum for different strengths and widths of defects in detail. The multiple resonant peaks are observed due to the enhanced interference effect. Different resonant behaviors are shown when the strength of defect is less or greater than /2, correspondingly the resonances occur in a wide region of incident momentum or the sharp resonant peaks appear at discrete values of momentum. Under the condition of strong defect strength, i.e., approaching to , the qualitative relation between the number of resonant peaks and the widths of defect region is given. The number of resonant peaks is 2(N-1) when the two phase defects are located at N sites symmetric about the origin, while the number is 2N when a piece of phase defects is located at -N to N sites. In the case of a piece of phase defects, we also present the phase diagram in parameter space of (k, ) to show the discrete time of quantum walk propagating or tunneling through the defect region. In terms of this phase diagram, the variations of transmission rate with the incident momentum are reasonably explained. One special phenomenon is that the quantum walk is almost totally reflected in the tunneling case except for =/2 and k being slightly off -/2. Moreover, this behavior seems little affecting the defect strength, just similar to a classical particle. As a result of this research, we hope to deepen the insight of the quantum walk and provide methods to control the spreading of quantum walk through artificial defects.

Acta Physica Sinica•Jan 1, 2016•1 citation

Clustering Algorithm Based on Quantum Game and Grid

Huang De-ca

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.

•Jan 1, 2014•1 citation
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.
Traditional machine learning shares several benefits with quantum information processing field. The study of machine learning with quantum mechanics is called quantum machine learning. Data clustering is an important tool for machine learning where quantum computing plays a vital role in its inherent speed up capability. In this paper, a hybrid quantum algorithm for data clustering (quantum walk-based hybrid clustering (QWBHC)) is introduced where one-dimensional discrete time quantum walks (DTQW) play the central role to update the positions of data points according to their probability distributions. A quantum oracle is also designed and it is mainly implemented on a finite [Formula: see text]-regular bipartite graph where data points are initially distributed as a predefined set of clusters. An overview of a quantum walk (QW) based clustering algorithm on 1D lattice structure is also introduced and described in this paper. In order to search the nearest neighbors, a unitary and reversible DTQW gives a quadratic speed up over the traditional classical random walk. This paper also demonstrates the comparisons of our proposed hybrid quantum clustering algorithm with some state-of-the-art clustering algorithms in terms of clustering accuracy and time complexity analysis. The proposed quantum oracle needs [Formula: see text] queries to mark the nearest data points among clusters and modify the existing clusters. Finally, the proposed QWBHC algorithm achieves [Formula: see text] performance.
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.
The enormous successes have been made by quantum algorithms during the last decade. In this paper, we combine the quantum random walk (QRW) with the problem of data clustering, and develop two clustering algorithms based on the one dimensional QRW. Then, the probability distributions on the positions induced by QRW in these algorithms are investigated, which also indicates the possibility of obtaining better results. Consequently, the experimental results have demonstrated that data points in datasets are clustered reasonably and efficiently, and the clustering algorithms are of fast rates of convergence. Moreover, the comparison with other algorithms also provides an indication of the effectiveness of the proposed approach.
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.
In this paper, the resonance transmission of discrete time quantum walk is studied when it walks on one-dimensional lattice in which two-phase defects or a piece of phase defects exists. The quasi energy of discrete time quantum walk has a unique dispersion relation with the momentum, from which we first discuss the wave velocity direction versus the values of momentum, and distinguish the incident wave and the reflected wave. The gap between two energy bands depends on the parameters of coincident operator, so the phase defects, which break down the translation invariance of quantum walk on uniform lattices, can be regarded as an analogue of quantum potential. Then we use the condition of energy conversion at the boundary points to obtain the transmission rate and discuss its variation with the incident momentum for different strengths and widths of defects in detail. The multiple resonant peaks are observed due to the enhanced interference effect. Different resonant behaviors are shown when the strength of defect is less or greater than /2, correspondingly the resonances occur in a wide region of incident momentum or the sharp resonant peaks appear at discrete values of momentum. Under the condition of strong defect strength, i.e., approaching to , the qualitative relation between the number of resonant peaks and the widths of defect region is given. The number of resonant peaks is 2(N-1) when the two phase defects are located at N sites symmetric about the origin, while the number is 2N when a piece of phase defects is located at -N to N sites. In the case of a piece of phase defects, we also present the phase diagram in parameter space of (k, ) to show the discrete time of quantum walk propagating or tunneling through the defect region. In terms of this phase diagram, the variations of transmission rate with the incident momentum are reasonably explained. One special phenomenon is that the quantum walk is almost totally reflected in the tunneling case except for =/2 and k being slightly off -/2. Moreover, this behavior seems little affecting the defect strength, just similar to a classical particle. As a result of this research, we hope to deepen the insight of the quantum walk and provide methods to control the spreading of quantum walk through artificial defects.
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.