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

Suzhen Yuan; Dehang Chen; Lifeng Shen; Shuyin Xia; Jeremiah D. Deng

cs.LGSep 5, 2026

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

Authors: Suzhen Yuan, Dehang Chen, Lifeng Shen, Shuyin Xia, Jeremiah D. Deng

Organizations: 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 · 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, China ·

Abstract

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.

Figures & tables

Symbol	Description
$k$	Number of neighbors in $k$ -NN
$N$	Total number of samples in dataset
$M$	Dataset size after granular ball compression ( $M\ll N$ )
$GB$	Granular ball (core data structure)
$P$	Purity of a granular ball (majority-class ratio)
$T$	Purity threshold for granular ball splitting

Table 1: Key Notations Used in the Paper

Figure 2: Quantum kernel estimation ansatz.

Panel of Figure 3 — Figure 3: Illustration of the local optimum problem of Hierarchical Navigable Small World (HNSW) and its mitigation strategy based on granular balls. (a) The local optimum problem of HNSW, where query point A locates the locally optimal nearest neighbor point C. (b) The granular ball-based hierarchical assignment strategy alleviates the local optimum problem of HNSW, enabling query point A to find its true nearest neighbor point B.

Method	Construction	Search
QGB-W $k$ NN	$O(N\cdot d)$	$O(d+\log M)$
GB $k$ NN++	$O\left((T+R)\cdot N\cdot d\right)$	$O(k_{g}\cdot d)$
HNSW	$O(N\cdot\log N)$	$O(d\cdot\log N)$
QSVC	${O(N^{3})}$	$O(d\cdot n_{q})$
GLVQ	$O(N\cdot n_{p}\cdot d)$	$O(n_{p}\cdot d)$

Table 2: Time Complexity Comparison of Different Methods

Symbol	Description
$k_{g}$	Number of subgraphs in DiskANN
$n_{q}$	Number of qubits for angle encoding
${n_{p}}$	Number of prototype vectors of GLVQ

Table 3: Explanations of Core Symbols in Time Complexity Comparison

	Dataset	Samples	Dim	Classes
	Ionosphere	351	34	2
	Spambase	4601	57	2
	German Credit	1000	20	2
real	Diabetes (Pima)	768	8	2
	Breast Cancer	569	30	2
	Mushrooms	8124	117	2

Table 4: Key Information of Experimental Datasets.

Dataset

QGB-W

k

k

GLVQ

HNSW

k

QSVC

Acc

Macro-F1

Acc

Macro-F1

Acc

Macro-F1

Acc

Macro-F1

Acc

Macro-F1

Acc

Macro-F1

20newsgroups

0.919

\pm

0.006

0.918

0.538

\pm

0.026

0.539

0.859

\pm

0.005

0.862

0.866

\pm

0.008

0.868

0.866

\pm

0.008

0.868

—

breastcancer

0.962

\pm

0.010

0.959

0.933

\pm

0.036

0.928

0.962

\pm

0.020

0.959

0.953

\pm

0.022

0.949

0.953

\pm

0.022

0.949

0.848

\pm

0.045

0.830

diabetes

0.766

\pm

0.030

0.751

0.678

\pm

0.043

0.655

0.749

\pm

0.029

0.708

0.747

\pm

0.007

0.715

0.747

\pm

0.007

0.715

0.716

\pm

0.008

0.627

german_credit

0.717

\pm

0.040

0.691

0.618

\pm

0.050

0.570

0.722

\pm

0.028

0.608

0.717

\pm

0.008

0.615

0.717

\pm

0.008

0.615

—

ionosphere

0.873

\pm

0.037

0.860

0.826

\pm

0.035

0.783

0.812

\pm

0.064

0.762

0.822

\pm

0.080

0.774

0.822

\pm

0.080

0.774

0.808

\pm

0.064

0.763

Table 5: Comparison on classification accuracy and macro-F1. Bold indicates the best result. “—” denotes memory overflow or timeout.

Figure 4: Pareto trade-off between classification accuracy and computational overhead of different methods on the 20newsgroups dataset during model construction and inference stages. Some baseline methods are not presented in the Pareto diagrams because their excessive computational consumption or inferior classification performance leads to completely dominated solutions, which provides no valid comparison significance. The proposed QGB-W

k

NN achieves a better balance between accuracy and efficiency.

Figure 5: Pareto trade-off between classification accuracy and computational overhead of different methods on the Ionosphere dataset during model construction and inference stages. Several baseline methods are omitted here since their performance is fully dominated by other competitors, resulting in no effective Pareto optimal solutions for comparison. QGB-W

k

NN maintains a favorable balance between classification performance and computational cost.

Dataset

QGB-W

k

k

GLVQ

HNSW

k

QSVC

Acc

Macro-F1

Acc

Macro-F1

Acc

Macro-F1

Acc

Macro-F1

Acc

Macro-F1

Acc

Macro-F1

20newsgroups

0.917

\pm

0.005

0.916

0.823

\pm

0.005

0.824

0.855

\pm

0.003

0.858

0.861

\pm

0.007

0.863

0.861

\pm

0.007

0.863

—

breastcancer

0.965

\pm

0.000

0.962

0.930

\pm

0.015

0.924

0.962

\pm

0.013

0.959

0.962

\pm

0.020

0.959

0.962

\pm

0.020

0.959

0.789

\pm

0.035

0.771

diabetes

0.764

\pm

0.032

0.749

0.723

\pm

0.027

0.684

0.755

\pm

0.031

0.715

0.745

\pm

0.016

0.713

0.745

\pm

0.016

0.713

—

german_credit

0.725

\pm

0.043

0.701

0.670

\pm

0.005

0.593

0.722

\pm

0.014

0.584

0.727

\pm

0.033

0.626

0.727

\pm

