PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2609.06016v1cs.LG

TL;DR

Quantum clustering uses pairwise quantum-kernel evaluations that scale quadratically, while classical granular-ball methods rely on Euclidean metrics that miss complex structures. GBQC combines PCA-guided granular-ball compression with quantum-kernel merging and cohesion-based noise filtering; experiments report stronger clustering performance alongside fewer quantum-kernel evaluations. [The lead is grounded in the cited facets.]

  • Problem

    Quantum clustering requires O(n2) pairwise circuit executions, while classical granular-ball clustering reduces sample complexity but relies on Euclidean metrics that miss complex, entangled structures.

    Source: §1 · pp. 2–3

  • Method

    GBQC compresses data into PCA-guided granular balls, clusters their representations using quantum kernels, and applies quantum cohesion to filter unreliable granules during merging.

    Source: §1 · p. 3, §5 · p. 17

  • Results

    Across synthetic, noisy, overlapping, and real-world datasets, GBQC consistently achieves superior clustering performance while substantially reducing quantum-kernel evaluations.

    Source: §5 · p. 18

  • Takeaways & Limitations

    Granular-ball compression can serve as structural abstraction as well as resource reduction by removing redundant and structurally ambiguous learning units.

    Source: §5 · p. 18

    The study is limited to simulated quantum environments; deployment on real quantum hardware remains future work.

    Source: §5 · p. 18

Abstract

from arXiv · show

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.

1 Introduction

The introduction asks whether granular-ball representations can reduce quantum clustering costs without sacrificing quality, and identifies limits in classical compression and raw-sample quantum methods. GBQC couples PCA-guided granule generation and quantum cohesion with quantum-kernel clustering to address that challenge.

1 Introduction

  • Classical granular-ball clustering relies on Euclidean metrics, while quantum clustering on raw samples requires O(n2) pairwise similarities, leaving compression and structural fidelity unresolved together.The paper identifies this combination as a central practical challenge under limited quantum resources.Source: §1 · pp. 2–3
  • GBQC couples granular-ball compression with quantum feature learning to address scalability and structural-preservation challenges in quantum clustering.The paper frames the open question as whether granular-ball representations can reduce computational costs while improving clustering quality.Source: §1 · p. 3
  • PCA-guided hyperplane splitting produces about 50% fewer granular balls than GBCT, reducing the Swap Test executions needed to construct the pairwise similarity matrix.The strategy replaces Euclidean-based 2-means splitting with PCA-guided splitting.Source: §1 · p. 3
  • Quantum cohesion scores local-neighborhood reliability and filters noisy or unreliable granular balls during hierarchical merging.The stated aim is to prevent corrupted samples from degrading quantum similarity estimation and to maintain structural consistency.Source: §1 · p. 3
  • The framework combines compact granular-ball representations and cohesion-based refinement to alleviate quantum-kernel scaling costs while maintaining Hilbert-space similarity estimation.The introduction states that this combination leads to improved clustering accuracy and reduced computational cost.Source: §1 · p. 4

2 Related Work

The review covers classical clustering scalability, granular-ball compression, and NISQ quantum clustering constraints. Across these areas, methods that represent complex geometry face scaling costs or limits in preserving local structure.

2.1 Classical Clustering

  • Kernel and spectral approaches capture complex geometry, but eigen-decomposition costs O(n3) or full-kernel memory is prohibitive; low-rank approximations can sacrifice local geometry on entangled or noisy data.Linear-time K-Means is efficient, but its isotropic assumptions limit performance on non-convex clusters.Source: §2.1 · p. 4

2.2 Granular Ball Computing

  • Granular Ball Computing compresses n samples into m adaptive hyperspheres, but its Euclidean metrics fail to model intrinsic similarities on complex geometric structures.The review motivates quantum measures as a way to capture correlations that classical kernels cannot tractably model.Source: §2.2 · p. 4

2.3 Quantum Clustering and Quantum Kernel Methods

  • Quantum clustering includes quantum-subroutine and quantum-kernel approaches, yet raw-point similarity matrices still require O(n2) circuit executions and limit experiments to datasets with hundreds of samples.The review notes that granular-ball representations have been explored in quantum nearest-neighbor search, while their practical clustering effectiveness remains largely unexplored.Source: §2.3 · pp. 4–5

