---
title: "Efficient Quantum Approximate kNN Algorithm via Granular-Ball Computing"
authors:
  - "Shuyin Xia"
  - "Xiaojiang Tian"
  - "Suzhen Yuan"
  - "Jeremiah D. Deng"
doi: "10.24963/ijcai.2025/739"
url: "https://ijcai.org/proceedings/2025/739"
pdf: "https://ijcai.org/proceedings/2025/0739.pdf"
venue: "Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence"
year: 2025
pages: "6642-6649"
track: "Main Track"
keywords:
  - "Search: S: Search and machine learning"
  - "Machine Learning: ML: Clustering"
  - "Machine Learning: ML: Other"
  - "Machine Learning: ML: Classification"
---

# Efficient Quantum Approximate kNN Algorithm via Granular-Ball Computing

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

*Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence*, pages 6642-6649. DOI: [10.24963/ijcai.2025/739](https://doi.org/10.24963/ijcai.2025/739)

## 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.