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

arXiv:2505.23066 · International Joint Conference on Artificial Intelligence

Efficient Quantum Approximate kNN Algorithm via Granular-Ball Computing

Shuyin Xia, Xiaojiang Tian, Suzhen Yuan, Jeremiah D. Deng

Published Sep 1, 2025• 2 citations
arXivHTMLPDF

Abstract

High time complexity is one of the biggest challenges faced by k-Nearest Neighbors (kNN). Although current classical and quantum kNN algorithms have made some improvements, they still have a speed bottleneck when facing large amounts of data. To address this issue, we propose an innovative algorithm called Granular-Ball based Quantum kNN(GB-QkNN). This approach achieves higher efficiency by first employing granular-balls, which reduces the data size needed to processed. The search process is then accelerated by adopting a Hierarchical Navigable Small World (HNSW) method. Moreover, we optimize the time-consuming steps, such as distance calculation, of the HNSW via quantization, further reducing the time complexity of the construct and search process. By combining the use of granular-balls and quantization of the HNSW method, our approach manages to take advantage of these treatments and significantly reduces the time complexity of the kNN-like algorithms, as revealed by a comprehensive complexity analysis.

DOI
10.24963/ijcai.2025/739

Related papers

Quantum granular-ball generation methods and their application in KNN classification

Suzhen Yuan, Xiaojiang Tian, Wenping Lin +2 more

Granular-balls reduce the data volume and enhance the efficiency of fundamental algorithms such as clustering and classification. However, generating granular-balls is a time-consuming process, posing a significant bottleneck for the practical application of granular-balls. In this paper, we propose two innovative quantum granular-ball generation methods that capitalize on the inherent properties of quantum computing. The first method employs an iterative splitting technique, while the second utilizes a predetermined number of splits. The iterative splitting method significantly reduces time complexity compared to existing classical granular-ball generation methods. Notably, the method employing a fixed number of splits delivers a substantial quadratic acceleration over the iterative technique. Moreover, we also propose a quantum k-nearest neighbors algorithm based on granular-balls (QGBkNN) and empirically show the effectiveness of our approach.

Scientific Reports•Aug 14, 2025•2 citations

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

Suzhen Yuan, Dehang Chen, Lifeng Shen +2 more

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.

arXiv:2609.05952•Sep 5, 2026•0 citations

Quantum multi-label k-nearest neighbor

Yilin Shen, Qin Liao

Although multi-label k-nearest neighbor (ML-kNN) is able to effectively solve multi-label learning (MLL) problem with local neighborhood similarity, its time complexity is nearly unacceptable with large-scale datasets. To solve this issue, we propose a novel ML-kNN algorithm with quantum computing techniques, which called quantum multi-label k-nearest neighbor (QML-kNN). In particular, we first accelerate the calculation of the prior probability by taking advantage of quantum phase estimation and Grover's amplitude amplification. Then, a controlled-SWAP test and a quantum k-maximal similarity search are used for efficiently identifying the neighbors. Subsequently, a quantum parallel counting circuit (QPCC) is designed to rapidly calculate the posterior probabilities. Experimental results demonstrate that QML-kNN is able to significantly reduce the time complexity of solving multi-label problems with performance improvement, achieving a substantial speedup over the classical MLL algorithm.

quant-pharXiv:2607.21919•Jul 27, 2026•0 citations

New approach of KNN Algorithm in quantum computing based on new design of quantum circuits

Vu Tuan Hai, Phan Hoang Chuong, Pham The Bao

Quantum computing has risen as the new type of computer that theoretically reduces the time complexity of classical methods exponentially because of the nature of superposition. It is promising to reduce runtimes on large data sets in machine learning (ML). Meanwhile, k-nearest neighbor (kNN) is a simple ML algorithm that can be translated to a quantum version (QkNN) to perform classification tasks efficiently. Here, we show a new version of QkNN which has a speed up in time complexity by using a new design of quantum circuits called integrated swap test. This quantum circuit can load two N-dimensional states and calculate the fidelity between them. Results show that QkNN allows us to take a different approach to the ML field.

Informatica•Apr 19, 2022•11 citations

QKNN: Noise‐Resilient Quantum KNN Algorithm for High‐Accuracy Classification

Asif Akhtab Ronggon, Tuhin Hossain, Tahani Jaser Alahmadi +1 more

ABSTRACT A quantum K‐nearest neighbors(QKNN) algorithm is proposed to offer superior performance compared to the classical KNN(CKNN) approach, improving classification accuracy, scalability, and robustness. Our approach optimizes Hadamard and rotation gates for quantum data encoding and efficiently embeds classical data into quantum states. Entangled gates, such as IsingXY and CNOT, enhance feature extraction and classification by enabling complex feature interactions. A new quantum distance metric based on swap test results is used to calculate similarity measures between quantum states. This algorithm offers superior accuracy and computational efficiency compared to traditional Euclidean distance metrics. We used three benchmark datasets to evaluate the suggested QKNN method. The results demonstrated that it outperformed the other two methods, classical KNN (CKNN) and quantum neural networks (QNN), as well as the more recent QKNN research. The proposed QKNN algorithm achieves prediction accuracies of 98.25%, 100%, and 99.27% for the three datasets, whereas the QNN achieves prediction accuracies of 97.17%, 83.33%, and 86.18%, respectively. Moreover, quantum noise challenges are addressed by integrating a Shor code‐based error mitigation strategy, which ensures stability of the algorithm and resilience to noisy quantum environments. The results demonstrate the scalability, efficiency, and robustness of the proposed QKNN algorithm.

