Granular-Ball Quantum Clustering for Resource-Efficient and Robust Learning

Suzhen Yuan; Qilin Xie; Lifeng Shen; Shuyin Xia; Jermiah D. Deng; Guoying Wang

cs.LGSep 5, 2026

Granular-Ball Quantum Clustering for Resource-Efficient and Robust Learning

Authors: Suzhen Yuan, Qilin Xie, Lifeng Shen, Shuyin Xia, Jermiah D. Deng, Guoying Wang

Organizations: School of Electronic Science and Engineering, Chongqing University of Posts and Telecommunications, Chongqing, 400065, State, China. · School of Artificial Intelligence, Chongqing University of Posts and Telecommunications, Chongqing, 400065, State, China. · School of Computing, University of Otago, Dunedin, 9054, State, New Zealand. · School of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing, 400065, State, China. ·

Abstract

Quantum clustering aims to exploit quantum feature representations to uncover complex data structures beyond conventional Euclidean geometry. Yet this sample-level kernel construction requires O(n^2) quantum circuit executions for n data points, creating a major bottleneck under near-term quantum resource constraints. Prior solutions fail to resolve this efficiency-accuracy dilemma: classical granular-ball clustering reduces sample complexity but relies on Euclidean metrics that cannot capture quantum correlations, while existing quantum compression schemes prioritize efficiency over structural preservation, degrading performance on non-convex or noisy data. Here we propose Granular-Ball Quantum Clustering (GBQC), a framework that tightly couples granular-ball structural abstraction with quantum feature learning. GBQC first compresses raw data into compact, representative granular balls via a PCA-guided splitting strategy, reducing kernel evaluations by 80% compared to full-sample methods. A quantum cohesion mechanism then filters noisy granules in Hilbert space to improve clustering robustness. Extensive experiments on synthetic, noisy, overlapping, and real-world datasets demonstrate that GBQC consistently achieves superior clustering accuracy and robustness compared with representative classical and quantum clustering methods. Meanwhile, the proposed granular-ball compression significantly reduces quantum kernel evaluations and computational overhead, enabling quantum clustering experiments on larger datasets within parameterized quantum learning frameworks. These results suggest that granular-ball representations serve not only as a compression mechanism to reduce quantum computational costs but also as an effective structural abstraction mechanism that improves clustering quality by eliminating redundant and structurally ambiguous learning units.

Figures & tables

Figure 1: Overview of the GBQC framework. (i) Compressing data via PCA-guided granular ball generation; (ii) Mapping ball centers to Hilbert space for quantum kernel construction; (iii) Merging balls using the cohesion.

Figure 2: Illustration of the PCA-guided splitting mechanism. (a) Determination of the splitting axis orthogonal to the eigenvector using core samples; (b) The resulting partition into two child balls.

Figure 3: Illustration of the quantum feature mapping circuit based on angle encoding

Datasets	Gene_time (s)		GBs (Count)
Datasets	GBCT	P-GBG	GBCT	P-GBG
A	3.246	0.037	527	319
B	11.218	0.130	1934	447
C	10.088	0.130	1590	607
D	9.550	0.129	1568	637
E	1.811	0.027	247	265

Table 1: Comparison of generation time and number of granular balls between GB generation in GBCT and P-GBG.

Figure 5: Visual comparison of the number of GBs generated by P-GBG and GBCT on datasets B and C

Datasets	Metric	Classical Methods				Quantum Methods			Ours
Datasets	Metric	KM	DP	GBSC	GBCT	QM	QKKM	QCKM	GBQC
A	ACC	0.487	0.657	1.000	1.000	0.496	0.487	0.482	0.999
A	NMI	0.541	0.678	1.000	1.000	0.520	0.473	0.545	0.997
B	ACC	0.622	0.614	0.754	0.677	0.610	—	0.634	0.800
B	NMI	0.674	0.652	0.805	0.822	0.665	—	0.677	0.829
C	ACC	0.621	0.733	0.677	0.770	0.594	—	0.633	0.848

Table 2: Performance comparison on 16 synthetic datasets. Bold indicates the best result. “—” denotes memory overflow or timeout.

Datasets	Metric	Classical Methods				Quantum Methods			Ours
Datasets	Metric	KM	DP	GBSC	GBCT	QM	QKKM	QCKM	GBQC
A noise	ACC	0.487	0.648	0.914	0.926	0.498	0.452	0.482	1.000
A noise	NMI	0.536	0.663	0.935	0.876	0.524	0.415	0.525	1.000
B noise	ACC	0.620	0.622	0.814	0.853	0.579	—	0.623	0.855
B noise	NMI	0.673	0.697	0.911	0.921	0.636	—	0.676	0.880
C noise	ACC	0.625	0.755	0.586	0.645	0.563	—	0.602	0.851