3 Methods

GBQC compresses data into granular balls, maps their centers into quantum feature space, and merges balls using local quantum cohesion. PCA-guided splitting and cohesion-based filtering define the framework’s main design choices.

3 Methods

  • GBQC first compresses raw samples into granular balls, then maps ball centers into Hilbert space and merges balls using cohesion.Figure 1 depicts these three coupled phases.Source: §3 · p. 5, Figure 1 · p. 5, §3.2 · p. 8

3.1 PCA-guided Granular Ball Generation

  • Candidate centers are sampled in rounds with probability proportional to squared distance from the nearest center, then k-means++ selects representative centroids for initial balls.Each sample is assigned to its nearest selected centroid to form the initial granular balls.Source: §3.1 · pp. 5–6
  • PCA-guided splitting uses core-sample principal directions and a global gain threshold to form compact granular balls while avoiding iterative 2-means splitting.The split hyperplane passes through the ball center, orthogonal to the first principal eigenvector; a split is retained only when its gain exceeds τ times the maximum initial-ball gain.Source: §3.1 · pp. 6–8, Figure 2 · p. 6

3.2.1 Quantum Feature Map

  • Each ball center is angle-encoded into a quantum state, and a Swap Test estimates pairwise quantum fidelity to construct the granular-ball kernel matrix.The encoded features map to the Bloch sphere, introducing nonlinear periodic characteristics distinct from Euclidean-based kernels.Source: §3.2.1 · p. 8, Figure 3 · p. 8, Figure 4 · p. 9

3.2.2 Cohesion-based Granular Ball Merging

  • Cohesion averages each ball’s quantum similarity to its k-nearest neighbors; the bottom 10% are temporarily excluded as potential noise before sparse-neighbor hierarchical merging.The resulting neighbor-based similarity is symmetrized and converted to a distance matrix for average-linkage clustering until the target cluster count is reached.Source: §3.2.2 · p. 9

3.3 Time Complexity Analysis

  • The complexity analysis identifies granular-ball generation as the dominant phase, involving distance computations for sampling and assignment and covariance construction for PCA splitting.The subsequent quantum-enhanced merging is also included in the analysis.Source: §3.3 · pp. 9–10

4 Experiments

Across synthetic, noise-injected, overlapping, and real datasets, GBQC is evaluated against classical and quantum clustering baselines. It achieves strong clustering performance while reducing quantum resource use, with ablations separating the roles of compression and cohesion.

4.2.1 Clustering on Synthetic Datasets

  • On datasets B and C, P-GBG stops splitting flat regions, unlike GBCT, which over-splits to satisfy strict internal consistency.This behavior eliminates redundant tiny granular balls.Source: Figure 5 · p. 12, §4.2.1 · p. 12
  • GBQC leads on 16 synthetic datasets, with average ACC 0.976 and NMI 0.975, while reducing Swap Test executions by approximately 80%.The average number of granular balls falls from 704 to 320; Table 2 reports the performance comparison.Source: Table 2 · p. 13, §4.2.1 · p. 13

4.2.2 Clustering on Noisy Datasets

  • GBQC achieves the highest average ACC and NMI on 16 noise datasets, with cohesion filtering suppressing noisy and structurally ambiguous granules.The proposed mechanism uses local cohesion in quantum feature space to identify and filter low-cohesion granules.Source: §4.2.2 · p. 14, Table 3 · p. 15

4.2.3 Ablation Studies

  • Across 16 synthetic datasets, P-GBG reduces average granular balls from 704.1 to 319.6, approximately 54.6%, without degrading clustering performance.The smaller representation reduces quantum similarity evaluations.Source: Table 1 · p. 11, §4.2.3 · p. 15

4.2.4 Clustering on Real Datasets

  • GBQC performs better on most real datasets but does not achieve the best result on Segment.Compared with GBCT, it yields substantial accuracy gains on Iris and Landsat.Source: Table 4 · p. 16, §4.2.4 · p. 16