Advanced Quantum Technologies•Jan 1, 2026•1 citation

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
High time complexity is one of the biggest challenges faced by k-Nearest Neighbors (kNN). Although current classical and quantum kNN algorithms have made some improvements, they still have a speed bottleneck when facing large amounts of data. To address this issue, we propose an innovative algorithm called Granular-Ball based Quantum kNN(GB-QkNN). This approach achieves higher efficiency by first employing granular-balls, which reduces the data size needed to processed. The search process is then accelerated by adopting a Hierarchical Navigable Small World (HNSW) method. Moreover, we optimize the time-consuming steps, such as distance calculation, of the HNSW via quantization, further reducing the time complexity of the construct and search process. By combining the use of granular-balls and quantization of the HNSW method, our approach manages to take advantage of these treatments and significantly reduces the time complexity of the kNN-like algorithms, as revealed by a comprehensive complexity analysis.
Granular-balls reduce the data volume and enhance the efficiency of fundamental algorithms such as clustering and classification. However, generating granular-balls is a time-consuming process, posing a significant bottleneck for the practical application of granular-balls. In this paper, we propose two innovative quantum granular-ball generation methods that capitalize on the inherent properties of quantum computing. The first method employs an iterative splitting technique, while the second utilizes a predetermined number of splits. The iterative splitting method significantly reduces time complexity compared to existing classical granular-ball generation methods. Notably, the method employing a fixed number of splits delivers a substantial quadratic acceleration over the iterative technique. Moreover, we also propose a quantum k-nearest neighbors algorithm based on granular-balls (QGBkNN) and empirically show the effectiveness of our approach.
QGB-WkkkNN: Quantum Granular-Ball Learning for Robust Classification
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 KKK-nearest neighbor classification framework based on quantum granular balls, termed QGB-WkkkNN. 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-WkkkNN 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.
Although multi-label k-nearest neighbor (ML-kNN) is able to effectively solve multi-label learning (MLL) problem with local neighborhood similarity, its time complexity is nearly unacceptable with large-scale datasets. To solve this issue, we propose a novel ML-kNN algorithm with quantum computing techniques, which called quantum multi-label k-nearest neighbor (QML-kNN). In particular, we first accelerate the calculation of the prior probability by taking advantage of quantum phase estimation and Grover's amplitude amplification. Then, a controlled-SWAP test and a quantum k-maximal similarity search are used for efficiently identifying the neighbors. Subsequently, a quantum parallel counting circuit (QPCC) is designed to rapidly calculate the posterior probabilities. Experimental results demonstrate that QML-kNN is able to significantly reduce the time complexity of solving multi-label problems with performance improvement, achieving a substantial speedup over the classical MLL algorithm.
Quantum computing has risen as the new type of computer that theoretically reduces the time complexity of classical methods exponentially because of the nature of superposition. It is promising to reduce runtimes on large data sets in machine learning (ML). Meanwhile, k-nearest neighbor (kNN) is a simple ML algorithm that can be translated to a quantum version (QkNN) to perform classification tasks efficiently. Here, we show a new version of QkNN which has a speed up in time complexity by using a new design of quantum circuits called integrated swap test. This quantum circuit can load two N-dimensional states and calculate the fidelity between them. Results show that QkNN allows us to take a different approach to the ML field.
ABSTRACT A quantum K‐nearest neighbors(QKNN) algorithm is proposed to offer superior performance compared to the classical KNN(CKNN) approach, improving classification accuracy, scalability, and robustness. Our approach optimizes Hadamard and rotation gates for quantum data encoding and efficiently embeds classical data into quantum states. Entangled gates, such as IsingXY and CNOT, enhance feature extraction and classification by enabling complex feature interactions. A new quantum distance metric based on swap test results is used to calculate similarity measures between quantum states. This algorithm offers superior accuracy and computational efficiency compared to traditional Euclidean distance metrics. We used three benchmark datasets to evaluate the suggested QKNN method. The results demonstrated that it outperformed the other two methods, classical KNN (CKNN) and quantum neural networks (QNN), as well as the more recent QKNN research. The proposed QKNN algorithm achieves prediction accuracies of 98.25%, 100%, and 99.27% for the three datasets, whereas the QNN achieves prediction accuracies of 97.17%, 83.33%, and 86.18%, respectively. Moreover, quantum noise challenges are addressed by integrating a Shor code‐based error mitigation strategy, which ensures stability of the algorithm and resilience to noisy quantum environments. The results demonstrate the scalability, efficiency, and robustness of the proposed QKNN algorithm.
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.