Table 3: Performance comparison on 16 noise datasets. Bold indicates the best result. “—” denotes memory overflow or timeout.

Dataset	Metric	Classical Method				Quantum Method			Ours
Dataset	Metric	KM	DP	GBSC	GBCT	QM	QKKM	QCKM	GBQC
iris	ACC	0.887	0.907	0.853	0.660	0.880	0.793	0.833	0.953
iris	NMI	0.742	0.806	0.734	0.734	0.715	0.481	0.659	0.874
seeds	ACC	0.890	0.886	0.900	0.505	0.890	0.895	0.910	0.890
seeds	NMI	0.674	0.698	0.707	0.306	0.674	0.651	0.709	0.668
landsat	ACC	0.557	0.647	0.561	0.335	0.536	0.671	0.480	0.695

Table 4: Performance comparison on 5 real datasets. Bold indicates the best result. “—” denotes memory overflow or timeout.

Figure 6: Comparison of running time (seconds) between GBQC and other quantum algorithms on synthetic datasets.

Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

Method	Time Complexity
KM	$O(nktd)$
DP	$O(n^{2}d)$
GBSC	$O(n\log nd+n^{\frac{3}{2}})$
GBCT	$O(n^{\frac{3}{2}}d+n\log\sqrt{n}d)$
QM	$O(tk^{2}d\log n)$
QKKM	$O(n^{2}d)$

Appendix

Table 5: Time Complexity Comparison.

Dataset ID	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P
Clusters	6	7	6	9	3	3	4	3	2	3	2	3	4	4	5	3
Clean Inst.	1735	7679	7200	6800	1438	1641	1039	212	1043	1020	1502	3603	1427	1016	6698	1307
Noisy Inst.	1869	8097	8280	7586	1618	1723	1153	226	1119	1083	1579	3791	1598	1120	7109	1376

Appendix

Table 6: Detailed statistics of the 16 Synthetic Datasets and their Noise-injected counterparts.

Dataset	Instances	Dimensions	Clusters
iris	150	4	3
seeds	210	7	3
landsat	2000	2	6
segment	2310	3	7
mushroom	8124	2	2

Appendix

Table 7: Details of the 5 Real Datasets.

Figure 7: The Performance of GBQC on Synthetic Datasets

Figure 8: Comparison of Time (seconds) between GBQC and other algorithms on synthetic datasets.

Figure 9: The Performance of GBQC on Noisy Datasets

Dataset	KM	DP	GBSC	GBCT	QM	QKKM	QCKM	GBQC
A	$k=6$	$k=6$	$k=6,\delta=0.05$	$k=6$	$k=6$	$k=6$	$k=6,B=512,D=4$	$k=6$
B	$k=7$	$k=7$	$k=7,\delta=0.05$	$k=7$	$k=7$	$k=7$	$k=7,B=512,D=4$	$k=7$
C	$k=6$	$k=6$	$k=6,\delta=0.1\phantom{0}$	$k=6$	$k=6$	$k=6$	$k=6,B=512,D=4$	$k=6$
D	$k=9$	$k=9$	$k=9,\delta=0.05$	$k=9$	$k=9$	$k=9$	$k=9,B=512,D=4$	$k=9$
E	$k=3$	$k=3$	$k=3,\delta=0.05$	$k=3$	$k=3$	$k=3$	$k=3,B=512,D=4$	$k=3$
F	$k=3$	$k=3$	$k=3,\delta=0.05$	$k=3$	$k=3$	$k=3$	$k=3,B=512,D=4$	$k=3$

Appendix

Table 8: Parameters Settings on Synthetic Datasets.

Dataset	Metric	Classical Methods				Quantum Methods			Ours
Dataset	Metric	KM	DP	GBSC	GBCT	QM	QKKM	QCKM	GBQC
Overlap1	ACC	0.853	0.997	0.992	0.930	0.759	0.680	0.849	0.992
Overlap1	NMI	0.833	0.992	0.979	0.932	0.839	0.755	0.833	0.980
Overlap2	ACC	0.738	0.991	0.766	0.984	0.738	0.805	0.741	0.995
Overlap2	NMI	0.696	0.954	0.739	0.930	0.693	0.705	0.639	0.968
Overlap3	ACC	0.986	0.984	0.984	0.985	0.986	0.943	0.985	0.984

Appendix

Table 9: Performance comparison on 4 overlap datasets. Bold indicates the best result.

Figure 10: The Performance of GBQC on Overlap Datasets

Dataset	Overlap1	Overlap2	Overlap3	Overlap4
Instances	788	1280	1500	1400
Clusters	7	3	3	2

Appendix

Table 10: Detailed statistics of the 4 overlap datasets.

Dataset	Metric	GBQC	GBQC(w/o GB)	GBQC(2-means)
A	ACC	0.999	1.000	0.999
	NMI	0.997	1.000	0.997
	Time	18.972	1442.950	46.003
B	ACC	0.800	0.788	0.709
	NMI	0.829	0.815	0.801
	Time	38.040	27401.661	632.558

Appendix

Table 11: Ablation study on the effectiveness of the P-GBG strategy. We compare GBQC against a variant without granular ball generation (GBQC(w/o GB)) and a variant that uses standard 2-means splitting (GBQC(2-means)) across 16 synthetic datasets.

Dataset	Metric	GBQC	w/o Cohesion
A noise	ACC	1.000	0.804
A noise	NMI	1.000	0.855
B noise	ACC	0.855	0.851
B noise	NMI	0.880	0.880
C noise	ACC	0.851	0.804
C noise	NMI	0.788	0.735

Appendix

Table 12: Ablation study on the effectiveness of the cohesion-based merging mechanism. We compare the GBQC against a variant without cohesion (w/o Coh.) on 16 noisy datasets.

Clustering

Clustering groups data points by shared structure, developing methods to discover, validate, and interpret groups across diverse data and constraints.

See all 347 papers

QGB-W $k$ NN: Quantum Granular-Ball Learning for Robust Classification
Sep 5, 2026Suzhen Yuan, Dehang Chen, Lifeng Shen +2k-Nearest Neighbors Quantum Machine Learning
School of Electronic Science and Engineering, Chongqing University of Posts and Telecommunications, Chongqing, 400065, China · School of Artificial Intelligence, Chongqing University of Posts and Telecommunications, Chongqing, 400065, China · School of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing, 400065, China +2
Equivariant Quantum Clustering with Differential Privacy: Parameter-Efficient Privacy-Preserving Analysis Across Heterogeneous Sensitive Datasets
Jul 9, 2026B. M. Taslimul Haq, Md Arifur Rahman, Tawfiq Al Islam Foysal +2Clustering Quantum Machine Learning
Department of Information Systems, Central Michigan University, Mount Pleasant, MI, USA. · Department of Computer and Information Sciences, Trine University, Angola, IN, USA. · Department of Computer Science and Engineering, American International University–Bangladesh (AIUB), Dhaka, Bangladesh. +2
Benign Overfitting with Quantum Kernels
Mar 21, 2025Joachim Tomasi, Sandrine Anthoine, Hachem KadriBenign Overfitting Quantum Machine Learning
Aix-Marseille Univ, CNRS, LIS, Marseille, France. · Aix Marseille Univ, CNRS, I2M, Marseille, France.

Sep 5, 2026J/K move · Enter open · S save

QGB-W $k$ NN: Quantum Granular-Ball Learning for Robust Classification

Suzhen Yuan, Dehang Chen, Lifeng Shen, Shuyin Xia+1

School of Electronic Science and Engineering, Chongqing University of Posts and Telecommunications, Chongqing, 400065, China · School of Artificial Intelligence, Chongqing University of Posts and Telecommunications, Chongqing, 400065, China · School of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing, 400065, China+2

k-Nearest Neighbors Quantum Machine Learning Approximate Nearest Neighbor Search

Open paper AskPDF arXiv

Nearest-neighbor classification is widely used in machine learning, yet existing methods often suffer from low computational efficiency and limited robustness in noisy environments. To jointly address these challenges, this paper proposes an efficient and reliable weighted

K

-nearest neighbor classification framework based on quantum granular balls, termed QGB-W

k

NN. The proposed framework improves computational efficiency by integrating quantum-enhanced granular-ball representation with hierarchical nearest-neighbor search, while enhancing classification reliability through a purity-aware weighted decision mechanism. Specifically, quantum-kernel granular balls are constructed to reduce retrieval redundancy and strengthen nonlinear feature representation under limited quantum resources. A granular-ball purity-guided HNSW optimization strategy is developed to exploit structural reliability for hierarchical graph construction during neighbor retrieval, alleviating the local optimality issue caused by conventional random layering. Finally, a weighted voting mechanism jointly incorporating granular-ball similarity and purity is introduced to produce more reliable classification decisions in noisy environments. Extensive experiments on benchmark datasets demonstrate that QGB-W

k

NN achieves competitive classification accuracy while exhibiting favorable Pareto trade-offs between classification performance and computational cost. Moreover, the proposed framework consistently improves robustness under various noisy conditions, suggesting that reliability-aware quantum granular-ball learning provides a promising paradigm for efficient and robust nearest-neighbor classification.

Abstract

Clustering

Explore similar work

QGB-WkkkNN: Quantum Granular-Ball Learning for Robust Classification

Equivariant Quantum Clustering with Differential Privacy: Parameter-Efficient Privacy-Preserving Analysis Across Heterogeneous Sensitive Datasets

Benign Overfitting with Quantum Kernels

QGB-W $k$ NN: Quantum Granular-Ball Learning for Robust Classification