Proceedings

Efficient Quantum Approximate kNN Algorithm via Granular-Ball Computing

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

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 6642-6649.

https://doi.org/10.24963/ijcai.2025/739

Keywords

  • Search: S: Search and machine learning
  • Machine Learning: ML: Clustering
  • Machine Learning: ML: Other
  • Machine Learning: ML: Classification

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.

Shuyin Xia, Xiaojiang Tian, Suzhen Yuan, and Jeremiah D. Deng. 2025. Efficient Quantum Approximate kNN Algorithm via Granular-Ball Computing. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 6642–6649. https://doi.org/10.24963/ijcai.2025/739
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards