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. · Key Laboratory of Big Data Intelligent Computing, Key Laboratory of Cyberspace Big Data Intelligent Security, Ministry of Education, Chongqing University of Posts and Telecommunications, Chongqing, 400065, State, China. · National Center for Applied Mathematics in Chongqing, Chongqing Normal University, Chongqing, 401331, State, China.
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
Figure 4: The SwapTest Quantum Circuit
Datasets
Gene_time (s)
GBs (Count)
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
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
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
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
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
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
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
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
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
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(n2d)
GBSC
O(nlognd+n23)
GBCT
O(n23d+nlognd)
QM
O(tk2dlogn)
QKKM
O(n2d)
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,δ=0.05
k=6
k=6
k=6
k=6,B=512,D=4
k=6
B
k=7
k=7
k=7,δ=0.05
k=7
k=7
k=7
k=7,B=512,D=4
k=7
C
k=6
k=6
k=6,δ=0.10
k=6
k=6
k=6
k=6,B=512,D=4
k=6
D
k=9
k=9
k=9,δ=0.05
k=9
k=9
k=9
k=9,B=512,D=4
k=9
E
k=3
k=3
k=3,δ=0.05
k=3
k=3
k=3
k=3,B=512,D=4
k=3
F
k=3
k=3
k=3,δ=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
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
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
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
NMI
1.000
0.855
B noise
ACC
0.855
0.851
NMI
0.880
0.880
C noise
ACC
0.851
0.804
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.
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-WkNN. 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-WkNN 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.
Suzhen Yuan, Dehang Chen, Lifeng Shen +2
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
Privacy-preserving clustering is critical for analyzing sensitive data in healthcare, cybersecurity, and enterprise applications, where maintaining data confidentiality must be balanced with analytical performance. This paper presents Equivariant Quantum Clustering (EQC), a parameter-efficient framework that integrates symmetry-aware quantum circuits with differential privacy to improve the privacy-utility tradeoff. EQC employs p4m equivariant parameter sharing to reduce circuit complexity while preserving informative feature representations. The framework is evaluated on three privacy-sensitive datasets: NSL-KDD, CERT Insider Threat v6.2, and a synthetic MIMIC-III clinical dataset. On the NSL-KDD benchmark, EQC achieves 79.3% clustering accuracy while reducing membership inference attack success to 38.3% under a privacy budget of ε = 1.0 and δ = 10^-5, outperforming representative classical and quantum baselines. Ablation studies indicate that the performance gains primarily arise from parameter-efficient circuit design combined with differential privacy. The results demonstrate that EQC provides a practical quantum-ready framework for secure and privacy-preserving clustering across heterogeneous sensitive datasets.
B. M. Taslimul Haq, Md Arifur Rahman, Tawfiq Al Islam Foysal +2
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
Kernel methods compare inputs through feature maps. Quantum kernels follow the same principle: input data are encoded into quantum states, which define quantum feature representations in Hilbert spaces. Kernel values are then obtained by estimating inner products between these states using suitable quantum circuit measurements. As a result, quantum kernels may be intractable to compute classically while remaining efficiently computable on quantum hardware, potentially leading to a quantum advantage. However, designing effective quantum kernels remains a major challenge. Many quantum kernels, such as the fidelity kernel, suffer from exponential concentration. This results in near-identity kernel matrices that fail to capture meaningful data correlations and lead to overfitting and poor generalization. In this paper, we propose a novel strategy for constructing quantum kernels that achieve good generalization performance, drawing inspiration from benign overfitting in classical machine learning. We introduce the concept of Local-Global quantum kernels, which combine two components: a local quantum kernel based on measurements of small subsystems, and a global quantum kernel derived from full-system measurements. To support the effectiveness of the proposed construction, we show theoretically and empirically that Local-Global quantum kernels exhibit benign overfitting.
Joachim Tomasi, Sandrine Anthoine, Hachem Kadri
Aix-Marseille Univ, CNRS, LIS, Marseille, France. · Aix Marseille Univ, CNRS, I2M, Marseille, France.