4.2.3 Ablation Studies

  • Removing cohesion lowers average ACC on noisy datasets from 0.964 to 0.884, supporting its contribution to clustering robustness.The ablation attributes the difference to filtering structurally unreliable granules and erroneous connections from noise or ambiguous boundaries.Source: §4.2.3 · p. 16
  • The ablations assign complementary roles to P-GBG, which improves scalability, and cohesion, which improves robustness; together they lower quantum cost while improving clustering performance.P-GBG constructs a more compact granular-ball representation, while cohesion filters structurally unreliable granules.Source: §4.2.3 · p. 16

4.3 Runtime and Quantum Resource Analysis

  • GBQC generally runs within 10–100 seconds on tested synthetic datasets, while full-kernel QKKM often exceeds 10^3 seconds or times out.Its efficiency advantage is over quantum clustering methods, not lightweight classical methods such as K-Means.Source: Figure 6 · p. 17, §4.3 · p. 17

5 Conclusion

GBQC combines PCA-guided granular-ball generation with quantum-kernel merging and cohesion-based filtering. Experiments report strong clustering performance with fewer quantum kernel evaluations, while the study remains limited to simulated quantum environments.

5 Conclusion

  • Across synthetic, noisy, overlapping, and real-world datasets, GBQC achieves superior clustering performance while substantially reducing quantum kernel evaluations.The conclusion contrasts GBQC with conventional quantum clustering methods operating directly on raw samples.Source: §5 · pp. 17–18
  • Granular-ball compression is presented as a structural abstraction that removes redundant and ambiguous learning units while preserving clustering-relevant structure.The conclusion says this can improve clustering quality while reducing quantum computational costs.Source: §5 · p. 18
  • The study is limited to simulated quantum environments; deployment on real quantum hardware remains future work.Future work also includes trainable quantum feature maps and theoretical study of granulation, quantum feature representation, and clustering performance.Source: §5 · p. 18

A Time Complexity Analysis

The time-complexity analysis separates granular-ball generation from merging over the compressed set. With m on the order of √n, generation dominates GBQC's overall complexity.

A.1 Granular Ball Generation and Splitting

  • Generation uses t sampling rounds to update probabilities from O(√n) candidate samples against the n-point dataset, and covariance construction scans the dataset.The generation-phase total is given as O(n^1.5d + nd^2); eigen-decomposition for m balls is described as negligible when m ≪ n and d is typically small.Source: §A.1 · p. 22

A.2 Granular Ball Merging

  • Merging computes an m-by-m fidelity kernel, sorts similarities for k-nearest neighbors, and performs agglomerative hierarchical clustering over m balls.The stated costs are O(m^2d), O(m^2 log m), and O(m^3), respectively; substituting m≈√n gives O(nd), O(n log n), and O(n^1.5).Source: §A.2 · p. 22

A Time Complexity Analysis

B.1 The Information of The Datasets

The dataset section describes synthetic data and noisy variants, alongside five real-world benchmarks. The synthetic noise setup adds random global background noise to obscure cluster boundaries.

B.1 The Information of The Datasets

  • The noisy variants add random global background noise, creating cases where cluster boundaries are obscured by low-density noise.The noise generation follows the probability-distribution methodology described in.Source: §B.1 · p. 23
  • Table 6 covers 16 synthetic datasets (A–P) and their noise-injected counterparts.The table summarizes dataset characteristics.Source: §B.1 · p. 22, Table 6 · p. 23
  • Table 7 lists five real-world benchmarks curated from the UCI Machine Learning Repository and recent granular-ball studies [38].The datasets vary in scale and have irregular distributions.Source: Table 7 · p. 23, §B.1 · p. 23

B.2 Visualization of Clustering Results

GBQC visualizations show clustering assignments across synthetic datasets and noisy variants. The reported results describe successful recovery of varied cluster structures and retained accuracy under background noise.

B.2 Visualization of Clustering Results

  • GBQC identifies the correct cluster structures in the vast majority of 16 synthetic datasets spanning convex blobs, spirals, rings, and irregular shapes.Figure 7 presents the assignments; the text attributes the ability to separate linearly inseparable data to the quantum feature map.Source: §B.2 · p. 24
  • On noise-injected variants, GBQC maintains high clustering accuracy, with cohesion-based filtering distinguishing core members from background noise in spiral and ring examples.The text reports that cluster topology remains intact in the noisy spirals and rings.Source: §B.2 · p. 24
  • Figure 8 compares GBQC and other algorithms by runtime in seconds on synthetic datasets.Source: Figure 8 · p. 25