0.033

0.626

—

ionosphere

0.873

\pm

0.028

0.861

0.864

\pm

0.008

0.841

0.803

\pm

0.070

0.746

0.822

\pm

0.080

0.774

0.822

\pm

0.080

0.774

0.761

\pm

0.014

0.721

Table 6: Classification accuracy and macro-F1 under noise ratio

\boldsymbol{0.2}

. Bold indicates the best result. “—” denotes memory overflow or timeout.

Dataset

QGB-W

k

k

GLVQ

HNSW

k

QSVC

Acc

Macro-F1

Acc

Macro-F1

Acc

Macro-F1

Acc

Macro-F1

Acc

Macro-F1

Acc

Macro-F1

20newsgroups

0.895

\pm

0.017

0.894

0.807

\pm

0.010

0.808

0.845

\pm

0.001

0.848

0.850

\pm

0.002

0.851

0.850

\pm

0.002

0.851

—

breastcancer

0.950

\pm

0.005

0.947

\pm

0.026

0.943

0.953

\pm

0.010

0.949

0.956

\pm

0.018

0.953

0.956

\pm

0.018

0.953

0.681

\pm

0.022

0.662

diabetes

0.742

\pm

0.053

0.731

0.684

\pm

0.023

0.652

0.740

\pm

0.028

0.702

0.714

\pm

0.017

0.674

0.714

\pm

0.017

0.674

—

german_credit

0.712

\pm

0.042

0.681

0.673

\pm

0.037

0.610

0.743

\pm

0.032

0.608

0.693

\pm

0.024

0.582

0.693

\pm

0.024

0.582

—

ionosphere

0.850

\pm

0.008

0.838

0.864

\pm

0.022

0.845

0.808

\pm

0.064

0.757

0.831

\pm

0.061

0.790

0.831

\pm

0.061

0.790

0.723

\pm

0.045

0.695

Table 7: Classification accuracy and macro-F1 under noise ratio

\boldsymbol{0.4}

. Bold indicates the best result. “—” denotes memory overflow or timeout.

Panel of Figure 6 — Figure 6: Parameter sensitivity analysis of the proposed QGB-W $k$ NN. (a) Classification accuracy with respect to the purity threshold $T$ . (b) Macro-F1 score with respect to the purity threshold $T$ . (c) Classification accuracy with respect to the similarity threshold $T_{s}$ . (d) Macro-F1 score with respect to the similarity threshold $T_{s}$ .

Dataset	Noise Ratio	Basic	P- $k$ NN	W- $k$ NN	QGB-W $k$ NN
Ionosphere	0	0.822	0.859	0.887	0.873
	0.2	0.822	0.831	0.873	0.873
	0.4	0.831	0.831	0.873	0.850
Spambase	0	0.918	0.919	0.912	0.905
	0.2	0.903	0.908	0.897	0.900
	0.4	0.893	0.858	0.872	0.867

Table 8: Accuracy of Basic, P-

k

NN, W-

k

NN and QGB-W

k

NN under various noise ratios on datasets.

Dataset	Noise Ratio	Basic	P- $k$ NN	W- $k$ NN	QGB-W $k$ NN
Ionosphere	0	0.774	0.800	0.849	0.860
	0.2	0.774	0.769	0.847	0.861
	0.4	0.790	0.769	0.820	0.838
Spambase	0	0.913	0.903	0.900	0.900
	0.2	0.898	0.892	0.900	0.894
	0.4	0.887	0.835	0.850	0.860

Table 9: Macro-recall of Basic, P-

k

NN, W-

k

NN and QGB-W

k

NN under various noise ratios on datasets.

k-Nearest Neighbors

k-Nearest Neighbors (k-NN) predicts or retrieves from nearby data points using local similarity for classification, regression, clustering, and uncertainty.

See all 34 papers

Granular-Ball Quantum Clustering for Resource-Efficient and Robust Learning
Sep 5, 2026Suzhen Yuan, Qilin Xie, Lifeng Shen +3Clustering Quantum Machine Learning
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. +3
JGRA: Jacobian Geometry Robustness Assessment in NISQ Noise-Aware Quantum Neural Networks
Jun 8, 2026Gianluca Scanu, Luca Barletta, Stefano RiniNeural Network Robustness Quantum Machine Learning
Dipartimento di Elettronica, Informazione e Bioingegneria, Politecnico di Milano, 20133 Milan, Italy. · Department of Electrical and Computer Engineering, National Yang Ming Chiao Tung University (NYCU), Hsinchu, Taiwan.
Adaptive $k$ Nearest Neighbors Classifier via Granular Ball Computing
Aug 13, 2026Xiaoyu Lian, Shuyin Xia, Hongxuan He +3k-Nearest Neighbors
Chongqing Key Laboratory of Computational Intelligence, Key Laboratory of Cyberspace Big Data Intelligent Security, Ministry of Education, Sichuan-Chongqing Co-construction Key Laboratory of Digital Economy Intelligence and Key Laboratory of Big Data Intelligent Computing, Chongqing University of Posts and Telecommunications, 400065, Chongqing, China · College of Computer and Information Science, the National Center for Applied Mathematics in Chongqing, Chongqing Normal University, Chongqing 401331, China

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

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

Suzhen Yuan, Qilin Xie, Lifeng Shen, Shuyin Xia+2

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.+3

Clustering Quantum Machine Learning Quantum Kernel Methods

Open paper AskPDF arXiv

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.

Abstract

k-Nearest Neighbors

Explore similar work

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

JGRA: Jacobian Geometry Robustness Assessment in NISQ Noise-Aware Quantum Neural Networks

Adaptive kkk Nearest Neighbors Classifier via Granular Ball Computing

Adaptive $k$ Nearest Neighbors Classifier via Granular Ball Computing