B.3 Running Time Comparison

GBQC runs in tens of seconds on the reported larger datasets, while direct quantum-kernel clustering can exceed 10^3 seconds. The section also points to parameter settings for the algorithms on synthetic datasets.

B.3 Running Time Comparison

  • Direct quantum-kernel clustering often exceeds 10^3 seconds on larger datasets, while GBQC generally runs in 10 to 100 seconds.GBQC is slightly slower than simple linear algorithms such as K-Means because of quantum circuit simulation overhead.Source: §B.3 · p. 25
  • GBQC is reported as significantly faster than spectral and kernel-based baselines, whose cited complexities are O(n2) or O(n3).The passage gives GBQC's approximate complexity in an incomplete form, so it is not restated here.Source: §B.3 · p. 25

B.4 Parameter Settings of All Algorithms

C Analysis on Overlapping Datasets

Across four synthetic overlap scenarios, GBQC is reported to outperform competing methods. The analysis attributes its performance under physical overlap to quantum feature mapping and its handling of fuzzy transition regions to cohesion-based filtering.

C Analysis on Overlapping Datasets

  • The four synthetic datasets cover touching multi-density clusters, highly overlapping Gaussian clusters, and intertwined non-convex structures.The datasets are described as boundary-blurred scenarios; their statistics are summarized in Table 10, and Figure 10 visualizes GBQC performance on overlap datasets.Source: C Analysis on Overlapping Datasets · pp. 26–27, Table 10 · p. 27, Figure 10 · p. 27
  • GBQC achieves superior performance across all four overlapping scenarios, as compared in Table 9.Source: C Analysis on Overlapping Datasets · p. 27
  • Despite sparse granular balls and substantial physical overlap, GBQC's clustering accuracy remains unaffected in the reported analysis.The authors attribute this to mapping ball centers into a high-dimensional Hilbert space, where the nonlinear feature map makes physically intersecting representations linearly distinguishable.Source: C Analysis on Overlapping Datasets · p. 28
  • On Overlap4, cohesion scores identify balls in fuzzy transition regions as potential noise during initial merging.The metric combines local-neighborhood information with quantum similarity; filtering weakly supported balls helps prevent merging distinct clusters through overlapping regions.Source: C Analysis on Overlapping Datasets · p. 28

D.1 Effectiveness of P-GBG Strategy

The ablations report that granular-ball generation improves runtime and that cohesion-based filtering improves results on noisy datasets. The PCA-guided splitting strategy is also associated with stronger performance than standard 2-means splitting, particularly on complex manifolds.

D.1 Effectiveness of P-GBG Strategy

  • The P-GBG ablation compares GBQC with direct sample-level quantum feature mapping and with granular-ball generation using 2-means splitting.Source: §D.1 · p. 28, Table 11 · p. 30
  • GBQC takes 25.39 seconds on average, compared with 6789.90 seconds for GBQC(w/o GB) and 226.28 seconds for GBQC-2means.The authors attribute the latter runtime difference to PCA-guided splitting converging with fewer splits and balls than standard 2-means.Source: §D.1 · p. 28, Table 11 · p. 30
  • GBQC consistently outperforms GBQC(2means), particularly on the complex-manifold Spirals and Rings datasets.The 2-means variant has reported Avg ACC: 0.893; the authors contrast its isotropic, spherical assumptions with PCA-guided splits orthogonal to maximum variance.Source: §D.1 · pp. 28–29

D.2 Effectiveness of Cohesion-based Merging

  • On 16 noise-injected datasets, GBQC achieves average ACC 0.964 versus 0.884 and NMI 0.944 versus 0.872 for the variant without cohesion.The reported ACC drops on Dnoise, Nnoise, and Mnoise are 0.998 →0.697, 0.999 →0.630, and 0.739 →0.596, respectively, when cohesion is removed.Source: §D.2 · p. 29, Table 12 · p. 31
  • During initial merging, GBQC temporarily filters the bottom 10% of low-cohesion balls to sever weak noise connections between clusters.Without this filtering, the hierarchical clustering algorithm may treat weak noise connections as valid structural links and erroneously merge separate clusters.Source: §D.2 · p. 29, Table 12 · p. 31
Loading 2609.06016v1…